Czy mogę używać dowolnych danych do wyszukiwania drzew KD?

Question

Właśnie skończyłem wdrażanie kd-tree do szybkiego wyszukiwania najbliższego sąsiada. Interesuje mnie zabawa z innymi metrykami odległości niż Euclidean distance. Moje rozumienie drzewa kd jest takie, że szybkie przeszukiwanie drzewa kd nie gwarantuje dokładnych wyszukiwań, jeśli metryka nie jest Euklidesowa, co oznacza, że ​​jeśli chcę spróbować, może potrzebować implementacji nowej struktury danych i algorytmu wyszukiwania. nowe dane dla mojego wyszukiwania.

Mam dwa pytania:

1. Czy stosując kd-tree trwale wiążą mnie do Euclidean distance?
2. Jeśli tak, to jakie inne rodzaje algorytmów powinienem wypróbować dla arbitralnego metrics? Nie mam dużo czasu na implementację wielu różnych struktur danych, ale inne struktury, o których myślę, to: cover trees i vp-trees.

Answer 1

Najbliższy-sąsiad procedura szukaj opisane na stronie Wikipedii związanej z pewnością można uogólnić na inne dane na odległość, pod warunkiem zastąpienia „hypersphere” z równoważnej geometrycznego obiektu dla danej metryki i przetestować każdy hiperpłaszczyznę dla skrzyżowania z tym obiektem.

Przykład: jeśli korzystasz z odległości na Manhattanie (tj. Z sumy wartości bezwzględnych wszystkich różnic w składowych wektora), twoja hiperfera stałaby się (wielowymiarowym) diamentem. (Jest to najłatwiejsze do wizualizacji w 2D - jeśli bieżący najbliższy sąsiad znajduje się w odległości x od punktu zapytania p, wtedy każdy bliźniak znajdujący się za inną hiperpłaszczyzną musi przecinać kształt diamentu, który ma szerokość i wysokość 2x i jest wyśrodkowany na p). Może to utrudnić wykonanie testu hiperplitudy skrzyżowania lub wolniej pracować, jednak ogólna zasada nadal obowiązuje.

Answer 2

Nie sądzę, że jesteś związany z odległością euklidesową - jak mówi j_random_hacker, możesz prawdopodobnie użyć odległości na Manhattanie - ale jestem prawie pewny, że jesteś powiązany z geometrią, która może być reprezentowana we współrzędnych kartezjańskich. Nie można na przykład użyć drzewa kd do indeksowania przestrzeni metryki.