Fast set intersection and two-patterns matching

DOI10.1016/J.TCS.2010.06.002MaRDI QIDQ708235zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

set intersectiontwo patterns

Mathematics Subject Classification ID

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

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

Cites work

• Combinatorial Pattern Matching
• Fast Evaluation of Union-Intersection Expressions
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 1445338 (Why is no real title available?)
• scientific article; zbMATH DE number 1445373 (Why is no real title available?)
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Two-dimensional substring indexing.

Cited in

(25)

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

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)