Pretraživanje najbližeg suseda

Izvor: Wikipedia

Pretraživanje najbližeg suseda (engleski: Nearest neighbour search, NNS), koji je takođe poznat kao i okolna pretraga, pretraga sličnosti ili pretraga najbliže tačke, je optimizacija problema za pronalaženje najbliže tačke u metričkim prostorima. Problem je, ako je dat komplet "S" tačaka u metričkom prostoru "M" i tačka pretrage q ∈ M, pronaći najbližu tačku u S do q. U mnogim slučajevima, M se smatra d-dimenzionalnim Euklidovim prostorom i rastojanje se meri Euklidovom razdaljinom, Menhetn razdaljinom ili drugim merama razdaljine.

Donald Knut u 3. tomu dela "Umetnost kompjuterskog programiranja" iz 1973. nazvao je to poštanskim problemom, misleći na princip da se uz mesto prebivališta dodeli najblža pošta.

Primene[uredi - уреди]

Problem pretrage najbližeg suseda se pojavljuje u brojnim oblastima primene, uključujući:

Metode[uredi - уреди]

Razna rešenja su predložena za NNS problem. Koeficijent efikasnosti algoritma zavise od prostora bilo koje data structure koja mora biti održavana. Neformalno posmatranje se uobičajeno naziva kao kletva dimenzionalnosti, kaže da ne postoji generalno resenje za NNS problem koristeći polinomijalno predprocesiranje i polialgoritamsko vreme pretrage.

Linearna pretraga[uredi - уреди]

Najjednostavnije rešenje NNS problema jeste da se izračuna rastojanje od mesta polaska paketa do svake druge tačke iz baze podataka, vodeći računa o "najboljem do sada". Ovaj algoritam, ponekad moze biti nazvan naivnom prilazu, ima vreme izvršavanja O(Nd), gde je N kardinalnost od S i d je dimenzionalnost od M. Naivna pretraga, uobičajeno, je bolja od deljenja prostora na višim dimenzionalnim prostorima.[1]

Razdvajanje prostora[uredi - уреди]

Još od 1970tih, metodologija separacije i evaluacije je primenjivana na problem. U slučaju Euklidovog rastojanja ovaj prustup je poznat kao prostorni indeks ili metod prostornog pristupa. Nekoliko metoda razdvajanja prostora je razvijeno radi rešavanja NNS problema. Verovatno je najjednostavnije K-D stablo, koje iterativno polovi pretragu prostora na 2 regije zadrđavajući polovinu tačaka regije roditelja. U zavisnosti od razdaljine određene upitom, prosečna složenost je O(logN)[2] u slučaju nasumično dodeljenih poena, najgori slučaj složenosti analize koji je bio izvršen.[3] Alternativno R-stablo strukture podataka je dizajnirano da pomogne pretrazi najbližeg suseda u dinamičnom kontekstu, pošto ima efektivne algoritme za umetanje i brisanja.

U slučaju generalnog metričkog prostora "branch and bound” pristup je poznat kao metričko stablo. Posebni primer uključuje vp-stablo i BK-stablo.

Koristeći set tačaka uzet iz trodimenzionalnog prostora i njegovim stavljanjem ga u BSP stablo, i koristeći datu upitnu tačku iz istog prostora, moguće rešenje problema se nalazi na sledeći način. (Strogo govoreći, ne postoji takva tačka, zbog toga šo ne može biti jedinstvena. Međutim u praksi, obično nam je jedino cilj da nađemo podskup svih postojećih tačka oblaka na najkraćem rastojanju od date upitne tačke). Ideja je, da se za svaku granu stabla pretpostavi da je najbliža tačka u oblaku koja je u poluprostoru, sadrži tačku polaska. Ovo ne mora da bude slučaj, ali je dobra heuaristika. Pošto se rekurzvno prođe kroz problem nalaženja poluprostora, poredi se rastojanje vraćeno kao rezultat sa najkraćim rastojanjem od tačke polaska do podele paketa. Ovo kasnije rastojanje je između tačke polaska i najbliže tačke koja može da postoji u nepretraženom poluprostoru. Ako je ovo rastojanje veće od ranijeg rezultata, onda je jasno da nema potrebe istraživati ostatak poluprostora. Ako postoji takva potreba, tada se mora rešiti problem za drugu polovinu prostora, i onda da uporedi rezultat sa prethodnim, i vrati odgovarajuća vrednost. Performanca ovog algoritma je bliža logaritamskom vremenu nego linearnom kada je polazna tačka blizu oblaka, zbog toga što je rastojanje između polazne tačke i najbliže tačka oblaka blizu nule, algoritam jedino treba da pretraži koristeci polaznu tačku kao ključ za tačan rezultat.

