The case for hybrid succinct data structures

Christoph Anneser, Andreas Kipf, Harald Lang, Thomas Neumann, Alfons Kemper

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

3 Scopus citations


One of the biggest challenges in data management is to retain the high performance of in-memory processing with the ever increasing data volumes. Recent years have shown that the amount of collected data is increasing at a faster pace than DRAM capacities. Many state-of-the-art index data structures are optimized for performance rather than for low space consumption and quickly exceed the limited main-memory capacities when indexing larger data sets. Succinct data structures on the other hand allow for space efficient indexing, but compromise performance while still being orders of magnitude faster than disk-based data structures. In this work, we propose a novel framework that combines state-of-the-art indexes with succinct data structures to form new hybrid succinct data structures. These hybrids enable fine-grained trade-offs between space and performance. Frequently accessed parts of an index, e.g. the upper levels of a tree, are thereby maintained in performance-optimized structures whereas less frequently accessed parts have a space-optimized representation. Our evaluation shows that our approach can significantly reduce the amount of used space by up to 50% (resp. 90% for our compressed version) while retaining 93% (resp. 87%) of the performance.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2020
Subtitle of host publication23rd International Conference on Extending Database Technology, Proceedings
EditorsAngela Bonifati, Yongluan Zhou, Marcos Antonio Vaz Salles, Alexander Bohm, Dan Olteanu, George Fletcher, Arijit Khan, Bin Yang
Number of pages4
ISBN (Electronic)9783893180837
StatePublished - 2020
Event23rd International Conference on Extending Database Technology, EDBT 2020 - Copenhagen, Denmark
Duration: 30 Mar 20202 Apr 2020

Publication series

NameAdvances in Database Technology - EDBT
ISSN (Electronic)2367-2005


Conference23rd International Conference on Extending Database Technology, EDBT 2020


Dive into the research topics of 'The case for hybrid succinct data structures'. Together they form a unique fingerprint.

Cite this