Data structure lower bounds for document indexing problems

DOI10.4230/LIPICS.ICALP.2016.93MaRDI QIDQ4598234zbMATH OpenFDO

Authors Peyman Afshani, Jesper Sindahl Nielsen

Publication date 19 December 2017

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

zbMATH Keywords

data structurelower boundpattern matchingpointer machineset intersection

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Hardness of Several String Indexing Problems
• Forbidden patterns
• On hardness of several string indexing problems
• A linear lower bound on index size for text retrieval
• A linear lower bound on index size for text retrieval

Cited in

(9)

• scientific article; zbMATH DE number 7650989 (Why is no real title available?)
• Data Structures Lower Bounds and Popular Conjectures
• On hardness of several string indexing problems
• General space-time tradeoffs via relational queries
• Dynamic and internal longest common substring
• Ranked document retrieval for multiple patterns
• Towards optimal set-disjointness and set-intersection data structures
• Longest common extensions with wildcards: trade-off and applications
• Pattern masking for dictionary matching: theory and practice

This page was built for publication: Data structure lower bounds for document indexing problems

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