Gapped indexing for consecutive occurrences

DOI10.1007/s00453-022-01051-6OpenAlexW3183726873MaRDI QIDQ2696274

Philip Bille, Teresa Anna Steiner, Max Rishøj Pedersen, Inge Li Gørtz

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

string indexingtwo patternsconditional lower boundconsecutive occurrences

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Reporting consecutive substring occurrences under bounded gap constraints
• Top-\(k\) document retrieval in optimal space
• String matching with variable length gaps
• Substring range reporting
• Efficient index for retrieving top-\(k\) most frequent documents
• Fast set intersection and two-patterns matching
• Two-dimensional range successor in optimal time and almost linear space
• Discovering subword associations in strings in time linear in the output size
• Two-dimensional substring indexing.
• Ranked document retrieval for multiple patterns
• Log-logarithmic worst-case range queries are possible in space theta(N)
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• String indexing for patterns with wildcards
• Ranked document selection
• On hardness of several string indexing problems
• Top-\(k\) term-proximity in succinct space
• Indexing factors with gaps
• Conditional lower bounds for space/time tradeoffs
• Indexes for Document Retrieval with Relevance
• Top-k Document Retrieval in External Memory
• Sorted Range Reporting
• Time-Optimal Top-$k$ Document Retrieval
• The tree inclusion problem
• Space-Efficient Frameworks for Top- k String Retrieval
• Range Non-overlapping Indexing and Successive List Indexing
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Minimizing diameters of dynamic trees
• Higher Lower Bounds from the 3SUM Conjecture
• Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
• On Hardness of Jumbled Indexing
• Spaces, Trees, and Colors
• Color-Distance Oracles and Snippets
• Discovery Science
• Gapped indexing for consecutive occurrences

This page was built for publication: Gapped indexing for consecutive occurrences