Struttura dati per il recupero efficiente dell'elemento più vicino da un set

Question

tl; dr In che modo può essere implementato in modo efficiente lo Nearest di Mathematica?

Mathematica ha una funzione chiamata Nearest che avrà una lista di "cose" (possono essere numeri, coordinate in n spazio dimensionale, le stringhe, ecc), e restituisce un oggetto NearestFunction. Questo oggetto è una funzione che, se applicata a x, restituirà l'elemento dell'elenco più vicino a x con una certa metrica di distanza. La metrica della distanza può essere passata come parametro a Nearest: per impostazione predefinita utilizza la distanza euclidea per i dati numerici e un tipo di distanza di modifica per le stringhe.

---

Esempio (questo si spera rendere la questione più chiaro):

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50] tornerà 58, l'elemento più vicino al 50. nf[50, 2] restituirà {58, 39}, i due elementi più vicini.

---

Domanda: Che cosa è un modo efficace per implementare questa funzionalità? Che tipo di struttura dati è probabile utilizzare internamente NearestFunction? Qual è la migliore complessità possibile del calcolo di un elemento più vicino per diversi tipi di dati?

Per un semplice elenco di numeri che li ordinano e facendo una ricerca binaria funzionerebbe, ma Nearest funziona con dati multidimensionali e con una funzione di distanza arbitraria, quindi suppongo che usi qualcosa di più generale. Ma non sarei sorpreso se si rivelasse specializzato per determinati tipi di funzioni dati/distanza.

Answer 1

Per le funzioni di distanza che sono ben educate, ci sono molte strutture dati ottimizzate specificamente per questo. Per i dati multidimensionali, lo k-d tree (e altro binary space partitioning trees) può fornire un eccellente nearest-neighbor searches, di solito in tempo sublimatico. Potresti anche voler esaminare metric trees, che sono strutture ad albero ottimizzate per memorizzare punti in alcuni spazi metrici in modo da supportare le ricerche più vicine. A seconda del particolare spazio metrico (distanza euclidea, modifica distanza, ecc.), Diverse strutture di dati potrebbero essere più o meno appropriate.

Per le funzioni di distanza arbitrarie in cui non vi sono restrizioni sul comportamento (nemmeno ad esempio le disuguaglianze del triangolo, ad esempio), il meglio che si può fare è una ricerca lineare, poiché la funzione distanza potrebbe essere infinita per tutti punti ad eccezione di un punto specifico nel set.

Spero che questo aiuti!

Answer 2

Dipende interamente dai dati e dalla metrica. Leggi tutto su di esso qui: Nearest Neighbour Search