Rare Time Series Motif Discovery from Unbounded Streams

The detection of time series motifs, which are approximately repeated subsequences in time series streams, has been shown to have great utility as a subroutine in many higher-level data mining algorithms. However, this detection becomes much harder in cases where the motifs of interest are vanishingly rare or when faced with a never-ending stream of data. In this work we investigate algorithms to find such rare motifs. We demonstrate that under reasonable assumptions we must abandon any hope of an exact solution to the motif problem as it is normally defined; however, we introduce algorithms that allow us to solve the underlying problem with high probability.

• Publication year

  2014

• Venue

  Proceedings of the VLDB Endowment

• Publication date

  2014-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.14778/2735471.2735476
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Towards never-ending learning from time series streams

  2013influential reference
• Enumeration of time series motifs of all lengths

  2013influential reference
• AMPds: A public dataset for load disaggregation and eco-feedback research

  2013cited by this paper
• Fast repetition detection in TV streams using duration patterns

  2013cited by this paper
• Significant motifs in time series

  2012cited by this paper
• A dictionary of behavioral motifs reveals clusters of genes affecting Caenorhabditis elegans locomotion

  2012cited by this paper
• A disk-aware algorithm for time series motif discovery

  2011influential reference
• Methods for finding frequent items in data streams

  2010influential reference
• Mining top-K frequent itemsets through progressive sampling

  2010cited by this paper
• Experimental comparison of representation methods and distance measures for time series data

  2010cited by this paper
• Online discovery and maintenance of time series motifs

  2010influential reference
• Toward Unsupervised Activity Discovery Using Multi-Dimensional Motif Detection in Time Series

  2009cited by this paper
• SensorScope: Out-of-the-Box Environmental Monitoring

  2008cited by this paper
• Experiencing SAX: a novel symbolic representation of time series

  2007cited by this paper
• Automated Wildlife Monitoring Using Self-Configuring Sensor Networks Deployed in Natural Habitats

  2007cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005cited by this paper
• Instability of FIFO at arbitrarily low rates in the adversarial queuing model

  2003cited by this paper
• Probabilistic discovery of time series motifs

  2003cited by this paper
• On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration

  2002cited by this paper
• Efficient indexing structures for mining frequent patterns

  2002cited by this paper
• Finding Motifs in Time Series

  2002cited by this paper
• Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

  2001cited by this paper
• Efficient time series matching by wavelets

  1999cited by this paper
• Novelty detection in time series data using ideas from immunology

  1996cited by this paper
• Efficient Similarity Search In Sequence Databases

  1993cited by this paper
• Instruction Cache Replacement Policies and Organizations

  1985cited by this paper
• Space/time trade-offs in hash coding with allowable errors

  1970cited by this paper
• Error detecting and error correcting codes

  1950cited by this paper

• Efficient Generalized Temporal Pattern Mining in Time Series Using Mutual Information

  2025cites this paper
• Time-Series Clustering: A Comprehensive Study of Data Mining, Machine Learning, and Deep Learning Methods

  2025cites this paper
• A Structured Study of Multivariate Time-Series Distance Measures

  2025cites this paper
• A survey of multimodal event detection based on data fusion

  2024cites this paper
• Efficient Rare Temporal Pattern Mining in Time Series

  2024cites this paper
• TWStream: Three-Way Stream Clustering

  2024cites this paper
• Rare Category Analysis for Complex Data: A Review

  2023cites this paper
• Novelets: a new primitive that allows online detection of emerging behaviors in time series

  2023cites this paper
• Efficient Generalized Temporal Pattern Mining in Big Time Series Using Mutual Information

  2023cites this paper
• Exploring the Lived Experience of Behavior Change Technologies: Towards an Existential Model of Behavior Change for HCI

  2023cites this paper
• Accelerating Similarity Search for Elastic Measures: A Study and New Generalization of Lower Bounding Distances

  2023cites this paper
• Cross-Correlation for Streaming Seismic Time Series to Detect Events using Parallel and Real-time Methods

  2022cites this paper
• Discovering All-chain Set with Direction and Graduality Characteristics over Streaming Time Series

  2022cites this paper
• Learning Evolvable Time-series Shapelets

  2022cites this paper
• Fast Adaptive Similarity Search through Variance-Aware Quantization

  2022cites this paper
• Forecasting the abnormal events at well drilling with machine learning

  2022cites this paper
• Matrix Profile XXV: Introducing Novelets: A Primitive that Allows Online Detection of Emerging Behaviors in Time Series

  2022cites this paper
• Efficient Shapelet Discovery for Time Series Classification

  2022cites this paper
• Efficient Shapelet Discovery for Time Series Classification (Extended Abstract)

  2021cites this paper
