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
3018
Venue
SIGMOD
Year
1998
Pagerank
0.00011180126
Overall Rank
1,605 | 88.85%
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
595 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019459302
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,769 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010608375
2,248 On Efficient Spatial Matching 2007 VLDB 9.1958821e-05
2,815 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 8.0773367e-05
3,911 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD 6.6343292e-05
4,072 Proximity Rank Join 2010 VLDB 6.4726748e-05
4,287 Clue-based Spatio-textual Query 2017 VLDB 6.2824978e-05
5,646 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3924438e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
6,802 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 4.9172931e-05
6,892 C2P: Clustering based on Closest Pairs 2001 VLDB 4.8889412e-05
7,469 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 4.7165172e-05
8,217 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 4.5519066e-05
8,868 A Bayesian Method for Guessing the Extreme Values in a Data Set 2007 VLDB 4.4278388e-05
9,940 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 4.241573e-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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
14 Online Aggregation 1997 SIGMOD 0.0010813443
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
469 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00022397468
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
833 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016085787
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
2,905 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9364369e-05
5,751 Query Processing for Distance Metrics 1990 VLDB 5.3396192e-05
7,113 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226178e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
5,864 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2947135e-05
4,613 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0427196e-05
2,905 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9364369e-05
1,769 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010608375
7,727 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6616221e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05