A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees

2022/10/23 by Ingo Wald, Wald, Ingo
Computer Science · #Data Management and Algorithms #Advanced Database Systems and Queries #Data Mining Algorithms and Applications

paper · pdf · doi:10.48550/arxiv.2210.12859

Abstract

We present an algorithm that allows for find-closest-point and kNN-style traversals of left-balanced k-d trees, without the need for either recursion or software-managed stacks; instead using only current and last previously traversed node to compute which node to traverse next.

Related

• GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees
• Building a Balanced k-d Tree with MapReduce
• Building a Balanced k-d Tree in O(kn log n) Time
• Review of Three Algorithms That Build k-d Trees
• Tree-Independent Dual-Tree Algorithms