From Theory to Practice: Plug and Play with Succinct Data Structures

By Simon Gog, Timo Beller, Alistair Moffat, Matthias Petri. The Sea, 2013

422 citations recorded by the source corpus.

Engineering efficient implementations of compact and succinct structures is time-consuming and challenging, since there is no standard library of easy-to-use, highly optimized, and composable components. One consequence is that measuring the practical impact of new theoretical proposals is difficult, since older baseline implementations may not rely on the same basic components, and reimplementing from scratch can be time-consuming. In this paper we present a framework for experimentation with succinct data structures, providing a large set of configurable components, together with tests, benchmarks, and tools to analyze resource requirements. We demonstrate the functionality of the framework by recomposing two succinct solutions for top-k document retrieval which can operate on both character and integer alphabets.

Subfields: Artificial Intelligence, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/de7a529d144f0a78dd75864dd6012f969521f7f8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

Citations in the corpus

Variation graph toolkit improves read mapping by representing genetic variation in the reference (2018, positive): “…and other random access operations against large sequence graphs we have implemented a succinct representation of a vg variation graph (xg) that is static but very memory and time efficient, using rank/select dictionaries and other data structures from the Succinct Data Structures Library (SDSL)30.”
Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction (2016, background): “Table 2 compares the 32-core running time of our algorithms ddWT and recursiveWT to the parallel levelWT implementation, the serial serWT implementation from [4] and the SDSL implementation sdslWT, and Table 3 compares their memory consumption.”