Fast Output-Sensitive Pattern Discovery in Massive Sequences using the Motif Trie

Abstract : We introduce the motif trie data structure, which has applications in pattern matching and discovery in genomic analysis, plagiarism detection, data mining, intrusion detection, spam fighting and time series analysis, to name a few. Here the extraction of recurring patterns in sequential and textual data is one of the main computational bottlenecks. For this, we address the problem of extracting maximal patterns with at most k don't care symbols and at least q occurrences, according to a maximality notion we define. We apply the motif trie to this problem, also showing how to build it efficiently. As a result, we give the first algorithm that attains a stronger notion of output-sensitivity, where the cost for an input sequence of n symbols is proportional to the actual number of occurrences of each pattern, which is at most n (much smaller in practice). This avoids the best-known cost of O(nc)O(nc) per pattern, for constant c>1c>1, which is otherwise impractical for massive sequences with large n.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017, pp.25. 〈10.1016/j.tcs.2017.04.012〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01525745
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 24 mai 2017 - 11:11:15
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : lundi 28 août 2017 - 16:41:14

Fichier

Auth-TCS17.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Roberto Grossi, Giulia Menconi, Nadia Pisanti, Roberto Trani, Søren Vind. Fast Output-Sensitive Pattern Discovery in Massive Sequences using the Motif Trie. Theoretical Computer Science, Elsevier, 2017, pp.25. 〈10.1016/j.tcs.2017.04.012〉. 〈hal-01525745〉

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

77