Pattern matching in multiple streams

Raphael Clifford, Markus T Jalsenius, Porat Ely, Benjamin G Sach

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)

Abstract

We investigate the problem of 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 matching upper and deterministic space lower bounds for three distinct pattern matching problems. For exact matching we show that the space complexity is $Theta(m + s) words and that new matches can be reported in worst case constant time. For the k-mismatch and k-differences problems we show that the space complexity is Theta(m+ks) and that both problems can be solved in O(k) time per new symbol. Finally we set out a number of open problems related to this new model for pattern matching.
Original languageEnglish
Title of host publicationCPM 2012
Pages97-109
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Pattern matching in multiple streams'. Together they form a unique fingerprint.

Cite this