Database Paper Browser

Back to papers

A Class of Data Structures for Associative Searching

Summary: Map tuples to integers by bit-interleaving (Morton/Z-order), letting conventional 1D indexes (e.g., B-trees) index multidimensional data. Produces a class of structures—an efficiently balanceable kd-tree variant, a simpler multidimensional B-tree, and related range-search indexes—that also support efficient set operations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
697
Venue
PODS
Year
1984
Pagerank
0.00033542705
Overall Rank
216 | 98.50%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
76 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057303551
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
255 Interpolation-Based Index Maintenance 1983 PODS 0.00030498284
290 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00028919734
426 Amazon Redshift and the Case for Simpler Data Warehouses 2015 SIGMOD 0.00023594359
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
925 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015264328
1,034 Redundancy in Spatial Databases 1989 SIGMOD 0.00014534274
1,249 Fractals for Secondary Key Retrieval 1989 PODS 0.00013044758
1,997 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8322994e-05
2,472 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.7237893e-05
2,485 Multiattribute Hashing Using Gray Codes. 1986 SIGMOD 8.6800526e-05
2,502 Integrating the UB-Tree into a Database System Kernel 2000 VLDB 8.6438339e-05
2,678 Effectively Learning Spatial Indices 2020 VLDB 8.3252088e-05
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.7002798e-05
3,527 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0073154e-05
4,142 Approaching the Skyline in Z Order 2007 VLDB 6.4138475e-05
4,286 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.2898839e-05
4,547 On Indexing Line Segments 1990 VLDB 6.0986695e-05
4,746 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 5.9571146e-05
5,146 The Interpolation-Based Grid File 1985 PODS 5.6644798e-05
5,990 On the Optimality of Clustering Properties of Space Filling Curves 2012 PODS 5.2424347e-05
6,571 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.0061936e-05
6,764 The hBII-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 4.9330419e-05
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
7,133 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226285e-05
7,433 Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse 1999 SIGMOD 4.7314388e-05
7,611 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 4.6964271e-05
7,651 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 4.6876337e-05
8,405 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 4.5224126e-05
9,864 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 4.2675822e-05
10,180 LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces 2026 SIGMOD 4.1945683e-05
10,507 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 4.1945683e-05
11,136 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 4.1945683e-05
11,599 Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data 2020 VLDB 4.1945683e-05
12,419 Community-Driven Data Grids 2008 VLDB 4.1945683e-05
12,471 HiSbase: Histogram-based P2P Main Memory Data Management 2007 VLDB 4.1945683e-05
12,497 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 4.1945683e-05
12,940 Clustered Multiattribute Hash Files 1989 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018397217
255 Interpolation-Based Index Maintenance 1983 PODS 0.00030498284
503 Storage Mappings For Multidimensional Linear Dynamic Hashing 1983 PODS 0.00021520176
8,060 A Dynamic Hash File for Random and Sequential Accessing 1983 VLDB 4.5943696e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
13,018 MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES 1985 SIGMOD 4.1945683e-05
12,747 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1945683e-05
3,804 Distributing a Search Tree Among a Growing Number of Processors 1994 SIGMOD 6.7525564e-05
2,003 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.8126082e-05
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
4,021 Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 2016 PODS 6.5225987e-05
12,294 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1945683e-05
4,286 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.2898839e-05
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018397217