Den kleinsten Winkel zwischen Vektoren in logarithmischer Zeit finden

Sie können alle Vektoren in O (n) Zeit normalisieren und eine Parametrisierung von ihnen auf die resultierende 9-dimensionale Hypersphäre finden. Sie können dann eine räumliche Suchstruktur im n-1 dimensionalen Raum verwenden, ähnlich einem Kd-Baum, um die Nächste-Nachbar-Abfrage zu beschleunigen. Dafür gibt es bekannte Methoden ( ANN ).

Was Sie haben, ist im Wesentlichen das Problem der Nahpunkt-auf-der-Kugel (da der Winkel zwischen den Vektoren ungefähr dem Abstand zwischen den Punkten auf der Kugel entspricht, auf der ihre Einheitsvektoren liegen), so könnten Sie wahrscheinlich mach eine Art von Binärdatei (vielleicht wäre Ternär einfacher, zu viele Randprobleme zu vermeiden) Partitionierung Zerlegung.

Aber das wäre unangenehm zu programmieren und wahrscheinlich nicht viel schneller als die naive Methode für 10.000 Punkte (vor allem beginnen Sie damit, die Punkte unter 3 ^ 10 = 59049 Boxen zu teilen, obwohl die meisten davon wären sei leer). Einhundert Millionen Zehn-Element-Dot-Produkte sollten gut unter einer Sekunde sein.

Wow. Zehndimensionale Vektoren? Was machst du mit denen?

Ich denke, ich würde damit beginnen, jeden Vektor auf Einheitslänge zu reduzieren - dh auf Punkte in einer Hypersphäre - und dann einen "Nearest Neighbour Search" (NNS) -Algorithmus wie kD-Baum (k-Dimensional binary tree) zu verwenden. R-Baum, Bester Behälter zuerst, usw.

Es ist wahrscheinlich unmöglich, dieses Problem schneller als O (n log n) zu lösen, denn wenn Sie dieses Problem schneller lösen könnten, könnten Sie das einfachere "engste Punkte-Problem" schneller lösen als die aktuelle untere Grenze von O (n log n).

Wie wäre es, wenn Sie Winkel für jeden Vektor berechnen (O (n)), dann sortieren Sie das Array basierend auf Winkeln (O (nlogn)) und gehen Sie dann durch das Array (O (n)) der nächste Vektor ist entweder i + 1 oder i-1.

Bearbeiten: Wie in Kommentaren ausgeführt, funktioniert dies nur in 2 Dimensionen.