Multicore construction of k-d trees with applications in graphics and vision

The k-d tree is widely used in graphics and vision applications for accelerating retrieval from large sets of geometric entities in R^k. Despite speeding up an otherwise brute force search, the time to construct and traverse the k-d tree remain a bottleneck in many applications. Increasing parallelism in modern processors offers hope for further speedups. But while traversal is easily parallelized over a large number of queries, construction is not as easily parallelized and will become a serial bottleneck if left unparallelized. This thesis studies parallel k-d tree construction and its applications. The results are new multicore parallelizations of SAH k-d tree and FLANN k-d tree variants, and new ways of utilizing these parallelizations for accelerating object detection and scripting point algorithms.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Lu, Victor

Contributors dc:contributor

• Hart, John C.
• Forsyth, David A.
• Hoiem, Derek W.
• Stroila, Matei

• vision
• computer graphics
• spatial data structures
• k-d trees
• multicore
• parallel algorithms
• ray-tracing
• nearest neighbor search
• image search
• object detection
• point cloud processing

Statement dc:rights

• Copyright 2013 Victor Lu

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/46588

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/46588