Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/62289

Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts.

File Size Format  
2018-05-ms-berney.pdf 991.84 kB Adobe PDF View/Open

Item Summary

Title:Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts.
Authors:Berney, Kyle M.
Contributors:Computer Science (department)
Keywords:permutation
searching
parallel
in-place
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
􀀀N
P

for the BST
layout, O
􀀀􀀀N
P + logB N

logB N

for the B-tree layout, and O
􀀀N
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.
URI:http://hdl.handle.net/10125/62289
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 libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.

Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.