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

Incoming Non-self Citations Over Time

Authors

1. John T. Robinson

Incoming Citations (Sorted by Pagerank)

Showing 15 of 65 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,495	ESDB: Processing Extremely Skewed Workloads in Real-time	2022	SIGMOD	4.7180617e-05
8,359	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5372925e-05
8,679	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	4.4697591e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
8,948	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	4.423786e-05
10,387	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1945683e-05
12,106	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	4.1945683e-05
12,277	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	4.1945683e-05
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
12,564	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.1945683e-05
12,625	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.1945683e-05
12,775	A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations	1997	VLDB	4.1945683e-05
12,940	Clustered Multiattribute Hash Files	1989	PODS	4.1945683e-05
13,018	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD	4.1945683e-05
13,019	Algorithm And Performance Evaluation Of Adaptive Multidimensional Clustering Technique	1985	SIGMOD	4.1945683e-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,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
14,348	Multi-Table Search For B-Tree Files	1979	SIGMOD	-
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
14,282	Performance Comparison Of Index Structures For Multi-Key Retrieval	1984	SIGMOD	-
13,018	MULTIKEY RETRIEVAL from K-d TREES and QUAD-TREES	1985	SIGMOD	4.1945683e-05
12,294	Worst-Case Efficient Range Search Indexing	2009	PODS	4.1945683e-05
4,672	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0085156e-05
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705
6,480	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0475112e-05