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: 9611
Venue: VLDB
Year: 2007
Pagerank: 9.1958821e-05
Overall Rank: 2,248 | 84.38%
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,088	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5707955e-05
3,080	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.5993605e-05
3,238	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3284717e-05
5,979	On Optimal Worst-Case Matching	2013	SIGMOD	5.242029e-05
7,643	Feedback-Aware Social Event-Participant Arrangement	2017	SIGMOD	4.6853818e-05
11,337	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.1905499e-05
11,802	Flexible Online Task Assignment in Real-Time Spatial Data	2017	VLDB	4.1905499e-05
11,822	Spatial Crowdsourcing: Challenges, Techniques, and Applications	2017	VLDB	4.1905499e-05
11,931	Utility-Aware Social Event-Participant Planning	2015	SIGMOD	4.1905499e-05
12,359	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.1905499e-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.0016113151
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
1,656	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	0.00010975688
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375
2,696	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	8.279376e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,370	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2392118e-05
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375
3,275	Progressive Computation of the Min-Dist Optimal-Location Query	2006	VLDB	7.288391e-05
1,317	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012615781
3,080	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.5993605e-05
8,687	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.4621895e-05
3,238	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3284717e-05
9,308	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	4.3544778e-05
2,088	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5707955e-05
5,979	On Optimal Worst-Case Matching	2013	SIGMOD	5.242029e-05