Fast prefix search in little space, with applications

DOI10.1007/978-3-642-15775-2_37zbMATH Open1287.68188arXiv1804.04720OpenAlexW1562034888MaRDI QIDQ3586483FDOQ3586483

Authors: Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna 

Publication date: 6 September 2010

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

Abstract: It has been shown in the indexing literature that there is an essential difference between prefix/range searches on the one hand, and predecessor/rank searches on the other hand, in that the former provably allows faster query resolution. Traditionally, prefix search is solved by data structures that are also dictionaries---they actually contain the strings in $S$. For very large collections stored in slow-access memory, we propose much more compact data structures that support emph{weak} prefix searches---they return the ranks of matching strings provided that emph{some} string in $S$ starts with the given prefix. In fact, we show that our most space-efficient data structure is asymptotically space-optimal. Previously, data structures such as String B-trees (and more complicated cache-oblivious string data structures) have implicitly supported weak prefix queries, but they all have query time that grows logarithmically with the size of the string collection. In contrast, our data structures are simple, naturally cache-efficient, and have query time that depends only on the length of the prefix, all the way down to constant query time for strings that fit in one machine word. We give several applications of weak prefix searches, including exact prefix counting and approximate counting of tuples matching conjunctive prefix conditions.

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

Recommendations

• On the weak prefix-search problem
• On the weak prefix-search problem
• c-trie++: a dynamic trie tailored for fast prefix searches
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Minimal indices for predecessor search

Mathematics Subject Classification ID

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

Cited In (23)

• On the weak prefix-search problem
• On the weak prefix-search problem
• Fast compressed self-indexes with deterministic linear-time construction
• Space-efficient substring occurrence estimation
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• Title not available (Why is that?)
• I/O-efficient data structures for colored range and prefix reporting
• Time-optimal top-\(k\) document retrieval
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• String Indexing with Compressed Patterns
• c-trie++: a dynamic trie tailored for fast prefix searches
• An encoding for order-preserving matching
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• Minimal indices for predecessor search
• Streaming Dictionary Matching with Mismatches
• All-pairs suffix/prefix in optimal time using Aho-Corasick space
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Fast prefix matching of bounded strings
• Linear-time computation of prefix table for weighted strings {\&} applications
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Universal compressed text indexing
• Space-efficient conversions from SLPs
• Minimal and monotone minimal perfect hash functions

This page was built for publication: Fast prefix search in little space, with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586483)