Dictionary matching in a stream

Raphael Clifford; Allyx Fontaine; Ely Porat; Benjamin Sach; Tatiana Starikovskaya

doi:10.1007/978-3-662-48350-3_31

Dictionary matching in a stream

Raphael Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya

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

34 Citations (Scopus)

355 Downloads (Pure)

Abstract

We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.

Original language	English
Title of host publication	Algorithms – ESA 2015
Subtitle of host publication	23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings
Publisher	Springer Verlag
Pages	361-372
ISBN (Electronic)	9783662483503
ISBN (Print)	9783662483497
DOIs	https://doi.org/10.1007/978-3-662-48350-3_31
Publication status	Published - Jul 2015
Event	European Symposium on Algorithms - , United Kingdom Duration: 14 Sept 2015 → …

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9294
ISSN (Print)	0302-9743

Conference

Conference	European Symposium on Algorithms
Country/Territory	United Kingdom
Period	14/09/15 → …

Bibliographical note

The paper was initially rejected due to an oversight by the Program Committee. Two papers were submitted on the same topic but were not directly compared. After we enquired, the PC compared our paper to the other and decided that we both should have been accepted.

Keywords

cs.DS

Access to Document

10.1007/978-3-662-48350-3_31

pdfAccepted author manuscript, 177 KB

Handle.net

Persistent link

Next generation pattern matching
Clifford, R. (Principal Investigator)
1/01/13 → 14/01/19
Project: Research

Dr Raphael Clifford
- Raphael.Cliffordbristol.acuk
- School of Computer Science - Reader in Algorithm Design
- Intelligent Systems Laboratory
- Algorithms and Complexity
Person: Academic , Member, Group lead

Cite this

@inproceedings{e08bd3eda4be4517a57254c088f6f6bd,

title = "Dictionary matching in a stream",

abstract = "We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.",

keywords = "cs.DS",

author = "Raphael Clifford and Allyx Fontaine and Ely Porat and Benjamin Sach and Tatiana Starikovskaya",

note = "The paper was initially rejected due to an oversight by the Program Committee. Two papers were submitted on the same topic but were not directly compared. After we enquired, the PC compared our paper to the other and decided that we both should have been accepted.; European Symposium on Algorithms ; Conference date: 14-09-2015",

year = "2015",

month = jul,

doi = "10.1007/978-3-662-48350-3_31",

language = "English",

isbn = "9783662483497",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "361--372",

booktitle = "Algorithms – ESA 2015",

address = "Germany",

}

Clifford, R, Fontaine, A, Porat, E, Sach, B & Starikovskaya, T 2015, Dictionary matching in a stream. in Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9294, Springer Verlag, pp. 361-372, European Symposium on Algorithms, United Kingdom, 14/09/15. https://doi.org/10.1007/978-3-662-48350-3_31

Dictionary matching in a stream. / Clifford, Raphael; Fontaine, Allyx; Porat, Ely et al.
Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. Springer Verlag, 2015. p. 361-372 (Lecture Notes in Computer Science; Vol. 9294).

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

TY - GEN

T1 - Dictionary matching in a stream

AU - Clifford, Raphael

AU - Fontaine, Allyx

AU - Porat, Ely

AU - Sach, Benjamin

AU - Starikovskaya, Tatiana

N1 - The paper was initially rejected due to an oversight by the Program Committee. Two papers were submitted on the same topic but were not directly compared. After we enquired, the PC compared our paper to the other and decided that we both should have been accepted.

PY - 2015/7

Y1 - 2015/7

N2 - We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.

AB - We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.

KW - cs.DS

U2 - 10.1007/978-3-662-48350-3_31

DO - 10.1007/978-3-662-48350-3_31

M3 - Conference Contribution (Conference Proceeding)

SN - 9783662483497

T3 - Lecture Notes in Computer Science

SP - 361

EP - 372

BT - Algorithms – ESA 2015

PB - Springer Verlag

T2 - European Symposium on Algorithms

Y2 - 14 September 2015

ER -

Dictionary matching in a stream

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Projects

Next generation pattern matching

Profiles

Dr Raphael Clifford

Cite this