Name
Abstract | ||
|---|---|---|
This paper proposes a revised algorithm of the nearest neighbor searching (NNS) with the PCA based binary tree data structure by Sproull [1]. In the PCA-tree, by the successive use of principal component analysis (PCA), database is partitioned into clusters. A cluster corresponds to a node of a complete binary tree. In the search step, the algorithm first choses a leaf node, i.e., a cluster, which is likely to include the nearest neighbor (NN) point. Then the exhaustive search only in the node is done. Other leaf nodes which are also likely to include the NN point are searched by the back tracking approach. The performance is improved by sorting the data on a leaf node to leaf node basis and updating the threshold value for choosing nodes by the minimum distance found so far. Sorting the data into leaf nodes contributes greatly to the improvement in the detection time of NN points. The threshold updating in epsilon-approximate nearest neighbors approach and a fixed threshold approach is enough efficient to cope with the deterioration of accuracy. The advantage of our revised approach is not only in the detection time but also in the computer memory usage. The k-dimensional tree approach [2], [3] used in this paper does not need large sized additional tables, whereas the popular NNS algorithms with multiple hash functions method need significantly large tables for large sized databases. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/FUZZ-IEEE.2012.6250773 | 2012 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ-IEEE) |
Keywords | Field | DocType |
Nearest Neighbor Search, Principal Component Analysis, Binary Tree, Cluster | k-nearest neighbors algorithm,R-tree,Pattern recognition,Computer science,Tree (data structure),Binary tree,Sorting,Artificial intelligence,Nearest-neighbor chain algorithm,Hash function,Machine learning,Nearest neighbor search | Conference |
ISSN | Citations | PageRank |
1098-7584 | 1 | 0.37 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hidetomo Ichihashi | 1 | 370 | 72.85 |
| Toshiro Ogita | 2 | 1 | 0.71 |
| Katsuhiro Honda | 3 | 289 | 63.11 |
| Akira Notsu | 4 | 146 | 42.93 |