Motif trie: An efficient text index for pattern discovery with don't cares

Roberto Grossi*, Giulia Menconi, Nadia Pisanti, Roberto Trani, Søren Juhl Vind

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

23 Downloads (Pure)

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.
Original languageEnglish
JournalTheoretical Computer Science
Volume710
Pages (from-to)74-87
ISSN0304-3975
DOIs
Publication statusPublished - 2017

Keywords

  • Theoretical Computer Science
  • Computer Science (all)
  • Data structures
  • Maximal intervals
  • Motifs
  • Pattern discovery
  • Tries and suffix trees
  • Intrusion detection
  • Pattern matching
  • Time series analysis
  • Trees (mathematics)
  • Computational bottlenecks
  • Genomic analysis
  • Plagiarism detection
  • Suffix-trees
  • Trie data structures
  • Data mining

Fingerprint Dive into the research topics of 'Motif trie: An efficient text index for pattern discovery with don't cares'. Together they form a unique fingerprint.

Cite this