Coefficient control multi-step k-NN search in time-series databases

Abstract

The k-NN search is widely used for similarity search on various time-series data such as image, text, trajectory, and biomedical data. In this paper, we address the problem of improving the performance of multi-step k-NN search on a multidimensional index. The existing multi-step k-NN search has a critical performance problem: it produces a large tolerance from a k-NN query on the index due to use of dimensionality reduction, and the large tolerance incurs a large number of candidates, which lead to severe I/O and CPU overhead. To overcome this problem, we propose a new solution, called coefficient control multi-step k-NN search (cc-kNN search in short), which uses c ・ k instead of k in a k-NN query to obtain a tight tolerance. For this, we intuitively explain why a simple operation of increasing k can produce the tight tolerance and formally prove that the cc-kNN search finds k results correctly without any false dismissal. We also define the control constant c used in the k-NN query and formally present how to construct an estimation function for determining the constant c. Experimental results show that the proposed cc-kNN search beats the existing multi-step k-NN search in the execution time as well as the number of candidates.