Znajdowanie podobnych wektorów w czasie subkwadratowym

Pozwolić $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus,$l_2$ norma, odległość Hamminga, podobieństwo Jaccard itp.

Rozważać $n$ binarne wektory długości $k$: $\vec{v} \in (\{0,1\}^k)^n$.

Naszym celem jest grupowanie wektorów, które są podobne. Bardziej formalnie chcemy obliczyć wykres podobieństwa, w którym węzły są wektorami, a krawędzie reprezentują wektory podobne ($d(v,u) \leq \epsilon$).

$n$ i $k$ są bardzo dużymi liczbami i porównują dwie długości $k$ wektory są drogie, nie możemy wykonać całej brutalnej siły $O(n^2)$operacje. Chcemy obliczyć wykres podobieństwa przy znacznie mniejszej liczbie operacji.

czy to możliwe? Jeśli nie, to możemy obliczyć przybliżenie do wykresu, który zawiera wszystkie krawędzie na wykresie podobieństwa plus co najwyżej$O(1)$ inne krawędzie?

Być może istnieje sposób na róg buta twierdzenie Johnsona-Lindenstraussa w tym problemie. Zasadniczo JL stwierdza, że ​​można wyświetlać dane wielowymiarowe w przestrzeniach o niższych wymiarach w taki sposób, że odległości par są prawie zachowane. Mówiąc prościej, Achlioptas ma artykuł zatytułowany Losowe projekcje przyjazne bazom danych: Johnson-Lindenstrauss z monetami binarnymi, które wykonują tę projekcję w sposób losowy, co działa całkiem dobrze w praktyce.

Teraz z pewnością twoja funkcja podobieństwa nie jest dokładnie taka sama, jak coś, co pasowałoby do twierdzenia JL. Wygląda jednak na funkcję odległości i być może część powyższej teorii może pomóc.