License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.303
URN: urn:nbn:de:0030-drops-48513
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4851/
Grossi, Roberto ;
Menconi, Giulia ;
Pisanti, Nadia ;
Trani, Roberto ;
Vind, Soren
Output-Sensitive Pattern Extraction in Sequences
Abstract
Genomic Analysis, Plagiarism Detection, Data Mining, Intrusion Detection, Spam Fighting and Time Series Analysis are just some examples of applications where extraction of recurring patterns in sequences of objects is one of the main computational challenges. Several notions of patterns exist, and many share the common idea of strictly specifying some parts of the pattern and to don't care about the remaining parts. Since the number of patterns can be exponential in the length of the sequences, pattern extraction focuses on statistically relevant patterns, where any attempt to further refine or extend them causes a loss of significant information (where the number of occurrences changes). Output-sensitive algorithms have been proposed to enumerate and list these patterns, taking polynomial time O(n^c) per pattern for constant c > 1, which is impractical for massive sequences of very large length n.
We address the problem of extracting maximal patterns with at most k don't care symbols and at least q occurrences. Our contribution is to give the first algorithm that attains a stronger notion of output-sensitivity, borrowed from the analysis of data structures: the cost is proportional to the actual number of occurrences of each pattern, which is at most n and practically much smaller than n in real applications, thus avoiding the aforementioned cost of O(n^c) per pattern.
BibTeX - Entry
@InProceedings{grossi_et_al:LIPIcs:2014:4851,
author = {Roberto Grossi and Giulia Menconi and Nadia Pisanti and Roberto Trani and Soren Vind},
title = {{Output-Sensitive Pattern Extraction in Sequences}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {303--314},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4851},
URN = {urn:nbn:de:0030-drops-48513},
doi = {10.4230/LIPIcs.FSTTCS.2014.303},
annote = {Keywords: Pattern Extraction, Motif Detection, Pattern Discovery, Motif Trie}
}
|
Keywords: |
|
Pattern Extraction, Motif Detection, Pattern Discovery, Motif Trie |
|
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
12.12.2014 |
