On Efficient Spatial Matching
In Very Large Data Bases conference (VLDB), 2007
This paper proposes and solves a new problem called
spatial matching (SPM). Let P and O be two sets of objects
in an arbitrary metric space, where object distances are defined according
to a norm satisfying the triangle inequality. Each object in O
represents a customer, and each object in P indicates a service
provider, which has a capacity corresponding to the maximum number of
customers that can be supported by the provider. SPM assigns each customer
to her/his nearest provider, among all the providers whose capacities have
not been exhausted in serving other closer customers. We elaborate the
applications where SPM is useful, and develop algorithms that settle this
problem with a linear number O(|P| + |O|) of nearest
neighbor queries. We verify our theoretical findings with extensive
experiments, and show that the proposed solutions outperform alternative
methods by a factor of orders of magnitude.
Before you proceed with downloading, please read and agree to the
terms of using
our implementation.
Download the source codes, which
include the implementations of SPM,
Gale-and-Shapley, and Closest-Pair. These codes were
accomplished by
Raymond Chi-Wing Wong.
Download the real datasets used in our
experiments, and the generator for
creating the synthetic data.