Multidimensional Binary Search Trees Used for Associative Searching¶
Bentley, J. L. (1975). Multidimensional Binary Search Trees Used for Associative Searching. Communications of the ACM, 18(9), 509-517.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Spatial Indexing
- The cheap geometric operation is built by recursively splitting the point set along alternating axes at the median, producing a balanced binary tree where each node owns an axis-aligned bounding box.
This sourceIntroduces the k-d tree: recursive median splits along alternating axes giving O(log n) nearest-neighbor and range queries in low dimensions via bounding-box pruning, with O(n log n) build cost.
SupportedVerified against the work's full text
Bentley's OPTIMIZE algorithm picks the J-median, splits, and recurses with the next discriminator, yielding a balanced k-d tree; each node has an associated bounds-array hyper-rectangle.
“The following algorithm produces an optimized k-d tree by building a tree such that the number of nodes in the HISON subtree of each node differs by at most one from the number of nodes in the LOSON subtree.”
- The cheap geometric operation is built by recursively splitting the point set along alternating axes at the median, producing a balanced binary tree where each node owns an axis-aligned bounding box.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 1 citation: 1 supported. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:c2daa7ce452f · see in the full table