Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Theoretical and Applied Informatics

1 2008

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Friedman’s algorithm

Sortuj według:

Ogranicz wyniki do:

Nearest neighbor search by using Partial KD-tree method

Kraus P., Dzwinel W.

Theoretical and Applied Informatics

2008

Vol. 20, No. 3

149-165

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.

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.