2015 · 50 citations · 23 references
Life SciencesBioinformaticsData MiningGenomic Data AnalysisSequence AnalysisMotif DiscoverySequence MiningExperimental Study DesignMotif DetectionPruningSequence Motif Discovery
Discovering motifs in sequence databases has been receiving abundant attentions from both database and data mining communities, where the motif is the most correlated pair of subsequences in a sequence object. Motif discovery is expensive for emerging applications which may have very long sequences (e.g., million observations per sequence) or the queries arrive rapidly (e.g., per 10 seconds). Prior works cannot offer fast correlation computations and prune subsequence pairs at the same time, as these two techniques require different orderings on examining subsequence pairs. In this work, we propose a novel framework named Quick-Motif which adopts a two-level approach to enable batch pruning at the outer level and enable fast correlation calculation at the inner level. We further propose two optimization techniques for the outer and the inner level. In our experimental study, our method is up to 3 orders of magnitude faster than the state-of-the-art methods.
23
Experiencing SAX: a novel symbolic representation of time series
Jessica Lin, Eamonn Keogh, Wei Li et al. · Data Mining and Knowledge Discovery · 2007 · 1.6K citations
Computing, Data Science, Mathematics +12
Probabilistic discovery of time series motifs
Bill Chiu, Eamonn Keogh, Stefano Lonardi · 2003 · 571 citations