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

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.

• Publication year

  2013

• Venue

  The Sea

• Publication date

  2013-11-05

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/978-3-319-07959-2_28arXiv 1311.1249
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimized succinct data structures for massive data

  2014cited by this paper
• String search experimentation using massive data

  2014cited by this paper
• Design of Practical Succinct Data Structures for Large Data Collections

  2013cited by this paper
• Faster Compact Top-k Document Retrieval

  2012influential reference
• Efficient in-memory top-k document retrieval

  2012cited by this paper
• Top-k document retrieval in optimal time and linear space

  2012cited by this paper
• Fast, Small, Simple Rank/Select on Bitmaps

  2012cited by this paper
• Inverted indexes for phrases and strings

  2011cited by this paper
• Practical Compressed Document Retrieval

  2011cited by this paper
• Top-k Ranked Document Search in General Text Databases

  2010cited by this paper
• Space-Efficient Framework for Top-k String Retrieval Problems

  2009cited by this paper
• Practical Rank/Select Queries over Arbitrary Sequences

  2008cited by this paper
• Broadword Implementation of Rank/Select Queries

  2008cited by this paper
• Compressed Suffix Trees with Full Functionality

  2007influential reference
• Faster suffix sorting

  2007influential reference
• Compressed text indexes: From theory to practice

  2007cited by this paper
• Practical Entropy-Compressed Rank/Select Dictionary

  2006cited by this paper
• Succinct Suffix Arrays based on Run-Length Encoding

  2005cited by this paper
• New text indexing functionalities of the compressed suffix arrays

  2003cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

  2002cited by this paper

• Adaptive encodings for small and fast compressed suffix arrays

  2026cites this paper
• Text Indexing and Pattern Matching with Ephemeral Edits

  2025cites this paper
• Worst-Case-Optimal Joins on Graphs with Topological Relations

  2025cites this paper
• Depth first representations of k2-trees

  2025cites this paper
• Efficient and accurate search in petabase-scale sequence repositories

  2025cites this paper
• FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT)

  2025cites this paper
• Engineering rank queries on bit vectors and strings

  2025cites this paper
• Elucidating Transitions of k-mer-Based Objects Across k-mer Sizes

  2025cites this paper
• Theory Meets Practice for Bit Vectors Supporting Rank and Select

  2025influential citation
• Wavelet Tree, Part I: A Brief History

  2025cites this paper
• Compressing Hypergraphs using Suffix Sorting

  2025cites this paper
• Heuristic-based computation of tailored spanning trees to speed up compact planar graphs

  2025cites this paper
• U-index: A Universal Indexing Framework for Matching Long Patterns

  2025cites this paper
• RLZ-r and LZ-End-r: Enhancing Move-r

  2025cites this paper
• Space-Efficient Lyndon Array Construction from Compressed Texts

  2025cites this paper
• Generating Multiple Alignments of Genomes of the Same Species

  2025cites this paper
• The Burrows-Wheeler transform of an elastic-degenerate string and its application to pattern matching

  2025cites this paper
• The TAG array of a multiple sequence alignment

  2025influential citation
• Scalable PBWT Queries with Minimum-Length SMEM Constraints

  2025cites this paper
• Minimum-Cost Synthetic Genome Planning: An Algorithmic Framework

  2025cites this paper
• Engineering Select Support for Hybrid Bitvectors

  2025influential citation
• Zombit: Exploiting Runs in Bitvectors

  2025cites this paper
• Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index

  2025cites this paper
• Haplotype Matching with GBWT for Pangenome Graphs

  2025cites this paper
• Digitalisation of MFIs with HCI Intervention for Low Income and Limited Literacy Individuals

  2024cites this paper
• Compressed Data Direct Computing for Databases

  2024cites this paper
• Worst-Case-Optimal Similarity Joins on Graph Databases

  2024cites this paper
• Toward Greener Matrix Operations by Lossless Compressed Formats

  2024cites this paper
• Adaptive Compression for Databases

  2024influential citation
• RetroLLM: Empowering Large Language Models to Retrieve Fine-grained Evidence within Generation

  2024cites this paper
• Prokrustean Graph: A substring index for rapid k-mer size analysis

  2024cites this paper
• Stronger compact representations of object trajectories

  2024cites this paper
• Centrifuger: lossless compression of microbial genomes for efficient and accurate metagenomic sequence classification

  2024cites this paper
• Pangenome graph layout by Path-Guided Stochastic Gradient Descent

  2024cites this paper
• The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space

  2024cites this paper
• PLA-index: A k-mer Index Exploiting Rank Curve Linearity

  2024cites this paper
• Improving Graph Compression for Efficient Resource-Constrained Graph Analytics

  2024cites this paper
• Space‐efficient data structures for the inference of subsumption and disjointness relations

  2024cites this paper
