Pattern matching in multiple streams

DOI10.1007/978-3-642-31265-6_8zbMATH Open1358.68335arXiv1202.3470OpenAlexW1648259537MaRDI QIDQ2904482FDOQ2904482

Authors: Raphaël Clifford, Markus Jalsenius, Ely Porat, Benjamin Sach 

Publication date: 14 August 2012

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: We investigate the problem of deterministic pattern matching in multiple streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The task at each time step is to report if there is a new match between a fixed pattern of length m and a newly updated stream. As is usual in the streaming context, the goal is to use as little space as possible while still reporting matches quickly. We give almost matching upper and lower space bounds for three distinct pattern matching problems. For exact matching we show that the problem can be solved in constant time per arriving symbol and O(m+s) words of space. For the k-mismatch and k-difference problems we give O(k) time solutions that require O(m+ks) words of space. In all three cases we also give space lower bounds which show our methods are optimal up to a single logarithmic factor. Finally we set out a number of open problems related to this new model for pattern matching.

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

Recommendations

• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• The streaming \(k\)-mismatch problem
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• The \(k\)-mismatch problem revisited
• scientific article

Mathematics Subject Classification ID

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

Cited In (13)

• Multiple matching of parameterized patterns
• Asynchronous Pattern Matching
• Pseudo-realtime pattern matching: closing the gap
• Dictionary matching in a stream
• The streaming \(k\)-mismatch problem
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Online stochastic pattern matching
• Real-time streaming string-matching
• Streaming pattern matching with \(d\) wildcards
• \(k\)-difference matching in amortized linear time for all the words in a text
• Fingerprints for highly similar streams
• Streaming Pattern Matching with d Wildcards
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Pattern matching in multiple streams

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