1. Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts
- Author
-
Kyle Berney, Ben Karsin, Nodari Sitchinava, and Henri Casanova
- Subjects
Binary search algorithm ,Computer science ,Sorted array ,Parallel algorithm ,Search tree ,Theoretical Computer Science ,Data modeling ,Permutation ,Computational Theory and Mathematics ,Hardware and Architecture ,Binary search tree ,Central processing unit ,Arithmetic ,Software - Abstract
We present parallel algorithms to efficiently 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. When considering the total time to permute the data in-place and to perform a series of search queries, the vEB layout provides the best performance on the CPU. Given an input of N=537 million 64-bit integers, the benefits of query performance (compared to binary search) outweigh the cost of in-place permutation when performing as few as 0.37% of N queries. On the GPU, results depend on the particular architecture, with the B-tree and vEB layouts performing the best. The number of queries necessary to reach the break-even point with binary search ranges from 1.3% to 8.9% of N=1,074 million 32-bit integers.
- Published
- 2022