• The Swiss army knife of time series data mining: ten useful things you can do with the matrix profile and ten lines of code

  2020cites this paper
• Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures

  2020cites this paper
• Length-Invariant Motif Discovery: Finding Similar Patterns at Different Subsequence Lengths

  2019cites this paper
• Length-Invariant Motif Discovery: Finding Similar Patterns at Different Subsequence Lengths

  2019cites this paper
• Discovering All-Chain Set in Streaming Time Series

  2019cites this paper
• Adaptive Long-Term Ensemble Learning from Multiple High-Dimensional Time-Series

  2019cites this paper
• SeiSMo: Semi-supervised Time Series Motif Discovery for Seismic Signal Detection

  2019cites this paper
• Discord Monitoring for Streaming Time-Series

  2019cites this paper
• Shapelet Classification Algorithm Based on Efficient Subsequence Matching

  2018cites this paper
• Efficient Discovery of Variable-length Time Series Motifs with Large Length Range in Million Scale Time Series

  2018influential citation
• Exploring variable-length time series motifs in one hundred million length scale

  2018influential citation
• Matching Consecutive Subpatterns Over Streaming Time Series

  2018cites this paper
• Monitoring Range Motif on Streaming Time-Series

  2018influential citation
• Vocalizing Large Time Series Efficiently

  2018cites this paper
• QP-DTW: Upgrading Dynamic Time Warping to Handle Quasi Periodic Time Series Alignment

  2018cites this paper
• Three-dimensional piecewise cloud representation for time series data mining

  2018cites this paper
• MDL-based Development of Ensembles with Active Learning over Evolving Data Streams

  2018cites this paper
• HIME: discovering variable-length motifs in large-scale time series

  2018influential citation
• Unsupervised online activity discovery using temporal behaviour assumption

  2017cites this paper
• Automatic Analysis of Facial Actions: Learning from Transductive, Supervised and Unsupervised Frameworks

  2017cites this paper
• A Branch-and-Bound Framework for Unsupervised Common Event Discovery

  2017cites this paper
• Efficient discovery of time series motifs with large length range in million scale time series

  2017influential citation
• Mining Patterns and Networks from Sequence Data

  2017cites this paper
• Pattern Matching with Adaptive Granularity Over Streaming Time Series

  2017cites this paper
• Learning in evolving video streams

  2017cites this paper
• Matrix Profile V: A Generic Technique to Incorporate Domain Knowledge into Motif Discovery

  2017cites this paper
• Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile

  2017cites this paper
• A New Time Series Representation Model and Corresponding Similarity Measure for Fast and Accurate Similarity Detection

  2017cites this paper
• Fine-Grained Pattern Matching Over Streaming Time Series

  2017cites this paper
• Clustering Stream Data by Exploring the Evolution of Density Mountain

  2017cites this paper
• A Novel Method for Fast and Accurate Similarity Measure in Time Series Field

  2017cites this paper
• Know Thyself: A Theory of the Self for Personal Informatics

  2017cites this paper
• Bi-Level Rare Temporal Pattern Detection

  2016cites this paper
• Towards Never-Ending Learning From Parallel Time-Series

  2016cites this paper
• Searching for Logical Patterns in Multi-sensor Data from the Industrial Internet

  2016cites this paper
• Piecewise two-dimensional normal cloud representation for time-series data mining

  2016cites this paper
• Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets

  2016cites this paper
• Irrevocable-choice algorithms for sampling from a stream

  2016cites this paper
• EXTRACT: Strong Examples from Weakly-Labeled Sensor Data

  2016cites this paper
• Fast motif discovery in short sequences

  2016cites this paper
• Time Series Data Mining Methods : A Review

  2015cites this paper
• Learning a Hierarchical Monitoring System for Detecting and Diagnosing Service Issues

  2015cites this paper
• A general solution to detect anomalies in networked distributed sensing systems

  2015cites this paper
• Symbolic representation of cyclic time series: application to biomechanics

  2015cites this paper
• Efficiently discovering frequent motifs in large-scale sensor data

  2015cites this paper
• A Genetic Algorithm to Discover Flexible Motifs with Support

  2015cites this paper
• Time Series Data Mining Methods: A Review

  2015cites this paper
• Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy

  2015cites this paper
• Actuator Networks

  2015cites this paper
• Unsupervised Synchrony Discovery in Human Interaction

  2015cites this paper
• Journal of Sensor and Actuator Networks Lesson Learned from Collecting Quantified Self Information via Mobile and Wearable Devices

  year unknowncites this paper
• Ieee Transactions on Knowledge and Data Engineering, Manuscript Id 1 a General Framework for Density Based Time Series Clustering Exploiting a Novel Admissible Pruning Strategy

  year unknowncites this paper