Abstract
The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary memory. By dynamic it is meant that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand. A new data structure, the K-D-B-tree, is presented as a solution to this problem. K-D-B-trees combine properties of K-D-trees and B-trees. It is expected that the multidimensional search effieciency of balanced K-D-trees and the I/O efficiency of B-trees should both be approximated in the K-D-B-tree. Preliminary experimental results that tend to support this are reported.
Keywords
B-treeTree (set theory)Index (typography)CombinatoricsComputer scienceWeight-balanced treeAlgorithmRange (aeronautics)Data structureMathematicsDiscrete mathematicsTheoretical computer scienceBinary treeBinary search treeMaterials science
Affiliated Institutions
Related Publications
Organization and maintenance of large ordered indices
Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like...
Similarity Search in High Dimensions via Hashing
The nearest- or near-neighbor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasin...
Best-first Decision Tree Learning
Decision trees are potentially powerful predictors and explicitly represent the structure of a dataset. Standard decision tree learners such as C4.5 expand nodes in depth-first ...
ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees
Evolutionary histories can be discordant across the genome, and such discordances need to be considered in reconstructing the species phylogeny. ASTRAL is one of the leading met...
The Grid file: A data structure designed to support proximity queries on spatial objects
Abstract : This document describes a technique for storing large sets of spatial objects so that proximity queries are handled efficiently as part of the accessing mechanism. Th...
Publication Info
- Year
- 1981
- Type
- article
- Pages
- 10-10
- Citations
- 885
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
885
OpenAlex
Cite This
John T. Robinson
(1981).
The K-D-B-tree.
, 10-10.
https://doi.org/10.1145/582318.582321
Identifiers
- DOI
- 10.1145/582318.582321