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.00033533621
Overall Rank
217 | 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
75 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057450043
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
254 Interpolation-Based Index Maintenance 1983 PODS 0.00030506096
290 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00028845557
424 Amazon Redshift and the Case for Simpler Data Warehouses 2015 SIGMOD 0.00023604384
833 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016085787
923 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015254021
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00014524981
1,250 Fractals for Secondary Key Retrieval 1989 PODS 0.00013037936
2,001 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8275076e-05
2,471 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.7158825e-05
2,481 Multiattribute Hashing Using Gray Codes. 1986 SIGMOD 8.6794604e-05
2,492 Integrating the UB-Tree into a Database System Kernel 2000 VLDB 8.649434e-05
2,676 Effectively Learning Spatial Indices 2020 VLDB 8.326321e-05
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.6995792e-05
3,528 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0033241e-05
4,141 Approaching the Skyline in Z Order 2007 VLDB 6.4110324e-05
4,279 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.2850695e-05
4,544 On Indexing Line Segments 1990 VLDB 6.0939082e-05
4,741 An Experimental Analysis of Iterated Spatial Joins in Main Memory 2013 VLDB 5.951386e-05
5,145 The Interpolation-Based Grid File 1985 PODS 5.6596839e-05
5,972 On the Optimality of Clustering Properties of Space Filling Curves 2012 PODS 5.2462762e-05
6,569 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.0017701e-05
6,765 The hBII-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 4.9285619e-05
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
7,113 Parallel Algorithms for High-dimensional Proximity Joins 1997 VLDB 4.8226178e-05
7,412 Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse 1999 SIGMOD 4.7316475e-05
7,612 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 4.6919232e-05
7,653 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 4.6831774e-05
8,089 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 4.5855593e-05
9,863 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 4.2636378e-05
10,180 LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces 2026 SIGMOD 4.1905499e-05
10,516 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 4.1905499e-05
11,139 Efficient Cost Modeling of Space-filling Curves 2024 VLDB 4.1905499e-05
11,603 Dynamic Interleaving of Content and Structure for Robust Indexing of Semi-Structured Hierarchical Data 2020 VLDB 4.1905499e-05
12,428 Community-Driven Data Grids 2008 VLDB 4.1905499e-05
12,480 HiSbase: Histogram-based P2P Main Memory Data Management 2007 VLDB 4.1905499e-05
12,506 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 4.1905499e-05
12,950 Clustered Multiattribute Hash Files 1989 PODS 4.1905499e-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.0018380955
254 Interpolation-Based Index Maintenance 1983 PODS 0.00030506096
501 Storage Mappings For Multidimensional Linear Dynamic Hashing 1983 PODS 0.00021529047
8,064 A Dynamic Hash File for Random and Sequential Accessing 1983 VLDB 4.5900019e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
13,029 MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES 1985 SIGMOD 4.1905499e-05
12,756 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1905499e-05
3,806 Distributing a Search Tree Among a Growing Number of Processors 1994 SIGMOD 6.7461245e-05
2,010 Indexing for Data Models with Constraints and Classes (Extended Abstract) 1993 PODS 9.8046157e-05
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
4,026 Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 2016 PODS 6.5166769e-05
12,302 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1905499e-05
4,279 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.2850695e-05
6,473 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0427056e-05
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955