Finden des nächsten Paares zwischen zwei Punktmengen auf dem Hyperwürfel

Bei zwei Teilmengen des dimensionalen Hyperwürfels (dh M , N ⊆ { 0 , 1 } d ) suche ich nach einem Algorithmus, der die Punkte m ∈ M , n ∈ N st der Hamming-Distanz (oder L 1 -) abruft Abstand auf dem Hyperwürfel) d H ( m , n ) ist minimal. Der naive Algorithmus, der nur jedes Paar überprüft, benötigt | M | ⋅ | N | ⋅ $d$$M, N \subseteq \{0,1\}^d$$m\in M, n\in N$$L_1$$d_H(m,n)$$|M|\cdot |N| \cdot d$ Zeit, gibt es ein besseres Ergebnis bekannt?

Der Einfachheit halber können wir annehmen, dass .$|M|=|N|=d$

$|M|=|N|=d$$M$$X$$N$$Y$$Y$$Z=XY$$z_{i,j}$$i$$M$$j$$N$$O(d^{2.3727})$$O(d^{2.3726999999})$

Sie können einen ähnlichen Effekt erzielen, wenn die Matrizen keine Quadrate sind. Ich denke, Uri Zwick hat ein Papier über schnelle Matrixmultiplikation in diesem Fall.

$O(|M| * |N|)$$d$

$L_\infty$$L_m$$L_1$$O(dn \log n)$$d$

[1] Ein optimaler Algorithmus für die Suche nach ungefähren Nachbarn in festen Dimensionen Arya et al., 30 Seiten

[2] Effektive Suche nach nächsten Nachbarn auf dem Hyperwürfel mit Anwendungen auf Cazals mit molekularer Clusterbildung