Trouver des vecteurs similaires en temps sub-quadratique

Soit $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ une fonction que nous appelons la fonction de similarité . Des exemples de fonctions de similitude sont la distance cosinus, la norme , la distance de Hamming, la similitude Jaccard, etc.$l_2$

Considérons vecteurs binaires de longueur : .k → v ∈ ( { 0 , 1 } k ) $n$$k$$\vec{v} \in (\{0,1\}^k)^n$

Notre objectif est de regrouper des vecteurs similaires. Plus formellement, nous voulons calculer un graphe de similitude où les nœuds sont les vecteurs et les arêtes représentent des vecteurs qui sont similaires ( ).$d(v,u) \leq \epsilon$

k k O ( n 2$n$ et sont de très grands nombres, et la comparaison de deux vecteurs de longueur coûte cher, nous ne pouvons pas faire toutes les opérations force brute . Nous voulons calculer le graphique de similitude avec beaucoup moins d'opérations.$k$$k$$O(n^2)$

Est-ce possible? Si ce n'est pas le cas, pouvons-nous calculer une approximation du graphique qui contient tous les bords du graphique de similitude plus éventuellement au plus autres bords?$O(1)$

Il y a peut-être un moyen d' inciter le théorème de Johnson-Lindenstrauss à résoudre ce problème. Essentiellement, JL indique que vous pouvez projeter des données de haute dimension dans des espaces de dimension inférieure de manière à ce que les distances par paire soient presque préservées. Plus concrètement, Achlioptas a un article intitulé Projections aléatoires adaptées aux bases de données: Johnson-Lindenstrauss avec des pièces binaires qui effectue cette projection de manière aléatoire, ce qui fonctionne plutôt bien en pratique.

Maintenant, certainement, votre fonction de similitude n'est pas exactement la même chose que quelque chose qui s'insérerait dans le théorème JL. Cependant, cela ressemble à une fonction de distance et peut-être qu'une partie de la théorie ci-dessus peut aider.