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: 2200
Venue: SIGMOD
Year: 1981
Pagerank: 0.00082404462
Overall Rank: 8 | 99.95%
DOI: 10.1145/582318.582321

Incoming Non-self Citations Over Time

Authors

1. John T. Robinson (Carnegie Mellon University)

BibTeX Citation

@inproceedings{robinson_sigmod81,
        title = {{The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes}},
        author = {Robinson, John T.},
        series = {{SIGMOD} '81},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582318.582321},
        url = {https://dl.acm.org/doi/10.1145/582318.582321},
        year = {1981}
}

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.0020210012
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
406	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00019054532
507	Interpolation-Based Index Maintenance	1983	PODS	0.00017277375
726	Client-Server Paradise	1994	VLDB	0.0001460632
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
833	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.0001372601
864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013522522
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,032	The BANG file: a new kind of grid file	1987	SIGMOD	0.00012530965
1,219	Processing Queries By Linear Constraints	1997	PODS	0.00011620957
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
1,742	ArrayStore: A Storage Manager for Complex Parallel Array Processing	2011	SIGMOD	9.8748669e-05
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
1,840	Effectively Learning Spatial Indices	2020	VLDB	9.6404567e-05
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.0469646e-05
2,341	Parallel R-trees	1992	SIGMOD	8.7233426e-05
2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.2957097e-05
2,742	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.1827223e-05
3,057	High-Concurrency Locking in R-Trees	1995	VLDB	7.807389e-05
3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.4203247e-05
3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.2750277e-05
3,771	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.1391812e-05
3,972	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.9814651e-05
4,357	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.7463723e-05
4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.4477987e-05
5,183	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	6.3286498e-05
5,304	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	6.2733516e-05
5,377	The Interpolation-Based Grid File	1985	PODS	6.2410452e-05
5,479	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.204351e-05
5,577	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	6.1661217e-05
5,857	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	6.0644613e-05
5,912	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	6.0442093e-05
6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.8751993e-05
6,491	Two-dimensional Substring Indexing	2001	PODS	5.8641664e-05
6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.7773009e-05
7,207	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.6727648e-05

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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
2	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
3	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
4	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
5	14,483	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD
6	13,217	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD
7	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
8	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
9	253	A Class of Data Structures for Associative Searching	1984	PODS
10	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB