Grossi, Roberto ;
Menconi, Giulia ;
Pisanti, Nadia ;
Trani, Roberto ;
Vind, Soren
OutputSensitive 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). Outputsensitive 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 outputsensitivity, 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 = {{OutputSensitive Pattern Extraction in Sequences}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {303314},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4851},
URN = {urn:nbn:de:0030drops48513},
doi = {10.4230/LIPIcs.FSTTCS.2014.303},
annote = {Keywords: Pattern Extraction, Motif Detection, Pattern Discovery, Motif Trie}
}
2014
Keywords: 

Pattern Extraction, Motif Detection, Pattern Discovery, Motif Trie 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 