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

Simon Gog
Department of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Timo Beller
Institute for Theoretical Computer Science, Ulm University D-89069, Germany

Alistair Moffat
Department of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Matthias Petri
Department of Computing and Information Systems, The University of Melbourne, Victoria 3010, Australia.

Status

Proc. Symp. Experimental Algorithms, Copenhagen, June 2014, LNCS Volume 8504, pages 326-337.

Abstract

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.

Full text

http://dx.doi.org/10.1007/978-3-319-07959-2_28