COMPLEXITY ANALYSIS FOR PARTITIONING NEAREST-NEIGHBOR SEARCHING ALGORITHMS

Authors
ZAKARAUSKAS P OZARD JM
Citation
P. Zakarauskas et Jm. Ozard, COMPLEXITY ANALYSIS FOR PARTITIONING NEAREST-NEIGHBOR SEARCHING ALGORITHMS, IEEE transactions on pattern analysis and machine intelligence, 18(6), 1996, pp. 663-668
Citations number
17
Categorie Soggetti
Computer Sciences","Computer Science Artificial Intelligence","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on pattern analysis and machine intelligence → ACNP
ISSN journal
01628828
Volume
18
Issue
6
Year of publication
1996
Pages
663 - 668
Database
ISI
SICI code
0162-8828(1996)18:6<663:CAFPNS>2.0.ZU;2-#
Abstract
In this paper we present cost estimates for finding the k-nearest neig hbors to a test pattern according to a Minkowski p-metric, as a functi on of the size of the buckets in partitioning searching algorithms. Th e asymptotic expected number of operations to find the nearest neighbo r is presented as a function of the average number of patterns per buc ket n and is shown to contain a global minimum.