Lokalno osetljivo usitnjavanje[uredi - уреди]

Locality sensitive hashing (LSH) tehnika je za grupisanje tačaka u prostoru u "kante” na bazi izvesne mere razdaljine. Tačke koje su bliže jedna drugoj u odredjenoj matrici su označene i imaju najviše šanse da budu u istoj "kanti”.[4]

NNS u prostorima sa malim unutrašnjim dimenzijama[uredi - уреди]

Pokrivno stablo ima teoretsku vezu zasnovanu na setu podataka konstante udvostručavanja. Granica pretrage je O(c12 log n), gde je c konstanta ekspanzije seta podataka.

Vector približnih fajlova[uredi - уреди]

U visoko dimenzionalnim prostorima stablo indeksiranja struktura postaje beskorisno zbog toga što rastući procenat čvorova mora biti pregledan. Za ubrzavanje linearne pretrage, kompresovana verzija budućih vektora čuvanih u RAM-u se koristi kao prefilter za setove podataka pri prvom izvršavanju. Finalni kandidati su određeni u drugom stupnju koristeći nekompresovane podatke sa diska za izračunavanje udaljenosti.[5]

Pretraga zasnovana na kompresiji/grupisanju[uredi - уреди]

VA fajl pristup je specijalan slučaj kompresije zasnovan na pretrazi, gde svaka je komponenta kompresovana jedinstveno. Optimalna tehnika kompresije u multidimenzionalnim postorima je vector kvantizacije (VQ), implemetrirana putem grupisanja. Baza podataka se grupiše i najpodesnija grupa se uzima.[6][7]

Varijante[uredi - уреди]

Postoje brojne varijante za NNS problem, a 2 najpoznatije su pretraga k-najbližih suseda i pretraga ε-aproksimativno najbližih suseda.

Reference[uredi - уреди]

  1. Weber, Schek, Blott. "A quantitative analysis and performance study for similarity search methods in high dimensional spaces". http://www.vldb.org/conf/1998/p194.pdf. 
  2. Andrew Moore. "An introductory tutorial on KD trees". http://www.autonlab.com/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en. 
  3. Lee, D. T.; Wong, C. K. (1977). "Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees". Acta Informatica 9 (1): 23–29. doi:10.1007/BF00263763. 
  4. A. Rajaraman and J. Ullman (2010). "Mining of Massive Datasets, Ch. 3.". http://infolab.stanford.edu/~ullman/mmds.html. 
  5. Weber, Blott. "An Approximation-Based Data Structure for Similarity Search". 
  6. Ramaswamy, Rose, ICIP 2007. "Adaptive cluster-distance bounding for similarity search in image databases". 
  7. Ramaswamy, Rose, TKDE 2001. "Adaptive cluster-distance bounding for high-dimensional indexing". 

Literatura[uredi - уреди]

  • Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal, vol. 19, no 11 (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
  • Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891–923
  • Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
  • Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE 2002: 617-627
  • Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9
  • Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6
  • Shasha, Dennis (2004). High Performance Discovery in Time Series. Berlin: Springer. ISBN 0-387-00857-8. 

Eksterni linkovi[uredi - уреди]

  • Nearest Neighbors and Similarity Search - a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits.
  • Similarity Search Wiki a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours.
  • Metric Spaces Library - An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez.