Files in this item

FilesDescriptionFormat

application/pdf

application/pdfVictor_Lu.pdf (5MB)
(no description provided)PDF

Description

Title:Multicore construction of k-d trees with applications in graphics and vision
Author(s):Lu, Victor
Director of Research:Hart, John C.
Doctoral Committee Chair(s):Hart, John C.
Doctoral Committee Member(s):Forsyth, David A.; Hoiem, Derek W.; Stroila, Matei
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2014-01-16
URI:http://hdl.handle.net/2142/46588
Rights Information:Copyright 2013 Victor Lu
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12


This item appears in the following Collection(s)

Item Statistics