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: 2139
Venue: SIGMOD
Year: 1981
Pagerank: 0.0018380955
Overall Rank: 5 | 99.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. John T. Robinson

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.0032118946
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
44	The Design Of Postgres	1986	SIGMOD	0.00071946446
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621
231	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00032141918
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
254	Interpolation-Based Index Maintenance	1983	PODS	0.00030506096
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
501	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS	0.00021529047
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018437125
730	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017443615
766	Client-Server Paradise	1994	VLDB	0.0001690298
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
929	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001523035
1,009	The BANG file: a new kind of grid file	1987	SIGMOD	0.00014658958
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00014524981
1,171	Processing Queries By Linear Constraints	1997	PODS	0.00013507216
1,184	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	0.00013442644
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,878	ArrayStore: A Storage Manager for Complex Parallel Array Processing	2011	SIGMOD	0.00010229691
2,001	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.8275076e-05
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05
2,245	Parallel R-trees	1992	SIGMOD	9.2048202e-05
2,481	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.6794604e-05
2,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
3,042	High-Concurrency Locking in R-Trees	1995	VLDB	7.6669657e-05
3,065	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.6258862e-05
3,616	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	6.9108126e-05
3,653	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8725114e-05
3,902	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6454492e-05
4,279	Balanced Multidimensional Extendible Hash Tree	1986	PODS	6.2850695e-05
4,669	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0039237e-05
5,013	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	5.7533424e-05
5,145	The Interpolation-Based Grid File	1985	PODS	5.6596839e-05
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
5,372	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB	5.5424242e-05
5,469	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.4895279e-05
6,055	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.2297716e-05
6,098	Two-dimensional Substring Indexing	2001	PODS	5.2078399e-05
6,268	MATE: Multi-Attribute Table Extraction	2022	VLDB	5.1288179e-05
6,473	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0427056e-05
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05
7,247	A Scalable and Generic Approach to Range Joins	2022	VLDB	4.7846107e-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	Pagerank
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
14,362	Multi-Table Search For B-Tree Files	1979	SIGMOD	-
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05
1,183	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013444058
14,296	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD	-
13,029	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD	4.1905499e-05
12,302	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1905499e-05
4,669	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0039237e-05
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621
6,473	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0427056e-05