In spatial databases, optimal matching refers to an assignment A between two set of spatial datasets (e.g., customers P and service providers Q) such that the assignment A ⊆ Q × P optimizes the quality of services (i.e., the quality of an assignment pair (q, p) can be measured by their Euclidean distance) subject to their capacity constraints (i.e., a service can serve up to k customers concurrently). Typically this problem can be solved by combinatorial optimization solvers or network flow based solutions, where these solutions require a distance-based affiliation matrix between the service providers and clients. For large spatial datasets, the affiliation matrix is expensive to compute and it may be too large to fit in main memory. Motivated by this challenge, some efficient algorithms are proposed for optimal matching that employ novel pruning strategies, based on the spatial properties of the problem.