Fast set intersection and two-patterns matching

DOI10.1016/j.tcs.2010.06.002zbMath1207.68270OpenAlexW2173123188MaRDI QIDQ708235

Ely Porat, Hagai Cohen

Publication date: 11 October 2010

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

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

zbMATH Keywords

set intersectiontwo patterns

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Pattern recognition, speech recognition (68T10) Information storage and retrieval of data (68P20)

Related Items

Document retrieval with one wildcard ⋮ Longest common extensions in trees ⋮ Dynamic Set Intersection ⋮ Space-efficient indexes for forbidden extension queries ⋮ An efficient method to evaluate intersections on big data sets ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Longest Common Extensions in Trees ⋮ Mind the gap! ⋮ Top-\(k\) document retrieval in optimal space ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ General space-time tradeoffs via relational queries ⋮ Gapped indexing for consecutive occurrences ⋮ Spaces, Trees, and Colors ⋮ Unnamed Item ⋮ Ranked document retrieval for multiple patterns ⋮ Indexes for Document Retrieval with Relevance ⋮ Navigating planar topologies in near-optimal space and time ⋮ On hardness of several string indexing problems ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two-dimensional substring indexing.
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Combinatorial Pattern Matching
• Fast Evaluation of Union-Intersection Expressions