The Library
Pattern matching in multiple streams
Tools
Tools
Tools
Clifford, Raphaël, Jalsenius, Markus, Porat, Ely and Sach, Ben (2012) Pattern matching in multiple streams. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 7354 . pp. 97-109. doi:10.1007/978-3-642-31265-6_8 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-31265-6_8
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. © 2012 Springer-Verlag.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Combinatorial Pattern Matching | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Volume 7354 | ||||
| Page Range: | pp. 97-109 | ||||
| DOI: | 10.1007/978-3-642-31265-6_8 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
