Scalable Motif Mining in Multidimensional Time Series

Multidimensional time series are sequences of numbers representing observations over time, produced in diverse domains (e.g., ECGs in medicine, seismograms in geology). Their analysis is fundamental to extract information on the activity. In this context motifs are repeated similar multidimensional patterns, finding them is non-trivial with brute force approaches that present polynomial complexity. The work will provide an approximate method to find the top-k motifs with probabilistic guarantees on the results and the cost of the operations based on Locality Sensitive Hashing. Optimizations are included to make the algorithm self-tuning, requiring just the data and the query information on input. Proofs will be developed for correctness and bounds on the number of computations. An extended experimental evaluation will prove scalability of the algorithm and analyze the impact of Locality Sensitive Hashing on the algorithm.

Le time series (i.e., serie storiche) multimensionali sono sequenze di numeri che rappresentano delle misurazioni nel tempo, esse sono prodotte in diversi campi (e.g., ECG in ambito medico, sismogrammi in ambito geologico). La loro analisi è fondamentale per estrarre informazioni sull’attività in atto. In questo ambito i motif (i.e., pattern) sono sottosequenze multidimensionali ripetute, la ricerca dei motif è non triviale con approcci brute-force che presentano complessità polinomiale. L’elaborato fornirà un metodo di approssimazione per trovare i primi k motif con garanzie probabilistiche sui risultati e il costo delle operazioni basandosi su tecniche di Locality Sensitive Hashing. Delle ottimizzazioni verranno implementate per rendere l’algoritmo adattabile all’input automaticamente. Verranno fornite dimostrazioni sulla correttezza dell’algoritmo e limiti sul numero di operazioni. Una sezione sperimentale di valutazione dimostrerà la scalabilità dell’approccio e l’impatto sull’algoritmo del Locality Sensitive Hashing.