Warum ist der KD-Baum-basierte Nearest Neighbor Exponential in K exponentiell?

8

Ich habe in vielen Artikeln über die Suche nach höherdimensionalen nächsten Nachbarn gelesen, dass KD-Bäume in K exponentiell sind, aber ich kann anscheinend nicht feststellen, warum.

Was ich suche, ist eine solide Analyse der Laufzeitkomplexität, die diesen Aspekt des Problems erklärt.

Akdom
quelle
Schneller Gedanke ist, dass dies keffektiv die Dimension des Problems ist und daher unter dem "Fluch der Dimensionalität" leidet.
Michael Klein

Antworten:

1

2k2k

Andere Bäume haben eine viel bessere Leistung, zum Beispiel der CoverTree . Ich fand auch, dass der PH-Tree ziemlich gut funktioniert, es scheint durchweg doppelt so lange zu dauern wie der CoverTree für Datensätze zwischen k = 8 und k = 27 (ich hatte keine Datensätze mit höherem k).

TilmannZ
quelle
Beachten Sie, dass Sie hier LaTeX verwenden können, um die Mathematik besser lesbar zu setzen. Sehen Sie hier eine kurze Einführung.
Raphael