On Efficient Spatial Matching

Summary: Defines spatial matching (SPM): assign each customer to the nearest provider with remaining capacity in a metric space. Algorithms achieve O(|P|+|O|) NN queries with linear-time processing; experiments show orders-of-magnitude speedups vs baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9610
Venue: VLDB
Year: 2007
Pagerank: 9.2048219e-05
Overall Rank: 2,247 | 84.37%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,085	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5804907e-05
3,071	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.6120001e-05
3,235	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3355287e-05
5,973	On Optimal Worst-Case Matching	2013	SIGMOD	5.2470655e-05
7,644	Feedback-Aware Social Event-Participant Arrangement	2017	SIGMOD	4.6898827e-05
11,335	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.1945683e-05
11,794	Flexible Online Task Assignment in Real-Time Spatial Data	2017	VLDB	4.1945683e-05
11,814	Spatial Crowdsourcing: Challenges, Techniques, and Applications	2017	VLDB	4.1945683e-05
11,923	Utility-Aware Social Event-Participant Planning	2015	SIGMOD	4.1945683e-05
12,351	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
1,682	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	0.00010923103
1,768	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010622873
2,711	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.2492925e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,373	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2443809e-05
1,768	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010622873
3,272	Progressive Computation of the Min-Dist Optimal-Location Query	2006	VLDB	7.2958583e-05
1,403	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012176993
3,071	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.6120001e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
3,235	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3355287e-05
9,308	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	4.3571035e-05
2,085	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5804907e-05
5,973	On Optimal Worst-Case Matching	2013	SIGMOD	5.2470655e-05