Ottimizzazione ricerche albero KD Python

Question

Scipy (http://www.scipy.org/) offre due classi KD Tree; il KDTree e il cKDTree.

Il cKDTree è molto più veloce, ma è meno personalizzabile e in grado di interrogare rispetto a KDTree (per quanto ne so dai documenti).

Ecco il mio problema: Ho una lista di 3 milioni di punti (X, Y) dimensionali. Devo restituire tutti i punti entro una distanza di X unità da ogni punto.

Con KDtree, c'è un'opzione per fare proprio questo: KDtree.query_ball_tree() Genera un elenco di elenchi di tutti i punti all'interno di unità X da ogni altro punto. TUTTAVIA: questa lista è enorme e riempie rapidamente la mia memoria virtuale (circa 744 milioni di articoli lungo).

Soluzione potenziale n. 1: C'è un modo per analizzare questo elenco in un file di testo mentre sta scrivendo?

soluzione Potenziale # 2: Ho provato con un ciclo for (per ogni punto nella lista) e poi trovare che i vicini singolo punto all'interno di X unità impiegando: KDtree.query_ball_point(). TUTTAVIA: ci vuole sempre perché ha bisogno di eseguire la query milioni di volte. Esiste un equivalente cKDTree di questo strumento KDTree?

Soluzione potenziale n. 3: Beats me, qualcun altro ha qualche idea?

Answer 1

Da scipy 0,12 in poi, entrambe le classi dell'albero KD hanno una parità di funzionalità. Citando la sua announcement:

cKDTree feature-complete

versione Cython di KDTree, cKDTree, è ora di funzionalità complete. La maggior parte delle operazioni (costruzione, query, query_ball_point, query_pairs, count_neighbors e sparse_distance_matrix) sono tra 200 e 1000 volte più veloci in cKDTree che in KDTree. Con avvertimenti molto minori, cKDTree ha esattamente la stessa interfaccia di KDTree e può essere usato come una sostituzione drop-in .

Answer 2

Provare a utilizzare KDTree.query_ball_point invece. Prende un singolo punto, o una serie di punti e produce i punti entro una data distanza dal/i punto/i di input.

È possibile utilizzare questa funzione per eseguire query batch. Dagli 100.000 punti alla volta, quindi scrivi i risultati in un file. Qualcosa del genere:

BATCH_SIZE = 100000 
for i in xrange(0, len(pts), BATCH_SIZE): 
    neighbours = tree.query_ball_point(pts[i:i+BATCH_SIZE], X) 
    # write neighbours to a file...