Adaptive Multi-Stage Distance Join Processing

Summary: Adaptive multi-stage k-distance and incremental distance joins with R-tree indexes, bidirectional node expansion, and plane-sweep pruning. Axis- and directional plane-sweep optimizations prune distant pairs, delivering order-of-magnitude speedups over prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3259
Venue: SIGMOD
Year: 2000
Pagerank: 5.8809448e-05
Overall Rank: 6,426 | 55.92%
DOI: 10.1145/342009.335428

Incoming Non-self Citations Over Time

Authors

1. Hyoseop Shin (Seoul National University)
2. Bongki Moon (University of Arizona)
3. Sukho Lee (Seoul National University)

BibTeX Citation

@inproceedings{shin_sigmod00,
        title = {{Adaptive Multi-Stage Distance Join Processing}},
        author = {Shin, Hyoseop and Moon, Bongki and Lee, Sukho},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335428},
        url = {https://dl.acm.org/doi/10.1145/342009.335428},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,636	Relaxing Join and Selection Queries	2006	VLDB	0.00010156479
6,749	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.7844585e-05
9,026	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.3295983e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
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
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,544	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010410466
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
2,149	Probabilistic Optimization of Top N Queries	1999	VLDB	9.0821709e-05
2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.8700017e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD
2	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
3	522	Multi-Step Processing of Spatial Joins	1994	SIGMOD
4	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
5	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
6	1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD
7	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
8	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
9	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
10	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS