Come trovare i più vicini 2 punti in uno spazio tridimensionale 100 con 500.000 punti?

Question

Ho un database con 500.000 punti in uno spazio tridimensionale 100, e voglio trovare il più vicino 2 punti. Come posso fare?

Aggiornamento: Lo spazio è euclideo, spiacenti. E grazie per tutte le risposte. BTW questo non è compito.

Answer 1

Si potrebbe provare il ANN biblioteca , ma che dà solo risultati affidabili up a 20 dimensioni.

Answer 2

C'è un capitolo nel Introduzione agli algoritmi dedicato alla ricerca di due punti più vicini in due dimensioni spazio a O (n * log n) tempo. È possibile controllare sul Google Libri . In realtà, vi suggerisco per tutti come il loro modo di applicare la tecnica divide et impera a questo problema è molto semplice, elegante e imponente.

Anche se non può essere esteso direttamente al vostro problema (come costante 7 sarebbe sostituito con 2^101 - 1), dovrebbe essere più che bene per la maggior parte di dati. Quindi, se si dispone di ingresso ragionevolmente casuale, che vi darà O(n*logn*m) complessità dove n è il numero di punti e m è il numero di dimensioni.

modifica
Questo è tutto a patto di avere spazio euclideo. Cioè, lunghezza del vettore v è sqrt(v0^2 + v1^2 + v2^2 + ...). Se è possibile scegliere metrica, tuttavia, ci potrebbero essere altre opzioni per ottimizzare l'algoritmo.

Answer 3

Usa un albero kd. Ecco un problema vicino più prossimo e ci sono altamente ottimizzate le strutture dati per la gestione di questa classe esatta dei problemi.

http://en.wikipedia.org/wiki/Kd-tree

P.S. problema Fun!

Answer 4

Esegui PCA sul tuo dati ai vettori convertire da 100 dimensioni dire 20 dimensioni. Quindi creare un K-Nearest albero Neighbor (KD-Tree) e ottenere il più vicino 2 vicini in base alla distanza euclidea.

In generale, se no. di dimensioni sono molto grandi, allora bisogna o fare un approccio forza bruta (parallela + distribuito / mappa ridurre) o un approccio di clustering.

Answer 5

Utilizza la struttura dati nota come KD-ALBERO. Avrete bisogno di allocare molta memoria, ma si può scoprire un'ottimizzazione o due lungo la strada in base ai dati.

http://en.wikipedia.org/wiki/Kd-tree .

Il mio amico stava lavorando al suo dottorato anni di tesi fa, quando ha incontrato un problema simile. Il suo lavoro è stato dell'ordine di punti 1M in 10 dimensioni. Abbiamo costruito una libreria di kd-tree per risolverlo. Potremmo essere in grado di scavare-up il codice se si desidera contattarci offline.

Ecco il suo articolo pubblicato: http://www.elec.qmul.ac.uk /people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf