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.00081207565
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 17 of 67 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,109	ESDB: Processing Extremely Skewed Workloads in Real-time	2022	SIGMOD	5.3739121e-05
8,391	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3248747e-05
8,813	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2570736e-05
8,877	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	5.2450451e-05
9,176	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.200391e-05
9,619	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	5.1376962e-05
10,378	AITTI: Augmented Interval Tree for Temporal Indexing	2027	SIGMOD	4.9605343e-05
10,976	RayBooster: A Ray Tracing Engine to Accelerate SedonaDB	2026	VLDB	4.9605343e-05
11,185	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.9605343e-05
12,643	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.9605343e-05
12,812	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	4.9605343e-05
12,828	Worst-Case Efficient Range Search Indexing	2009	PODS	4.9605343e-05
13,155	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.9605343e-05
13,306	A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations	1997	VLDB	4.9605343e-05
13,472	Clustered Multiattribute Hash Files	1989	PODS	4.9605343e-05
13,554	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD	4.9605343e-05
13,555	Algorithm And Performance Evaluation Of Adaptive Multidimensional Clustering Technique	1985	SIGMOD	4.9605343e-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,824	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
2	14,892	Multi-Table Search For B-Tree Files	1979	SIGMOD
3	9,129	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
4	1,514	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
5	14,838	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD
6	13,554	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD
7	12,828	Worst-Case Efficient Range Search Indexing	2009	PODS
8	5,050	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
9	267	A Class of Data Structures for Associative Searching	1984	PODS
10	6,597	Efficient Search of Multidimensional B-Trees	1995	VLDB