Closest Pair Queries in Spatial Databases

Summary: Five R-tree-based algorithms for K closest pairs between two spatial datasets; four recursive, one iterative. 1-pair case treated as special; extensive experiments on synthetic/real data show gains over existing incremental approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3186
Venue: SIGMOD
Year: 2000
Pagerank: 0.00010608375
Overall Rank: 1,769 | 87.71%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
391	Query Processing in Spatial Network Databases	2003	VLDB	0.00024560891
1,272	Continuous Nearest Neighbor Search	2002	VLDB	0.00012871443
1,545	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	0.00011428609
1,757	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010659352
2,088	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5707955e-05
2,248	On Efficient Spatial Matching	2007	VLDB	9.1958821e-05
3,802	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7524078e-05
6,802	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	4.9172931e-05
6,892	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8889412e-05
8,107	Adaptive Location Constraint Processing	2007	SIGMOD	4.5811252e-05
8,354	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5329424e-05
11,209	Closest Pairs Search Over Data Stream	2023	SIGMOD	4.1905499e-05
12,235	K-Nearest Neighbor Search for Fuzzy Objects	2010	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 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
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
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
766	Client-Server Paradise	1994	VLDB	0.0001690298
862	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015798065
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,048	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	4.8460286e-05
12,760	Algorithms for Querying by Spatial Structure	1998	VLDB	4.1905499e-05
391	Query Processing in Spatial Network Databases	2003	VLDB	0.00024560891
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
1,605	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011180126
6,892	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8889412e-05
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
3,802	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7524078e-05
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126