Multicore construction of k-d trees with applications in graphics and vision
Lu, Victor
Loading…
Permalink
https://hdl.handle.net/2142/46588
Description
Title
Multicore construction of k-d trees with applications in graphics and vision
Author(s)
Lu, Victor
Issue Date
2014-01-16T17:55:16Z
Director of Research (if dissertation) or Advisor (if thesis)
Hart, John C.
Doctoral Committee Chair(s)
Hart, John C.
Committee Member(s)
Forsyth, David A.
Hoiem, Derek W.
Stroila, Matei
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
computer graphics
vision
spatial data structures
k-d trees
multicore
parallel algorithms
ray-tracing
nearest neighbor search
image search
object detection
point cloud processing
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
