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(nc) 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(nc) per pattern.
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(nc) per pattern.
Original language | English |
---|---|
Title of host publication | Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany |
Publication date | 2014 |
Pages | 303-314 |
ISBN (Print) | 978-3-939897-77-4 |
DOIs | |
Publication status | Published - 2014 |
Event | 34th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014) - India International Centre, New Delhi, India Duration: 15 Dec 2014 → 17 Dec 2014 Conference number: 34 http://www.fsttcs.org/index.php |
Conference
Conference | 34th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
---|---|
Number | 34 |
Location | India International Centre |
Country/Territory | India |
City | New Delhi |
Period | 15/12/2014 → 17/12/2014 |
Internet address |
Series | Leibniz International Proceedings in Informatics |
---|---|
Volume | 29 |
ISSN | 1868-8969 |
Bibliographical note
Will be published Open Access in the Leibniz International Proceedings in Informatics (LIPIcs)Keywords
- Pattern Extraction
- Motif Detection
- Pattern Discovery
- Motif Trie