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: 3079
Venue: SIGMOD
Year: 1998
Pagerank: 0.00010493702
Overall Rank: 1,525 | 89.54%
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
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010017073
2,349	On Efficient Spatial Matching	2007	VLDB	8.7115756e-05
3,094	Efficient Spatial Sampling of Large Geographical Tables	2012	SIGMOD	7.765466e-05
3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.3597562e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05
5,640	Proximity Rank Join	2010	VLDB	6.1384844e-05
6,217	Clue-based Spatio-textual Query	2017	VLDB	5.9425753e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05
6,749	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.7844585e-05
7,023	C2P: Clustering based on Closest Pairs	2001	VLDB	5.7242118e-05
7,352	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.6353412e-05
8,593	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	5.4055214e-05
9,026	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.3295983e-05
10,087	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	5.1558402e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
9	Online Aggregation	1997	SIGMOD	0.00077458002
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
380	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019563191
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.432498e-05
5,798	Query Processing for Distance Metrics	1990	VLDB	6.0856815e-05
7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.6435709e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	994	Spatial Hash-Joins	1996	SIGMOD
2	5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
3	5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
4	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
5	1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD
6	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
8	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
10	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD