In the present research we provide an algorithm for a good quality approximate nearest neighbor distance (nnd) profile for a time series, faster than a brute force approach. There are three natural forms of topology embedded in a time series due to different processes: the Euclidean, Symbolic Aggregate Approximation (SAX) and time topology. The first one stems from calculating the Euclidean distance among the sequences; SAX is a quick form of clustering by approximating the values of a sequence; time topology simply refers to the fact that consecutive sequences are naturally similar. By interweaving these three topologies one can prune the calls to the distance function in respect to the brute force algorithm and thus speed up the calculation of the nnd profile. We evaluated the algorithm in terms of the speedup in respect to other algorithms and we compared its precision by counting the percentage of exact nnds returned.

Avogadro, P., Dominoni, M. (2020). An Approximate High Quality Nearest Neighbor Distance Profile. In Communications in Computer and Information Science (pp.158-182). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-66196-0_8].

An Approximate High Quality Nearest Neighbor Distance Profile

Avogadro P.;Dominoni M. A.
2020

Abstract

In the present research we provide an algorithm for a good quality approximate nearest neighbor distance (nnd) profile for a time series, faster than a brute force approach. There are three natural forms of topology embedded in a time series due to different processes: the Euclidean, Symbolic Aggregate Approximation (SAX) and time topology. The first one stems from calculating the Euclidean distance among the sequences; SAX is a quick form of clustering by approximating the values of a sequence; time topology simply refers to the fact that consecutive sequences are naturally similar. By interweaving these three topologies one can prune the calls to the distance function in respect to the brute force algorithm and thus speed up the calculation of the nnd profile. We evaluated the algorithm in terms of the speedup in respect to other algorithms and we compared its precision by counting the percentage of exact nnds returned.
No
paper
Discord; Matrix profile; Motif; Nearest neighbor distance; Time series; Topology
English
11th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management, IC3K 2019
978-3-030-66195-3
Avogadro, P., Dominoni, M. (2020). An Approximate High Quality Nearest Neighbor Distance Profile. In Communications in Computer and Information Science (pp.158-182). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-66196-0_8].
Avogadro, P; Dominoni, M
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/306934
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact