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

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.