metodo efficiente per la ricerca di KNN di tutti i nodi di un albero KD-

Question

Attualmente sto tentando di trovare K Nearest Neighbor di tutti i nodi di unequilibrata KD-Tree (con K = 2).

La mia implementazione è una variazione del codice dallo Wikipedia article ed è decentemente veloce per trovare KNN di qualsiasi nodo O (log N).

Il problema sta nel fatto che ho bisogno di trovare KNN di ogni nodo. Prossimamente con O (N log N) se eseguo l'iterazione su ciascun nodo ed eseguo la ricerca.

Esiste un modo più efficiente per farlo?

Answer 1

alt text http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif

A seconda delle esigenze, si può decidere di sperimentare tecniche approssimative. Per i dettagli, controlla il lavoro di Arya and Mount sull'argomento. Una carta chiave è here. I dettagli di complessità BigO si trovano nel loro '98 paper.

Ho usato la loro libreria su dataset ad altissima dimensione con centinaia di migliaia di elementi. È più veloce di qualsiasi altra cosa ho trovato. La libreria gestisce sia le ricerche esatte che quelle approssimative. Il pacchetto contiene alcune utility CLI che è possibile utilizzare per sperimentare facilmente con il set di dati; e persino visualizzare il kd-tree (vedi sopra).

FWIW: Ho utilizzato il R Bindings.

Da manuale ANN:

... E 'stato dimostrato da Arya e il Monte [AM93b] e Arya, et al. [AMN + 98] che se l'utente è disposto a tollerare una piccola quantità di errore nella ricerca (restituzione di un punto che non può essere il vicino più prossimo, ma non è significativamente più lontano dal punto di interrogazione di il vicino più prossimo allo ) è quindi possibile ottenere miglioramenti significativi nel tempo di esecuzione . ANN è un sistema per che risponde alle domande più vicine del vicino sia esattamente che approssimativamente.

Answer 2

Se i nodi stessi sono punti di query, quindi il tempo di ricerca potrebbe essere inferiore. È possibile iniziare con la fase di backtracking ei primi nodi testati sono già vicini al punto di interrogazione. Quindi grandi aree dell'albero possono essere potate presto.

Il vicino più prossimo è una relazione simmetrica (se n1 è un vicino più prossimo di n2, lo stesso vale per n2) quindi è sufficiente cercare metà dei nodi saltando tutti i nodi già contrassegnati come vicini più vicini. Solo un'idea

Puoi anche provare la ricerca BBD di KD-Tree (Best-Bin First), che ti aiuterà a cercare prima i nodi più vicini (bin). L'ho implementato in C#, quindi scrivimi se ti interessa il codice sorgente.

Ovviamente, il tempo di esecuzione effettivo dipende dalla dimensionalità, dalla struttura dell'albero KD e dalla distribuzione dei punti nel set di dati.

clustering dei punti potrebbe anche essere appropriata.

Answer 3

ho usato albero di copertura per questo problema. Ecco il link: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

In un set di dati per dimensione 50M (tutte le query kNN, k = 100), l'albero di copertina ha richiesto 5,5 secondi per la creazione e 120 secondi per l'esecuzione di query. Ann lib ha preso 3.3s per la creazione dell'albero e 138 per l'interrogazione.

aggiornamento: Il più vicino non è una relazione simmetrica. Considera questo: A (0,0) B (1,0) C (3,0). B è il più vicino per C mentre C non è il più vicino per B

Answer 4

Il termine da cercare è knn join. Più precisamente, probabilmente vorrai fare un self-join.

Forse questi risultati della ricerca di aiuto:

• http://scholar.google.com/scholar?q=k-d-tree+knn+join

ho visto solo unirsi knn algoritmi per l'* -tree R. Tuttavia, nei miei esperimenti, non erano in grado di sovraperformare una query ripetuta. Potrei mancare alcune idee di implementazione. Ma in generale, tenere i dati in modo appropriato per un albero di join è molto più difficile di una singola query knn.