Are van Emde Boas trees viable on the GPU?

Benedikt Mayr, Alexander Weinrauch, Mathias Parger, Markus Steinberger

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


Van Emde Boas trees show an asymptotic query complexity surpassing the performance of traditional data structure for performing search queries in large data sets. However, their implementation and large constant overheads prohibit their widespread use. In this work, we ask, whether van Emde Boas trees are viable on the GPU. We presents a novel algorithm to construct a van Emde Boas tree utilizing the parallel compute power and memory bandwidth of modern GPUs. By analyzing the structure of a sorted data set, our method is able to build a van Emde Boas tree efficiently in parallel with little thread synchronization. We compare querying data using a van Emde Boas tree and binary search on the GPU and show that for very large data sets, the van Emde Boas tree outperforms a binary search by up to 1.2x while similarly increasing space requirements. Overall, we confirm that van Emde Boas trees are viable for certain scenarios on the GPU
Original languageEnglish
Title of host publication2021 IEEE High Performance Extreme Computing Conference (HPEC)
PublisherIEEE Publications
Number of pages7
ISBN (Electronic)9781665423694
ISBN (Print)978-1-6654-2370-0
Publication statusPublished - 24 Sept 2021
Event26th IEEE High Performance Extreme Computing Conference : HPEC 2021 - Waltham, MA, USA, Virtuell, Austria
Duration: 20 Sept 202124 Sept 2021


Conference26th IEEE High Performance Extreme Computing Conference
Abbreviated titleHPEC 2021


  • CUDA
  • GPU
  • GPU querying
  • parallel construction
  • van Emde Boas tree
  • vEB tree

ASJC Scopus subject areas

  • Computational Mathematics
  • Artificial Intelligence
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Science Applications
  • Modelling and Simulation

Cite this