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

2013/11/05 by Gog, Simon, Beller, Timo, Moffat, Alistair +1 · 8 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1311.1249

Abstract

Engineering efficient implementations of compact and succinct structures is a time-consuming and challenging task, 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 a difficult task, since older base- line implementations may not rely on the same basic components, and reimplementing from scratch can be very 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 succinct solutions for document retrieval.

Cited by

• The TAG array of a multiple sequence alignment
• FroM Superstring to Indexing: a space-efficient index for unconstrained k -mer sets using the Masked Burrows-Wheeler Transform (MBWT)
• Theory Meets Practice for Bit Vectors Supporting Rank and Select
• Engineering Select Support for Hybrid Bitvectors
• Minimum-Cost Synthetic Genome Planning: An Algorithmic Framework
• jXBW: A Compressed Index for Structure-Aware JSONL Retrieval in Structured RAG
• Text Indexing and Pattern Matching with Ephemeral Edits
• RLZ-r and LZ-End-r: Enhancing Move-r

Related

• AnnoRetrieve: Efficient Structured Retrieval for Unstructured Document Analysis
• Trove: A Flexible Toolkit for Dense Retrieval
• SPIRE: Structure-Preserving Interpretable Retrieval of Evidence
• UDA: A Benchmark Suite for Retrieval Augmented Generation in Real-world Document Analysis
• Document Retrieval on Repetitive Collections