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

2025-04-30 0 0 290.46KB 8 页 10玖币

侵权投诉

A Stack-Free Traversal Algorithm for

Left-Balanced k-d Trees

Ingo Wald

(revision 1)

Abstract

We present an algorithm that allows for ﬁnd-closest-point and kNN-

style traversals of left-balanced k-d trees, without the need for either re-

cursion or software-managed stacks; instead using only current and last

previously traversed node to compute which node to traverse next.

1 Introduction

K-d trees (see Figure 1) are powerful, versatile, and widely used spatial data

structures for storing, managing, and performing queries on k-dimensional data.

One particularly interesting type of k-d trees are those that are left-balanced

and complete: for those, storing the tree’s nodes in level order means that the

entire tree topology—i.e., which are the parent, left, or right child of a given

node—can be deduced from each node’s array index. This means that such trees

require zero overhead for storing child pointers or similar explicit tree topology

data, which makes them particularly useful for large data, and for devices where

memory is precious (such as GPUs, FPGAs, etc). Throughout the rest of this

paper we will omit the adjectives left-balanced and complete, and simply refer

to ”k-d trees”; but always mean those that are both left-balanced and complete.

(7,2)

(5,4) (9,6)

(2,3) (4,7) (8,1)

0 2 4 6 8 10

Figure 1: Illustration of a 2-dimensional k-d tree from Wikipedia [Wik].

Left: The balanced tree for 2D point set {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}.

Right: The space partitioning achieved by that tree.

arXiv:2210.12859v2 [cs.DS] 2 Nov 2022

One issue with k-d trees is that their hierarchical nature means that they

work best with recursively formulated traversal techniques; but recursive for-

mulations can be problematic on highly parallel architectures such as, for ex-

ample, GPUs, FPGAs, dedicated hardware units, etc: true recursion—where

functions can call themselves—is often hard or impossible to realize on such

architectures, and is instead typically replaced with iterative algorithms that

emulate recursion through a manually managed stack of not-yet-traversed sub-

trees. Such “manual” stack based techniques do indeed avoid truly recursive

function calls—and thus work just ﬁne on GPUs—but can still cause several

issues: for example, maintaining a stack per live thread (of which there will

typically be many thousands) can require large amounts of temporary memory;

it can lead to a signiﬁcant amount of memory accesses (since such stacks are

can lead to hard-to-track errors if the reserved stack size isn’t large enough; etc.

In this paper, we describe a stack-free traversal algorithm for left-balanced

k-d trees that does not require any stack at all, and instead only requires two

integer values (for current and last traversed node IDs, respectively) to track all

traversal state. In particular, our algorithm can handle both simple unordered

traversals as well as the more channeling ordered kind where the traversal order

of two children depends on which side of the parent’s partitioning plane the

query point is located on. Our algorithm borrows from ideas we had previously

developed for bounding volume hierarchies [HDWS11], and relies on using a state

machine-like approach that, in each step, derives the respectively next node to

be traversed from some relatively simple logic that only needs to know the

current node that is currently traversed, and the one that was traversed in the

previous step. We describe the core algorithm, provide some simple pseudo-code

that realizes it, and present some performance data for a CUDA implementation

of various variations of ﬁnd-closest-point (fcp) and k-nearest-neighbor (kNN)

queries that use this algorithm.

2 Related Work

k-d Trees (sometimes also referred to as kd-trees) are hierarchical spatial search

trees used to encode k-dimensional data points [Sam90, Knu97, Wik]. Though

the same term in graphics is also sometimes used to refer to a diﬀerent kind of

spatial subdivision tree (where inner code describe arbitrary partitioning planes

and data are only stored in the leaves [WH06] ) for this paper we explicitly only

consider the former kind, in which the data to be encoded are k-dimensional

points, where points are stored also at inner nodes, and where partitioning

planes are deﬁned by the coordinates of the points stored at inner nodes (i.e.,

partitioning planes always pass through data points; see Figure 1).

Though k-d trees do not necessarily have to be balanced, one particularly

interesting type of k-d trees are those that are left-balanced and complete, since

these allow for storing the tree without any pointers or other explicit topology

data. In graphics, these became famous through photon mapping [Jen01], in

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AStack-FreeTraversalAlgorithmforLeft-Balancedk-dTreesIngoWald(revision1)AbstractWepresentanalgorithmthatallowsfornd-closest-pointandkNN-styletraversalsofleft-balancedk-dtrees,withouttheneedforeitherre-cursionorsoftware-managedstacks;insteadusingonlycurrentandlastpreviouslytraversednodetocomputewhic...

展开>> 收起<<

A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees Ingo Wald.pdf

共8页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: