1 Search Results for "Menconi, Giulia"


Document
Output-Sensitive Pattern Extraction in Sequences

Authors: Roberto Grossi, Giulia Menconi, Nadia Pisanti, Roberto Trani, and Soren Vind

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)


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(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 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(n^c) per pattern.

Cite as

Roberto Grossi, Giulia Menconi, Nadia Pisanti, Roberto Trani, and Soren Vind. Output-Sensitive Pattern Extraction in Sequences. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 303-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{grossi_et_al:LIPIcs.FSTTCS.2014.303,
  author =	{Grossi, Roberto and Menconi, Giulia and Pisanti, Nadia and Trani, Roberto and Vind, Soren},
  title =	{{Output-Sensitive Pattern Extraction in Sequences}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{303--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.303},
  URN =		{urn:nbn:de:0030-drops-48513},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.303},
  annote =	{Keywords: Pattern Extraction, Motif Detection, Pattern Discovery, Motif Trie}
}
  • Refine by Author
  • 1 Grossi, Roberto
  • 1 Menconi, Giulia
  • 1 Pisanti, Nadia
  • 1 Trani, Roberto
  • 1 Vind, Soren

  • Refine by Classification

  • Refine by Keyword
  • 1 Motif Detection
  • 1 Motif Trie
  • 1 Pattern Discovery
  • 1 Pattern Extraction

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail