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

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.

algorithm-analysis data-structures search-trees nearest-neighbour search 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:

$2^k$ $2^k$

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