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
| CREATOR | Eduardo V. L. Barboza, Robert Sabourin, Rafael M. O. Cruz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02752