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: ha969318bd4f17a61
Venue: SIGMOD
Year: 1981
Pagerank: 0.00081200096
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 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019923528
34	The Design Of Postgres	1986	SIGMOD	0.00049129967
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045319457
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00045027197
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034847854
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033923053
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003136296
207	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024976482
265	A Class of Data Structures for Associative Searching	1984	PODS	0.00022748432
281	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022303081
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022001327
336	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020652147
339	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020561716
358	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020011298
522	Interpolation-Based Index Maintenance	1983	PODS	0.00016904732
744	Client-Server Paradise	1994	VLDB	0.00014305129
839	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.0001354488
855	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.00013431635
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013253709
967	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00012803465
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012388306
1,055	The BANG file: a new kind of grid file	1987	SIGMOD	0.00012261335
1,239	Processing Queries By Linear Constraints	1997	PODS	0.00011391184
1,529	On the Analysis of Indexing Schemes	1997	PODS	0.00010346523
1,774	ArrayStore: A Storage Manager for Complex Parallel Array Processing	2011	SIGMOD	9.6661993e-05
1,862	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.4827102e-05
1,877	Effectively Learning Spatial Indices	2020	VLDB	9.4498401e-05
1,904	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.3990319e-05
2,206	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	8.8514881e-05
2,390	Parallel R-trees	1992	SIGMOD	8.5335833e-05
2,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.1074382e-05
2,794	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.0003415e-05
3,113	High-Concurrency Locking in R-Trees	1995	VLDB	7.633977e-05
3,414	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.3210151e-05
3,671	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.1092737e-05
3,843	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	6.9863511e-05
4,061	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.8218692e-05
4,367	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	6.6312601e-05
4,445	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.5956997e-05
5,026	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.3069286e-05
5,279	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.1973533e-05
5,294	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	6.1899509e-05
5,508	The Interpolation-Based Grid File	1985	PODS	6.0988906e-05
5,708	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	6.0254866e-05
5,965	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.9302348e-05
6,037	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.9060765e-05
6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.7409998e-05
6,621	Two-dimensional Substring Indexing	2001	PODS	5.7303819e-05
6,907	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.6479055e-05
7,351	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.542858e-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,792	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
2	14,852	Multi-Table Search For B-Tree Files	1979	SIGMOD
3	9,110	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
4	1,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
5	14,798	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD
6	13,513	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD
7	12,785	Worst-Case Efficient Range Search Indexing	2009	PODS
8	5,026	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
9	265	A Class of Data Structures for Associative Searching	1984	PODS
10	6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB