Dictionary matching in a stream

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

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

25 Citations (Scopus)
311 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 languageEnglish
Title of host publicationAlgorithms – ESA 2015
Subtitle of host publication23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings
PublisherSpringer Verlag
Pages361-372
ISBN (Electronic)9783662483503
ISBN (Print)9783662483497
DOIs
Publication statusPublished - Jul 2015
EventEuropean Symposium on Algorithms - , United Kingdom
Duration: 14 Sep 2015 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9294
ISSN (Print)0302-9743

Conference

ConferenceEuropean Symposium on Algorithms
CountryUnited Kingdom
Period14/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

Fingerprint Dive into the research topics of 'Dictionary matching in a stream'. Together they form a unique fingerprint.

Cite this