Scelta idonea della struttura dati e dell'algoritmo per la ricerca veloce del vicino più vicino di k in 2D

Question

Ho un set di dati di circa 100.000 (X, Y) coppie che rappresentano i punti nello spazio 2D. Per ogni punto, voglio trovare i suoi vicini k-più vicini.

Quindi, la mia domanda è: quale struttura/algoritmo dei dati sarebbe una scelta adatta, supponendo che voglio minimizzare assolutamente il tempo di esecuzione complessivo?

Non sto cercando codice, solo un puntatore verso un approccio adeguato. Sono un po 'intimidito dalla gamma di scelte che sembrano rilevanti: quad-tree, R-trees, kd-trees, ecc.

Sto pensando che l'approccio migliore sia costruire una struttura dati, quindi eseguire alcuni tipo di k - Ricerca dei vicini più vicina per ogni punto. Tuttavia, poiché (a) conosco i punti in anticipo e (b) so che devo eseguire la ricerca per ogni punto esattamente una volta, forse c'è un approccio migliore?

alcuni dettagli in più:

• Dal momento che voglio minimizzare tutto il tempo di esecuzione, non mi importa se la maggior parte del tempo viene speso per la struttura vs ricerca.
• Le coppie (X, Y) sono abbastanza distribuite, quindi possiamo assumere una distribuzione quasi uniforme.

Answer 1

Se k è relativamente piccolo (< 20 circa) e si ha una distribuzione approssimativamente uniforme, creare una griglia che si sovrappone l'intervallo in cui i punti cadono, scelta in modo che il numero medio di punti a griglia è comodamente superiore di k (in modo che un punto situato in posizione centrale ottenga solitamente i suoi k vicini in quell'unico punto della griglia). Quindi creare una serie di altre griglie impostate a metà del primo (sovrapposizione) lungo ciascun asse. Ora per ogni punto, calcola a quale elemento della griglia ricade (dato che le griglie sono regolari, non è richiesta alcuna ricerca) e scegli una delle quattro (o comunque le griglie sovrapposte che hai) che ha quel punto più vicino al suo centro.

All'interno di ciascun elemento della griglia, i punti devono essere ordinati in una coordinata (diciamo x). Partendo dall'elemento che hai scelto (trovandolo usando la bisezione), vai verso l'esterno lungo la lista ordinata finché non hai trovato k elementi (anche in questo caso, se k è piccolo, il modo più veloce per mantenere una lista dei migliori risultati è con l'ordinamento di inserimento binario , lasciando che la peggiore corrispondenza cada alla fine quando si inserisce, insertion sort generalmente batte tutto il resto fino a circa 30 elementi sull'hardware moderno). Continua fino a quando il tuo vicino più vicino è più vicino a te rispetto ai punti successivi in ​​x (cioè non contando il loro offset di y, quindi non ci potrebbe essere un nuovo punto che potrebbe essere più vicino del kth più vicino trovato fino ad ora) .

Se non si hanno ancora k punti o si hanno k punti ma una o più pareti dell'elemento griglia sono più vicine al punto di interesse rispetto al punto più lontano dei k, aggiungere gli elementi di griglia adiacenti pertinenti nel ricerca.

Questo dovrebbe darvi prestazioni di qualcosa come O(N*k^2), con un fattore costante relativamente basso. Se k è grande, allora questa strategia è troppo semplicistica e dovresti scegliere un algoritmo lineare o log-lineare in k, come possono essere gli alberi kd.