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 15 of 65 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,917	ESDB: Processing Extremely Skewed Workloads in Real-time	2022	SIGMOD	5.5181056e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
8,680	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	5.3857754e-05
8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.3577837e-05
8,986	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.3387783e-05
10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD	5.093636e-05
12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	5.093636e-05
12,472	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	5.093636e-05
12,489	Worst-Case Efficient Range Search Indexing	2009	PODS	5.093636e-05
12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	5.093636e-05
12,818	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	5.093636e-05
12,969	A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations	1997	VLDB	5.093636e-05
13,135	Clustered Multiattribute Hash Files	1989	PODS	5.093636e-05
13,217	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD	5.093636e-05
13,218	Algorithm And Performance Evaluation Of Adaptive Multidimensional Clustering Technique	1985	SIGMOD	5.093636e-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