Abstract

Efficient searching in a number of strings is a common task in computer science and radix-trees are often used as a compact storage for string saving. One variant is the Adaptive-Radix-Tree (ART). ART has adaptive node sizes for more compact and cache-friendly memory layout. Graphical Processing Units (GPUs) can be used as hardware accelerator for massively parallel tasks and in addition they use very fast memory. We propose a parallel approximate search in the ART on CPU and GPU to optimize the throughput of queries and speed up applications that depends on these algorithms. Thereby we use the edit distance to compare two search keys in the tree and select appropriate values.We use the CPU for experimental comparison with the GPU, which have several thousand cores and modern processors typically have four to several dozens cores, but theses cores and RAM are more flexible. We propose several variations of the CPU algorithm like fixed vs. dynamic memory layouts and pointer vs. pointer-less data structures. In our experimental evaluation with OpenCL on ROCm 3.0, AMDs platform for GPU-Enabled HPC and Ultrascale Computing, the speedup and throughput of the GPU implementation for the approximate search in comparison with the best CPU variant are in the maximum up to factor 4.16 depending on the size of the tree and batch size. The speedup between the best and the worst CPU algorithm is up to factor 11.67, depending on tree and batch size.

Original languageEnglish
Pages56-67
Number of pages12
Publication statusPublished - 2020
Event28th Italian Symposium on Advanced Database Systems - Online Streaming (Virtual, Online)
Duration: 21.06.202024.06.2020
Conference number: 162162

Conference

Conference28th Italian Symposium on Advanced Database Systems
Abbreviated titleSEBD 2020
Period21.06.2024.06.20

Research Areas and Centers

  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)
  • Research Area: Intelligent Systems

DFG Research Classification Scheme

  • 409-04 Operating, Communication, Database and Distributed Systems

Fingerprint

Dive into the research topics of 'Parallelizing Approximate Search on Adaptive Radix Trees'. Together they form a unique fingerprint.

Cite this