Posso usare metriche arbitrari per cercare KD-alberi?

Question

Ho appena finito l'attuazione di un kd-tree per fare velocemente ricerche vicini più vicini. Sono interessato a giocare con metriche diverse distanze diverse dalla distanza euclidea . La mia comprensione del kd-tree è che la rapida ricerca di kd-tree non è garantito per dare ricerche esatte se la metrica è non euclidea, il che significa che potrei aver bisogno di implementare una nuova struttura di dati e ricercare l'algoritmo se voglio provare nuove metriche per la mia ricerca.

Ho due domande:

1. Fa utilizzando un kd-tree permanentemente legarmi al distanza euclidea ?
2. Se sì, quali altri tipi di algoritmi Dovrei provare che il lavoro per metriche ? Non ho un sacco di tempo per implementare un sacco di diverse strutture di dati, ma altre strutture sto pensando a includo alberi copertura e VP-alberi .

Answer 1

La procedura di ricerca Nearest Neighbor descritto sulla pagina di Wikipedia si è collegato al può certamente essere generalizzato ad altre metriche a distanza, a patto di sostituire "ipersfera" con l'oggetto geometrico equivalente per la data metrica, e testare ogni iperpiano per incroci con questo oggetto.

Esempio: se si utilizza la distanza di Manhattan, invece (vale a dire la somma dei valori assoluti di tutte le differenze di componenti vettoriali), il vostro ipersfera sarebbe diventato un (multidimensionale) diamante. (Questo è più facile da visualizzare in 2D - se il vostro attuale vicino di casa più vicina è a distanza di x , dal punto di query p , quindi qualsiasi vicino più vicino dietro un iperpiano diversa devono intersecarsi un forma di diamante che ha larghezza e altezza 2x e centrato sulla p ). Questo potrebbe rendere il test iperpiano-crossing più difficili da codice o più lento a correre, ma il principio generale si applica ancora.

Answer 2

Non credo che siete vincolati ad distanza euclidea - come j_random_hacker dice, probabilmente si può utilizzare Manhattan distanza - ma sono abbastanza sicuro che siete legati a geometrie che possono essere rappresentati in coordinate cartesiane. Così non si poteva usare un kd-tree per indicizzare uno spazio metrico, per esempio.