Database Paper Browser

Back to papers

The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes

Summary: Introduces the K-D-B-tree, a disk-resident index for large, dynamic multikey workloads with interleaved inserts, deletes, and queries. It fuses K-D-tree multidimensional search with B-tree I/O efficiency to approximate both goals, with preliminary results supporting the approach. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2138
Venue
SIGMOD
Year
1981
Pagerank
0.0018397217
Overall Rank
5 | 99.97%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 65 citing papers.

Rank Citing Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
44 The Design Of Postgres 1986 SIGMOD 0.00071838587
76 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057303551
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
216 A Class of Data Structures for Associative Searching 1984 PODS 0.00033542705
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032163466
242 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00031110894
255 Interpolation-Based Index Maintenance 1983 PODS 0.00030498284
284 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028994728
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026768139
354 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026137988
503 Storage Mappings For Multidimensional Linear Dynamic Hashing 1983 PODS 0.00021520176
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018451109
736 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00017447617
769 Client-Server Paradise 1994 VLDB 0.00016918508
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,008 The BANG file: a new kind of grid file 1987 SIGMOD 0.00014666726
1,034 Redundancy in Spatial Databases 1989 SIGMOD 0.00014534274
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
1,184 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 0.00013455208
1,488 On the Analysis of Indexing Schemes 1997 PODS 0.00011699446
1,876 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 0.00010239284
1,997 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8322994e-05
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05
2,144 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4416732e-05
2,246 Parallel R-trees 1992 SIGMOD 9.2075292e-05
2,485 Multiattribute Hashing Using Gray Codes. 1986 SIGMOD 8.6800526e-05
2,678 Effectively Learning Spatial Indices 2020 VLDB 8.3252088e-05
3,039 High-Concurrency Locking in R-Trees 1995 VLDB 7.6708607e-05
3,064 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 7.6279403e-05
3,621 Angle-based Space Partitioning for Efficient Parallel Skyline Computation 2008 SIGMOD 6.9078084e-05
3,650 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8783391e-05
3,900 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.6518011e-05
4,286 Balanced Multidimensional Extendible Hash Tree 1986 PODS 6.2898839e-05
4,672 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.0085156e-05
5,021 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 5.7548311e-05
5,146 The Interpolation-Based Grid File 1985 PODS 5.6644798e-05
5,328 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 5.5665496e-05
5,363 A Mapping Function for the Directory of a Multidimensional Extendible Hashing 1984 VLDB 5.5471634e-05
5,461 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.4947899e-05
6,051 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2347385e-05
6,097 Two-dimensional Substring Indexing 2001 PODS 5.2119402e-05
6,270 MATE: Multi-Attribute Table Extraction 2022 VLDB 5.1337451e-05
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05
6,571 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.0061936e-05
7,250 A Scalable and Generic Approach to Range Joins 2022 VLDB 4.78908e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank Cited Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,498 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD 4.3341665e-05
14,348 Multi-Table Search For B-Tree Files 1979 SIGMOD -
8,767 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS 4.456315e-05
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
14,282 Performance Comparison Of Index Structures For Multi-Key Retrieval 1984 SIGMOD -
13,018 MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES 1985 SIGMOD 4.1945683e-05
12,294 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1945683e-05
4,672 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.0085156e-05
216 A Class of Data Structures for Associative Searching 1984 PODS 0.00033542705
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05