Distributed Adaptive Radix Tree for Efficient Metadata Search on HPC Systems

Authors: Wei Zhang (Texas Tech University), Houjun Tang (Lawrence Berkeley National Laboratory), Suren Byna (Lawrence Berkeley National Laboratory), Yong Chen (Texas Tech University)

Abstract: Affix-based search allows users to retrieve data without the need to remember all relevant information precisely. While building an inverted index to facilitate efficient affix-based search is a common practice for standalone databases and desktop file systems, they are often insufficient for high-performance computing (HPC) systems due to the massive amount of data and the distributed nature of the storage. In this poster, we present Distributed Adaptive Radix Tree (DART) which enables scalable and efficient affix-based search. DART maintains a balanced keyword distribution and optimizes for excessive keyword requests dynamically at scale. Our evaluation shows that compared with the “full string hashing” used by the commonly adopted DHT approach, DART achieves up to 55x throughput speedup for prefix and suffix search, and has a comparable throughput for exact and infix search. Also, DART maintains balanced keyword distribution and alleviates excessive query workload on popular keywords.

Best Poster Finalist (BP): no

Poster: pdf
Poster summary: PDF


Back to Poster Archive Listing