Name
Abstract | ||
|---|---|---|
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 k th 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@d) with @d=o(1) in n and @d@?1, for any fixed dimension m. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.patcog.2009.09.026 | Pattern Recognition |
Keywords | Field | DocType |
novel approach,marginal distribution,empirical percentile approach,high probability,correct approach,k-nearest neighbor search,brute-force algorithm,query time,high dimension,data size n,correct set,k-nearest neighbor,pattern recognition,k nearest neighbor,nearest neighbor | k-nearest neighbors algorithm,Sublinear function,Nearest neighbour,Pattern recognition,Euclidean distance,Curse of dimensionality,Artificial intelligence,Probabilistic logic,Machine learning,Marginal distribution,Mathematics,Percentile | Journal |
Volume | Issue | ISSN |
43 | 4 | Pattern Recognition |
Citations | PageRank | References |
9 | 0.55 | 25 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun Toyama | 1 | 130 | 19.87 |
| Mineichi Kudo | 2 | 927 | 116.09 |
| Hideyuki Imai | 3 | 103 | 25.08 |