Real-Time Streaming Multi-Pattern Search for Constant Alphabet

DOI10.4230/LIPICS.ESA.2017.41MaRDI QIDQ5111729zbMATH OpenOpenAlexFDO

Authors Shay Golan, Ely Porat

Publication date 27 May 2020

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2017/7855/pdf/LIPIcs-ESA-2017-41.pdf/

zbMATH Keywords

fingerprintsdictionary matchingstreaming pattern matchingmulti-pattern search

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Recommendations

• Real-time streaming string-matching
• Real-time streaming string-matching
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• CSA++: Fast Pattern Search for Large Alphabets
• Simple real-time constant-space string matching
• Simple real-time constant-space string matching

Cites work

• scientific article; zbMATH DE number 6678937 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• A framework for dynamic parameterized dictionary matching
• Addendum to: ``Exponential time improvement for min-wise based algorithms
• An Efficient TCAM-Based Implementation of Multipattern Matching Using Covered State Encoding
• An improved query time for succinct dynamic dictionary matching
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Constructing Efficient Dictionaries in Close to Sorting Time
• Data streams: algorithms and applications.
• Deterministic dictionaries
• Dictionary matching in a stream
• Dictionary matching with a few gaps
• Dictionary matching with one gap
• Efficient string matching
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast circular dictionary-matching algorithm
• Fast moment estimation in data streams in optimal space
• GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU
• Mind the gap: essentially optimal algorithms for online dictionary matching with one gap
• Periodicity in streams
• Real-time streaming string-matching
• Simple real-time constant-space string matching
• Space-efficient dictionaries for parameterized and order-preserving pattern matching
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Streaming Pattern Matching with d Wildcards
• Succinct online dictionary matching with improved worst-case guarantees
• The \(k\)-mismatch problem revisited
• The space complexity of approximating the frequency moments
• Theory and practice of monotone minimal perfect hashing

Cited in

(14)

• Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
• Online stochastic pattern matching
• Real-time streaming string-matching
• Streaming dictionary matching with mismatches
• Pattern matching in multiple streams
• Real-time streaming string-matching
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Streaming pattern matching with \(d\) wildcards
• Compressed Multiple Pattern Matching
• Searching Long Repeats in Streams
• Streaming Dictionary Matching with Mismatches
• Streaming \(k\)-mismatch with error correcting and applications
• Dictionary matching in a stream
• CSA++: Fast Pattern Search for Large Alphabets

This page was built for publication: Real-Time Streaming Multi-Pattern Search for Constant Alphabet

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