On hardness of several string indexing problems

DOI10.1016/j.tcs.2015.03.026zbMath1310.68073OpenAlexW1982358125MaRDI QIDQ2342674

J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan, Kasper Green Larsen

Publication date: 29 April 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.026

zbMATH Keywords

data structureslower boundsdocument retrievalstring searchingBoolean matrix multiplication

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (4)

General space-time tradeoffs via relational queries ⋮ Gapped indexing for consecutive occurrences ⋮ Unnamed Item ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On space efficient two dimensional range minimum data structures
• Fast set intersection and two-patterns matching
• Two-dimensional substring indexing.
• Forbidden Patterns
• Document Listing for Queries with Excluded Pattern
• Sorted Range Reporting
• Linear-Space Data Structures for Range Minority Query in Arrays
• Space-Efficient Frameworks for Top- k String Retrieval
• Powers of tensors and fast matrix multiplication
• On dynamic range reporting in one dimension
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• On Hardness of Several String Indexing Problems
• Optimal static range reporting in one dimension
• Spaces, Trees, and Colors
• Orthogonal range searching on the RAM, revisited

This page was built for publication: On hardness of several string indexing problems