2026-09-25T12:00:09Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/46588 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

vision Hart, John C. Hart, John C. Forsyth, David A. Hoiem, Derek W. Stroila, Matei Lu, Victor 2014-01-16T17:55:16Z 2014-01-16T17:55:16Z 2013-12 2014-01-16T17:55:16Z 2013-12 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. Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-21T17:23:05Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lu_Victor.pdf: 4681223 bytes, checksum: 28512effd9a0cb023c991ef48f5577d6 (MD5) Made available in DSpace on 2014-01-16T17:55:16Z (GMT). No. of bitstreams: 2 Victor_Lu.pdf: 4680955 bytes, checksum: 368b0f882a3da85d8446a0edf6b8b352 (MD5) license.txt: 4059 bytes, checksum: f1efa4724423d20fef5fbf8964232842 (MD5) http://hdl.handle.net/2142/46588 en Copyright 2013 Victor Lu computer graphics spatial data structures k-d trees multicore parallel algorithms ray-tracing nearest neighbor search image search object detection point cloud processing Multicore construction of k-d trees with applications in graphics and vision text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Computer Science -UIUC 10KS0112PHD