Database Paper Browser

Back to papers

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
3017
Venue
SIGMOD
Year
1998
Pagerank
0.00011078269
Overall Rank
1,631 | 88.66%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
601 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019375875
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,768 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010622873
2,247 On Efficient Spatial Matching 2007 VLDB 9.2048219e-05
2,981 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 7.7809306e-05
3,908 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD 6.6392878e-05
4,069 Proximity Rank Join 2010 VLDB 6.4789031e-05
5,636 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3981191e-05
6,012 Clue-based Spatio-textual Query 2017 VLDB 5.2415551e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-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
7,468 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 4.7210446e-05
8,223 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 4.5553657e-05
8,868 A Bayesian Method for Guessing the Extreme Values in a Data Set 2007 VLDB 4.4320869e-05
9,940 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 4.2456408e-05
Previous Page 1 / 1 Next

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.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
14 Online Aggregation 1997 SIGMOD 0.0010801504
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
470 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00022393068
478 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.0002222104
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
2,672 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3363695e-05
2,900 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9405413e-05
5,756 Query Processing for Distance Metrics 1990 VLDB 5.3401202e-05
7,133 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226285e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
5,860 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2990241e-05
4,612 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0484423e-05
2,900 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9405413e-05
1,768 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010622873
7,729 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6660821e-05
4,529 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.1078661e-05
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
2,672 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3363695e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05