Fast Prefix Search in Little Space, with Applications

DOI10.1007/978-3-642-15775-2_37zbMath1287.68188arXiv1804.04720OpenAlexW1562034888MaRDI QIDQ3586483

Paolo Boldi, Rasmus Pagh, Sebastiano Vigna, Djamal Belazzougui

Publication date: 6 September 2010

Published in: Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.04720

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (17)

Minimal and Monotone Minimal Perfect Hash Functions ⋮ On the weak prefix-search problem ⋮ String Indexing with Compressed Patterns ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Universal compressed text indexing ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ On the Weak Prefix-Search Problem ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ Minimal indices for predecessor search ⋮ Streaming Dictionary Matching with Mismatches ⋮ Fast scalable construction of ([compressed static | minimal perfect hash) functions] ⋮ An Encoding for Order-Preserving Matching. ⋮ Unnamed Item ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction ⋮ Space-efficient substring occurrence estimation

This page was built for publication: Fast Prefix Search in Little Space, with Applications