Incremental Distance Join Algorithms for Spatial Databases

Summary: Two new spatial joins: distance join and distance semi-join; outputs ordered by distance. Incremental, pipelined algorithms support these operations over hierarchical spatial structures, arbitrary data types and dimensions, and any distance metric; R-tree experiments show large gains for partial results and modest full-result cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf386fa667d655fbd
Venue: SIGMOD
Year: 1998
Pagerank: 0.00010236406
Overall Rank: 1,554 | 89.59%
DOI: 10.1145/276304.276326

Incoming Non-self Citations Over Time

Authors

1. Gisli R. Hjaltason (University of Maryland)
2. Hanan Samet (University of Maryland)

BibTeX Citation

@inproceedings{hjaltason_sigmod98,
        title = {{Incremental Distance Join Algorithms for Spatial Databases}},
        author = {Hjaltason, Gisli R. and Samet, Hanan},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276326},
        url = {https://dl.acm.org/doi/10.1145/276304.276326},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
547	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016545689
1,311	Continuous Nearest Neighbor Search	2002	VLDB	0.00011063629
1,729	Closest Pair Queries in Spatial Databases	2000	SIGMOD	9.761101e-05
2,415	On Efficient Spatial Matching	2007	VLDB	8.4848606e-05
3,162	Efficient Spatial Sampling of Large Geographical Tables	2012	SIGMOD	7.5630152e-05
3,578	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.1743861e-05
5,547	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0715188e-05
5,783	Proximity Rank Join	2010	VLDB	5.9780797e-05
6,360	Clue-based Spatio-textual Query	2017	VLDB	5.78729e-05
6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7306642e-05
6,811	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.6598101e-05
7,185	C2P: Clustering based on Closest Pairs	2001	VLDB	5.5746325e-05
7,521	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.4881075e-05
8,783	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	5.2645572e-05
9,227	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.1903311e-05
10,336	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	5.0211131e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
9	Online Aggregation	1997	SIGMOD	0.00076079812
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051134355
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
398	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019117739
530	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016832286
968	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00012763144
2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5495935e-05
2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2212352e-05
4,522	Query Processing for Distance Metrics	1990	VLDB	6.5492954e-05
7,491	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.4981344e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	999	Spatial Hash-Joins	1996	SIGMOD
2	5,921	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
3	5,350	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
4	2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
5	1,729	Closest Pair Queries in Spatial Databases	2000	SIGMOD
6	7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
8	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD
10	6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD