Back

Title
  • en Probably correct k-nearest neighbor search in high dimensions
Creator
    • en Toyama, Jun
    • en Imai, Hideyuki
Accessrights open access
Subject
  • Other en Pattern recognition
  • Other en The k-nearest neighbor method
  • Other en Probably correct algorithm
  • Other en PAC framework
  • NDC 007
Description
  • Abstract en A novel approach for k-nearest neighbor (k-NN) searching with Euclidean metric is described. It is well known that many sophisticated algorithms cannot beat the brute-force algorithm when the dimensionality is high. In this study, a probably correct approach, in which the correct set of k-nearest neighbors is obtained in high probability, is proposed for greatly reducing the searching time. We exploit the marginal distribution of the kth nearest neighbors in low dimensions, which is estimated from the stored data (an empirical percentile approach). We analyze the basic nature of the marginal distribution and show the advantage of the implemented algorithm, which is a probabilistic variant of the partial distance searching. Its query time is sublinear in data size n, that is, O(mnδ) with δ=o(1) in n and δ ≤ 1, for any fixed dimension m.
Publisher en Elsevier
Date
    Issued2010-04
Language
  • eng
Resource Type journal article
Version Type AM
Identifier HDL http://hdl.handle.net/2115/42786
Relation
  • isVersionOf DOI https://doi.org/10.1016/j.patcog.2009.09.026
Journal
    • PISSN 0031-3203
      • en Pattern Recognition
      • Volume Number43 Issue Number4 Page Start1361 Page End1372
File
Oaidate 2023-07-26