Please use this identifier to cite or link to this item:
Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts.
|Title:||Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts.|
|Authors:||Berney, Kyle M.|
|Contributors:||Computer Science (department)|
|Date Issued:||May 2018|
|Publisher:||University of Hawaiʻi at Mānoa|
|Abstract:||We present parallel algorithms to e ciently permute a sorted array into the level-order binary search|
tree (BST), level-order B-tree (B-tree), and van Emde Boas (vEB) layouts in-place. We analytically
determine the complexity of our algorithms and empirically measure their performance. Given N
elements and P processors, our fastest algorithms have a parallel runtime of O
for the BST
P + logB N
for the B-tree layout, and O
P log logN
for the vEB layout
using the CREW Parallel Random Access Machine (PRAM) model. Experimental results indicate
that on both CPU and GPU architectures, the B-tree layout provides the best query performance.
However, when considering the total time to permute the data using our algorithms and to perform
a series of search queries, the vEB layout provides the best performance on the CPU. We show that
given an input of N=500M 64-bit integers, the bene ts of query performance (compared to binary
search) outweigh the cost of in-place permutation using our algorithms when performing at least
5M queries (1% of N) and 27M queries (6% of N), on our CPU and GPU platforms, respectively.
|Description:||M.S. Thesis. University of Hawaiʻi at Mānoa 2018.|
|Rights:||All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.|
|Appears in Collections:||
M.S. - Computer Science|
Please email email@example.com if you need this content in ADA-compliant format.
Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.