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

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 23
  • Download : 0
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.
Publisher
ICIC INTERNATIONAL
Issue Date
2016
Language
English
Article Type
Article
Citation

INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, v.12, no.2, pp.419 - 431

ISSN
1349-4198
URI
http://hdl.handle.net/10203/224582
Appears in Collection
RIMS Journal Papers
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0