DBScholar

Back to papers

Spatial Hash-Joins

Summary: Defines a spatial hash-join framework with a two-component partition: bucket extents plus an assignment function; inner partitions adapt while outer partitions are immutable and may replicate items into multiple buckets. No precomputed indices required; it outperforms tree-based spatial joins (even with indices) and offers predictable costs and easy integration with existing hash-join engines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h3106f40a7860aecc
Venue
SIGMOD
Year
1996
Pagerank
0.00012630797
Overall Rank
994 | 93.33%
DOI
10.1145/233269.233337

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{lo_sigmod96,
        title = {{Spatial Hash-Joins}},
        author = {Lo, Ming-Ling and Ravishankar, Chinya V.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233337},
        url = {https://dl.acm.org/doi/10.1145/233269.233337},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
179 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026617591
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
1,081 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012126286
1,171 Set Containment Joins: The Good, The Bad and The Ugly 2000 VLDB 0.00011697392
1,594 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB 0.00010129129
1,924 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3706925e-05
1,998 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.2123795e-05
2,589 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2479257e-05
3,122 Size Separation Spatial Join 1997 SIGMOD 7.6263979e-05
3,223 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.5114215e-05
4,336 Joining Interval Data in Relational Databases 2004 SIGMOD 6.6528595e-05
4,570 Overlap Interval Partition Join 2014 SIGMOD 6.5270765e-05
4,928 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3473148e-05
4,958 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.3374701e-05
5,536 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0904184e-05
6,542 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7496415e-05
6,958 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6316072e-05
7,472 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 5.5163696e-05
9,204 A Bayesian Method for Guessing the Extreme Values in a Data Set 2007 VLDB 5.2075502e-05
10,787 Succinct and Fast Tiny Pointer Hash Tables 2026 VLDB 4.9769913e-05
11,495 Optimal (Multiway) Spatial Joins 2024 PODS 4.9769913e-05
12,479 An Effective Encoding Scheme for Spatial RDF Data 2014 VLDB 4.9769913e-05
12,779 LifeRaft: Data-Driven, Batch Processing for the Exploration of Scientific Databases 2009 CIDR 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
7 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.00081971778
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045319457
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029048509
156 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00028509887
744 Client-Server Paradise 1994 VLDB 0.00014305129
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
853 Hash-Partitioned Join Method Using Dynamic Destaging Strategy 1988 VLDB 0.00013439366
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00012388306
1,862 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4827102e-05
2,268 The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method 1989 VLDB 8.7182371e-05
2,298 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.6797199e-05
2,359 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5776736e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 963 Memory-Efficient Hash Joins 2015 VLDB
2 362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD
3 1,799 An Adaptive Hash Join Algorithm for Multiuser Environments 1990 VLDB
4 5,532 Generalized Hash Teams for Join and Group-by 1999 VLDB
5 2,359 Spatial Joins Using Seeded Trees 1994 SIGMOD
6 4,219 Spatial Partitioning Techniques in SpatialHadoop 2015 VLDB
7 11,495 Optimal (Multiway) Spatial Joins 2024 PODS
8 6,290 On Spatially Partitioned Temporal Join 1994 VLDB
9 4,928 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD
10 853 Hash-Partitioned Join Method Using Dynamic Destaging Strategy 1988 VLDB