Nearest neighbor search by using Partial KD-tree method

• Autorzy: Kraus P. , Dzwinel W.

Warianty tytułu

PL

Wyszukiwanie najbliższego sąsiada metodą częściowego KD-drzewa

• Języki publikacji: EN

Abstrakty

EN

We present a new nearest neighbor (NN) search algorithm, the Partial KD-Tree Search (PKD), which couples the Friedman’s algorithm and the Partial Distance Search (PDS ) technique. Its efficiency was tested using a wide spectrum of input datasets of various sizes and dimensions. The test datasets were both generated artificially and selected from the UCI repository. It appears that our hybrid algorithm is very efficient in comparison to its components and to other popular NN search technique – the Slicing Search algorithm. The results of tests show that PKD outperforms up to 100 times the brute force method and is substantially faster than other techniques. We can conclude that the Partial KD-Tree is a universal and effcient nearest neighbor search scheme.

PL

W pracy prezentujemy rezultaty poprawy efektywności poszukiwania najbliższego sąsiada poprzez hybrydyzację dwóch najczęściej używanych algorytmów: algorytmu Friedman’a opartego o tzw. K-D drzewa oraz prostej techniki liczenia odległości fragmentami (Partial Distance Search (PDS)). Efektywność powstałego algorytmu przetestowano na danych wygenerowanych w sposób sztuczny oraz na popularnym repozytorium danych UCI. Badano efektywność w zależności od wymiaru przestrzeni oraz strukturalnej złożoności testowanych danych. Okazuje sią że nasz hybrydowy algorytm jest wyraźnie efektywniejszy niż jego części składowe oraz inny popularny algorytmy znajdowania najbliższego sąsiada jak poszukiwanie plasterkowe (Slicing Search (SS)). Rezultaty testów pokazują, że na wybranych danych algorytm jest nawet parą rzędów szybszy niż metoda typu Exhaustive Search i kilka razy szybsza niż inne konkurencyjne wyspecjalizowane algorytmy.

Słowa kluczowe

EN

nearest neighbour search; partial distance; Friedman’s algorithm; Kd-tree; slicing approach; hybrid method; UCI datasets; efficiency

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2008
• Tom: Vol. 20, No. 3
• Strony: 149--165
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Kraus P.

autor

Dzwinel W.

• AGH Institute of Computer Science, al. Mickiewicza 30, 30-059, Krak´ow, Poland

Bibliografia

• [1] S. Arya, Nearest Neighbor Searching and Applications. PhD thesis, University of Maryland, 1995.
• [2] J. L. Bentley, Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975.
• [3] J. L. Bentley, A survey of techniques for fixed radius near neighbor searching. Technical report, Aug 1975.
• [4] De-Y. Cheng, A. Gersho, B. Ramamurthi, Y. Shoham, Fast search algorithms for vector quantization and pattern matching. In IEEE International Conference on Accoustics, Speech and Signal Processing, 1:9.11.1-4, 1984.
• [5] B. V. Dasarathy, Nearest neighbor (NN) Norms: NN Patterns classification Techniques. IEEE Computer Society Press, 1991.
• [6] B. V. Dasarathy, Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design. IEEE Transactions on Systems, Man, and Cybernetics, 24(3):511-517, 1994.
• [7] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification. Wiley Interscience, second edition, 2000.
• [8] J. H. Friedman, J. L. Bentley, and R. A. Finkel, An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3):209-226, 1977.
• [9] J. H. Friedman, F. Basket, and L. J. Shustek, An algorithm for finding nearest neighbors. Pattern Recognition, C-24:1000-6, 1975.
• [10] E. Fix and J. L. Hodges, Discriminatory analysis: Nonparametric discrimination: Consistency properties. USAF School of Aviation Medicine, 4:261-279, 1951.
• [11] E. Fix and J. L. Hodges, Discriminatory analysis: Nonparametric discrimination: Small sample performance. USAF School of Aviation Medicine, 11:280-322, 1952.
• [12] K. Fukunaga and P. M. Narendra, A branch and bound algorithm for computing k-nearest neighbors. IEEE Transactions on Computer, C-26:750-753, 1975.
• [13] P. E. Hart, The condensed nearest neighbor rule. IEEE Transactions on Information Theory, IT-14(3):515-516, 1968.
• [14] Y-S. Huang, Ch-Ch. Chiang, J-W. Shieh, and E. Grimson, Prototype optimization for nearest-neighbor classification. Pattern Recognition, 35(6):1237-1245, 2002.
• [15] K. Hattori and M. Takahashi, A new edited k-nearest neighbor rule in the pattern classification problem. Pattern Recognition, 33(3):521-528, 2000.
• I. Katsavounidis, C.-C. Jay Kuo, and Z. Zhang, Fast tree-structured nearest neighbor encoding for vector quantization. IEEE Transactions on Image Processing, 5(2):398-404, 1996.
• [16] D. E. Knuth, The art of computer programming. Volume 1 – Fundamental algorithms. Wydawnictwa Naukowo-Techniczne, 2002, Polish edition.
• [17] D. E. Knuth, The art of computer programming. Volume 3 – Sorting and searching. Wydawnictwa Naukowo-Techniczne, 2002, Polish edition.
• [18] B. S. Kim and S. B. Park, A fast nearest neighbor finding algorithm based on the ordered partition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):761-766, 1986.
• [19] L. I. Kuncheva, Fitness functions in editing k-nn reference set by genetic algorithms. Pattern Recognition, 30(6):1041-1049, 1997.
• [20] L. Micó, J. Oncina, and R. C. Corrasco, A fast branch & bound nearest neighbor classifier in metric spaces. Pattern Recognition Letters, 17:731-739, 1996.
• [21] S. A. Nene, S. K. Nayar, Closest point search in high dimensions. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 859-865, 1996.
• [22] S. A. Nene, S. K. Nayar, A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(9):989-1003, 1997.
• [23] D. L. Wilson, Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics, 2(3):408-421, 1972.
• [24] H. Yan, Prototype optimization for nearest neighbor classifiers using a two-layer perceptron. Pattern Recognition, 26:317-324, 1993.
• [25] P. N. Yanilos, Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA ’93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 311-321, 1993.
• [26] T. P. Yunck, A technique to identify nearest neighbors. IEEE Transactions on Systems, Man, and Cybernetics, 6(10):678-683, Oct 1976.