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.00010275036
Overall Rank: 1,552 | 89.57%
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
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
1,304	Continuous Nearest Neighbor Search	2002	VLDB	0.00011104243
1,719	Closest Pair Queries in Spatial Databases	2000	SIGMOD	9.7976056e-05
2,406	On Efficient Spatial Matching	2007	VLDB	8.5169461e-05
3,150	Efficient Spatial Sampling of Large Geographical Tables	2012	SIGMOD	7.5916819e-05
3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.2015969e-05
5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0932822e-05
5,769	Proximity Rank Join	2010	VLDB	6.0007533e-05
6,346	Clue-based Spatio-textual Query	2017	VLDB	5.8092399e-05
6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7523628e-05
6,790	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.6812765e-05
7,162	C2P: Clustering based on Closest Pairs	2001	VLDB	5.5957758e-05
7,497	Boolean + Ranking: Querying a Database by K-Constrained Optimization	2006	SIGMOD	5.5089205e-05
8,755	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	5.2845183e-05
9,195	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.2100166e-05
10,301	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	5.040157e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
9	Online Aggregation	1997	SIGMOD	0.00076195956
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
396	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019162218
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016880616
965	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00012809362
2,358	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.5817166e-05
2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	8.2518251e-05
4,501	Query Processing for Distance Metrics	1990	VLDB	6.5741203e-05
7,468	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.5189807e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	994	Spatial Hash-Joins	1996	SIGMOD
2	5,905	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB
3	5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
4	2,588	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
5	1,719	Closest Pair Queries in Spatial Databases	2000	SIGMOD
6	7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	4,927	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,358	Spatial Joins Using Seeded Trees	1994	SIGMOD
10	6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD