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: 3185
Venue: SIGMOD
Year: 2000
Pagerank: 0.00010622873
Overall Rank: 1,768 | 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
389	Query Processing in Spatial Network Databases	2003	VLDB	0.00024620268
1,275	Continuous Nearest Neighbor Search	2002	VLDB	0.00012883899
1,526	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	0.00011512916
1,763	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010638276
2,085	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	9.5804907e-05
2,247	On Efficient Spatial Matching	2007	VLDB	9.2048219e-05
3,800	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7585633e-05
6,770	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	4.9317829e-05
6,883	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8960306e-05
8,110	Adaptive Location Constraint Processing	2007	SIGMOD	4.5843047e-05
8,359	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5372925e-05
11,207	Closest Pairs Search Over Data Stream	2023	SIGMOD	4.1945683e-05
12,227	K-Nearest Neighbor Search for Fuzzy Objects	2010	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 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.0032169493
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
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
769	Client-Server Paradise	1994	VLDB	0.00016918508
871	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015767786
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,049	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	4.8505287e-05
12,751	Algorithms for Querying by Spatial Structure	1998	VLDB	4.1945683e-05
389	Query Processing in Spatial Network Databases	2003	VLDB	0.00024620268
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
1,631	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00011078269
6,883	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8960306e-05
6,500	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0381573e-05
3,800	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7585633e-05
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885