Impossibile trovare la carta: tutti i vicini più vicini cercano in n*log (n) utilizzando gli indici di distanza per i punti di supporto del registro (n)

Question

Ricordo di aver letto un documento sulla ricerca di Kinds più vicini per tutti gli oggetti multidimensionali nel set.

Ho cercato di ritrovarlo molte volte, ma finora ho fallito.

L'algoritmo era il seguente:

1. A ogni oggetto viene assegnata una coda ordinata di vicini vicini (la dimensione massima è k). Supponiamo che $ k <log (n) $
2. Ogni volta che calcoli $ distanza (a, b) $ prova ad aggiungere A nella lista dei vicini di B e nella morsa Versa.
3. Scegli $ log (n) $ support Objects (diciamo, First $ log (n) $ oggetti su $ n $). (O forse era $ sqrt (n) $)
4. Per ogni supporto, costruire l'indice basato sulla distanza contenente tutti gli oggetti N
5. Dopo la costruzione dell'indice, ogni oggetto ha un elenco candidato di vicini più vicini. Tutti i veri vicini più vicini non sono oltre il vicino più lontano nella lista dei candidati - RADIUS CANDIDATO.
6. Per ogni punto utilizziamo la disuguaglianza del triangolo e l'attuale raggio del vicino per limitare le distanze tra un punto candidato e i punti di supporto: $ | dist (candidate_i, support_j) - dist (punto, supporto_j) | <= raggio $. Estraggiamo in modo efficiente i candidati che rientrano nelle gamme basate sul raggio per tutti i punti di supporto.
7. Calcoliamo le distanze per quei candidati e aggiorniamo gli elenchi più vicini per il punto attuale che per i punti candidati.
8. Mentre elaboriamo più punti, gli elenchi dei vicini diventano "più stretti": il raggio, la distanza dal vicino più lontano diminuisce con ogni aggiornamento dell'elenco.
9. I vincoli più stretti significano che gli elenchi dei candidati diventano sempre più piccoli dopo ogni punto elaborato e portando al tempo di esecuzione totale di $ n*log (n) $.

Allora, perché ho bisogno di nuovo della carta? Prima di tutto, diverse persone me lo hanno chiesto e sono rimasto sorpreso che non riesco a ritrovarlo. Ancora più importante, non ha funzionato bene per me. Ciò potrebbe essere causato da una cattiva scelta degli oggetti di supporto. Non ricordo nulla del processo di selezione.