Cover Image

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nishimoto, Takaaki, Tabei, Yasuo
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Suffix Array in Optimal Compressed Space
by: Nishimoto, Takaaki, et al.
Published: (2024)

Dynamic r-index: An Updatable Self-Index in LCP-bounded Time
by: Nishimoto, Takaaki, et al.
Published: (2025)

jXBW: Fast Substructure Search for Large-Scale JSONL Datasets with LLM Applications
by: Tabei, Yasuo
Published: (2025)

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Compressed Index with Construction in Compressed Space
by: Kosolobov, Dmitry
Published: (2026)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
by: Duyster, Anouk, et al.
Published: (2026)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
by: Kosolobov, Dmitry, et al.
Published: (2021)

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

Towards Optimal Grammars for RNA Structures
by: Onokpasa, Evarista, et al.
Published: (2024)

LZ78 Substring Compression in Compressed Space
by: Shibata, Hiroki, et al.
Published: (2025)

Counting on General Run-Length Grammars
by: Navarro, Gonzalo, et al.
Published: (2024)

Space-Efficient k-Mismatch Text Indexes
by: Kociumaka, Tomasz, et al.
Published: (2025)

Indexing Tries within Entropy-Bounded Space
by: Carfagna, Lorenzo, et al.
Published: (2025)

Improved Time-Space Tradeoffs for 3SUM-Indexing
by: Dinur, Itai, et al.
Published: (2025)

Optimal-Time Mapping in Run-Length Compressed PBWT
by: Bonizzoni, Paola, et al.
Published: (2026)

Space-Efficient Text Indexing with Mismatches using Function Inversion
by: Bibbens, Jackson, et al.
Published: (2026)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation
by: Sun, Shengli, et al.
Published: (2025)

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions
by: Ramos, David Torres, et al.
Published: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Space-Efficient Indexes for Uncertain Strings
by: Gabory, Esteban, et al.
Published: (2024)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
by: Adudodla, Ankith Reddy, et al.
Published: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

NP-Completeness for the Space-Optimality of Double-Array Tries
by: Bannai, Hideo, et al.
Published: (2024)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
by: Domingues, Gabriel Marques
Published: (2026)

A Dynamic Working Set Method for Compressed Sensing
by: Cheng, Siu-Wing, et al.
Published: (2025)

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
by: Joshi, Amit
Published: (2025)

Implementation Of Dynamic De Bruijn Graphs Via Learned Index
by: Nigrelli, Riccardo
Published: (2024)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Parallel Dynamic Spatial Indexes
by: Men, Ziyang, et al.
Published: (2026)

Deterministic Retrieval at Scale: Optimal-Space LCP Indexing and 308x Energy Reduction on Modern GPUs
by: Byriukov, Stanislav
Published: (2026)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
by: Duyster, Anouk, et al.
Published: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)