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) per pattern, for constant c > 1, which is otherwise impractical for massive sequences with large n.

Motif Trie: An Efficient Text Index for Pattern Discovery with Don't Cares

GROSSI, ROBERTO;PISANTI, NADIA
;
TRANI, ROBERTO;
2018-01-01

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) per pattern, for constant c > 1, which is otherwise impractical for massive sequences with large n.
2018
Grossi, Roberto; G., Menconi; Pisanti, Nadia; Trani, Roberto; S., Vind
File in questo prodotto:
File Dimensione Formato  
revised.pdf

Open Access dal 01/03/2020

Tipologia: Documento in Pre-print
Licenza: Importato da Ugov Ricerca - Accesso privato/ristretto
Dimensione 643.95 kB
Formato Adobe PDF
643.95 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/852514
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 1
social impact