Online K-d tree for approximate neighborhood search in data streams

Eduardo V. L. Barboza, Robert Sabourin, Rafael M. O. Cruz · 2026

Read Online K-d tree for approximate neighborhood search in data streams by Eduardo V. L. Barboza, Robert Sabourin, Rafael M. O. Cruz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02752.txt.

Description

Barboza and co-authors keep nearest-neighbor search fast on streaming data. The k-nearest neighbors method is a machine learning staple. Its neighborhood search cost can block large-scale use. K-d trees speed that search up. Data streams break their upkeep, though. Insertions and deletions on the fly strain balance and invariants. Classic K-d trees also assume Minkowski-style distances.

Their Online K-d tree supports dynamic updates over streams. Structural invariants needed for efficient traversal are preserved. An adaptation to the Canberra distance is included. That distance enables effective subtree pruning. Experiments show faster processing under streaming conditions. Average accuracy dips only slightly. Instances processed per second gain substantially. The implementation is public on GitHub. Streaming applications get a classic index that finally keeps up.

Catalog record

CREATOREduardo V. L. Barboza, Robert Sabourin, Rafael M. O. Cruz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.02752

Browse the full library · About the Tower of Babel