@inproceedings{sitchinava-ipdps18,
  author = {Kyle Berney and Henri Casanova and Alyssa Higuchi and Ben Karsin and Nodari Sitchinava},
  title = {Beyond binary search: parallel in-place construction of implicit search tree layouts},
  booktitle = {Proceedings of the 32nd International Parallel and Distributed Processing Symposium},
  series = {IPDPS '18},
  pages = {1070-1079},
  year = {2018},
  month = 5, 
  doi = {10.1109/IPDPS.2018.00116},
  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. Results indicate that on both CPU and GPU architectures B-tree layouts provide the best query performance. However, when considering the total time to permute the data and to perform a series of search queries, our vEB permutation provides the best performance on the CPU. We show that, given an input of $N=500\mathrm{M}$ $64$-bit integers, the benefits of query performance (compared to binary search) outweigh the cost of in-place permutation using our algorithms when performing at least $5\mathrm{M}$ queries ($1\%$ of $N$) and 27M queries ($6\%$ of $N$), on our CPU and GPU platforms, respectively."
}