Skip to Main content Skip to Navigation
Journal articles

BestNeighbor: Efficient Evaluation of kNN Queries on Large Time Series Databases

Oleksandra Levchenko 1 Boyan Kolev 2 Djamel-Edine Yagoubi 1 Reza Akbarinia 1 Florent Masseglia 1 Themis Palpanas 3 Dennis Shasha 4 Patrick Valduriez 1
1 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper presents parallel solutions (developed based on two state-of-the-art algorithms iSAX and sketch) for evaluating kNN (k nearest neighbor) queries on large databases of time series, compares them based on various measures of quality and time performance, offers a tool that uses the characteristics of application data to determine which algorithm to choose for that application and how to set the parameters for that algorithm. Specifically, our experiments show that: (i) iSAX and its derivatives perform best in both time and quality when the time series can be characterized by a few low frequency Fourier Coefficients , a regime where the iSAX pruning approach works well. (ii) iSAX performs significantly less well when high frequency Fourier Coefficients have much of the energy of the time series. (iii) A random projection approach based on sketches by contrast is more or less independent of the frequency power spectrum. The experiments show the close relationship between pruning ratio and time for exact iSAX as well as between pruning ratio and the quality of approximate iSAX. Our toolkit analyzes typical time series of an application (i) to determine optimal segment sizes for iSAX and (ii) when to use Parallel Sketches instead of iSAX. Our algorithms have been implemented using Spark, evaluated over a cluster of nodes, and have been applied to both real and synthetic data. The results apply to any databases of numerical sequences, whether or not they relate to time.
Document type :
Journal articles
Complete list of metadata

Cited literature [56 references]  Display  Hide  Download
Contributor : Reza Akbarinia <>
Submitted on : Wednesday, October 21, 2020 - 10:34:09 AM
Last modification on : Wednesday, June 2, 2021 - 4:26:06 PM
Long-term archiving on: : Friday, January 22, 2021 - 6:30:28 PM


Files produced by the author(s)




Oleksandra Levchenko, Boyan Kolev, Djamel-Edine Yagoubi, Reza Akbarinia, Florent Masseglia, et al.. BestNeighbor: Efficient Evaluation of kNN Queries on Large Time Series Databases. Knowledge and Information Systems (KAIS), Springer, 2021, 63, pp.349-378. ⟨10.1007/s10115-020-01518-4⟩. ⟨lirmm-02973633v1⟩



Record views


Files downloads