Fast set intersection and two-patterns matching

DOI10.1016/J.TCS.2010.06.002zbMATH Open1207.68270OpenAlexW2173123188MaRDI QIDQ708235FDOQ708235

Authors: Hagai Cohen, Ely Porat 

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

Recommendations

• Fast set intersection and two-patterns matching
• Combinatorial Pattern Matching
• Set intersection and sequence matching with mismatch counting
• Fast Evaluation of Union-Intersection Expressions
• On Hardness of Several String Indexing Problems

zbMATH Keywords

set intersectiontwo patterns

Mathematics Subject Classification ID

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

Cites Work

• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Title not available (Why is that?)
• Combinatorial Pattern Matching
• Title not available (Why is that?)
• Fast Evaluation of Union-Intersection Expressions
• Two-dimensional substring indexing.
• Title not available (Why is that?)

Cited In (24)

• Top-\(k\) document retrieval in optimal space
• Dynamic set intersection
• Fast Intersection Algorithms for Sorted Sequences
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• On hardness of several string indexing problems
• Mind the gap!
• Document retrieval with one wildcard
• Title not available (Why is that?)
• Longest common extensions in trees
• Longest common extensions in trees
• Set intersection and sequence matching with mismatch counting
• Space-efficient indexes for forbidden extension queries
• An efficient method to evaluate intersections on big data sets
• Fast Evaluation of Union-Intersection Expressions
• General space-time tradeoffs via relational queries
• Fast set intersection and two-patterns matching
• Ranked document retrieval for multiple patterns
• Indexes for document retrieval with relevance
• Space-efficient frameworks for top-\(k\) string retrieval
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Gapped indexing for consecutive occurrences
• Internal masked prefix sums and its connection to fully internal measurement queries
• Implementing the topological model succinctly
• Navigating planar topologies in near-optimal space and time

This page was built for publication: Fast set intersection and two-patterns matching

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