• Move-r: Optimizing the r-index

  2024cites this paper
• Succinct Opacity Micromaps

  2024cites this paper
• Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings

  2024cites this paper
• Computing LZ78-Derivates with Suffix Trees

  2024cites this paper
• Generate and Update Large HDT RDF Knowledge Graphs on Commodity Hardware

  2024cites this paper
• The Burrows-Wheeler Transform of an Elastic-Degenerate String

  2024cites this paper
• Pfp-fm: an accelerated FM-index

  2024influential citation
• Exploiting New Properties of String Net Frequency for Efficient Computation

  2024cites this paper
• PLA-complexity of k-mer multisets

  2024cites this paper
• Two-level massive string dictionaries

  2024cites this paper
• Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests

  2024cites this paper
• SPIDER: Improved Succinct Rank and Select Performance

  2024cites this paper
• Learned Compression of Nonlinear Time Series with Random Access

  2024cites this paper
• Text indexing for long patterns using locally consistent anchors

  2024cites this paper
• Phylogenetic tree distance computation over succinct representations

  2023influential citation
• Text Indexing for Long Patterns: Anchors are All you Need

  2023cites this paper
• Adapting Knowledge Graphs to Edge Computing Devices

  2023cites this paper
• Adding Descriptors to Melodies Improves Pattern Matching: A Study on Slovenian Folk Songs

  2023cites this paper
• CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression

  2023cites this paper
• CoCo-trie: Data-aware compression and indexing of strings

  2023cites this paper
• Pangenomic genotyping with the marker array

  2023cites this paper
• GIN-TONIC: non-hierarchical full-text indexing for graph genomes

  2023cites this paper
• Homomorphic Compression: Making Text Processing on Compression Unlimited

  2023cites this paper
• Rank and Select on Degenerate Strings

  2023cites this paper
• Faster Wavelet Tree Queries

  2023cites this paper
• Acceleration of FM-index Queries Through Prefix-free Parsing

  2023cites this paper
• Faster Block Tree Construction

  2023cites this paper
• Towards Autonomous Anomaly Management Using Semantic Technologies at the Edge

  2023cites this paper
• Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space

  2023cites this paper
• Another virtue of wavelet forests

  2023cites this paper
• Engineering a Textbook Approach to Index Massive String Dictionaries

  2023cites this paper
• Simple Runs-Bounded FM-Index Designs Are Fast

  2023cites this paper
• Exact and Approximate Range Mode Query Data Structures in Practice

  2023cites this paper
• Subset Wavelet Trees

  2023cites this paper
• Koala: An Index for Quantifying Overlaps with Pre-training Corpora

  2023cites this paper
• Compact representations of spatial hierarchical structures with support for topological queries

  2023influential citation
• μ-PBWT: Enabling the Storage and Use of UK Biobank Data on a Commodity Laptop

  2023cites this paper
• Learned Monotone Minimal Perfect Hashing

  2023cites this paper
• Bidirectional String Anchors for Improved Text Indexing and Top-$K$ Similarity Search

  2023cites this paper
• Accurate and fast graph-based pangenome annotation and clustering with ggCaller

  2023cites this paper
• Pangenome graph layout by Path-Guided Stochastic Gradient Descent

  2023cites this paper
• Building a Pangenome Alignment Index via Recursive Prefix-Free Parsing

  2023cites this paper
• Faster Wavelet Trees with Quad Vectors

  2023cites this paper
• Map algebra on raster datasets represented by compact data structures

  2023cites this paper
• Practical Implementations of Compressed RAM

  2023cites this paper
• Counting with Prediction: Rank and Select Queries with Adjusted Anchoring

  2022cites this paper
• On Dynamic Bitvector Implementations*

  2022influential citation
• CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases

  2022cites this paper
• Prefix-free parsing for building large tunnelled Wheeler graphs

  2022cites this paper
• Speeding up compact planar graphs by using shallower trees

  2022cites this paper
• CSTs for Terabyte-Sized Data

  2022cites this paper
• Practical Implementation of Encoding Range Top-2 Queries

  2022cites this paper
• GBZ File Format for Pangenome Graphs

  2022cites this paper
• Pangenomic Genotyping with the Marker Array

  2022cites this paper
• Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors

  2022cites this paper
• Efficient Construction of the BWT for Repetitive Text Using String Compression

  2022cites this paper
• Improved sequence mapping using a complete reference genome and lift-over

  2022cites this paper
• Finding Maximal Exact Matches Using the r-Index

  2022cites this paper
• Genome-wide CRISPR guide RNA design and specificity analysis with GuideScan2

  2022cites this paper
• Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices

  2022cites this paper
• PaCHash: Packed and Compressed Hash Tables

  2022cites this paper
• A Learned Approach to Design Compressed Rank/Select Data Structures

  2022cites this paper