Encontrar vectores similares en tiempo subcuadratico

Sea una función a la que nos referimos como la función de similitud . Ejemplos de función de similitud son la distancia del coseno, la norma , la distancia de Hamming, la similitud de Jaccard, etc.$d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$$l_2$

Considere vectores binarios de longitud : .$n$$k$$\vec{v} \in (\{0,1\}^k)^n$

Nuestro objetivo es agrupar vectores que son similares. Más formalmente, queremos calcular un gráfico de similitud donde los nodos son los vectores y los bordes representan vectores que son similares ( ).$d(v,u) \leq \epsilon$

$n$ y son números muy grandes, y comparar dos vectores longitud es costoso, no podemos hacer todas las operaciones de fuerza bruta . Queremos calcular el gráfico de similitud con significativamente menos operaciones.$k$$k$$O(n^2)$

es posible? Si no, ¿podemos calcular una aproximación al gráfico que contiene todos los bordes en el gráfico de similitud más posiblemente a lo sumo otros bordes?$O(1)$

Puede haber una manera de calzar el teorema de Johnson-Lindenstrauss en este problema. Esencialmente, JL afirma que puede proyectar datos de alta dimensión en espacios de menor dimensión de tal manera que las distancias por pares estén casi preservadas. Más prácticamente, Achlioptas tiene un documento llamado Proyecciones aleatorias compatibles con la base de datos: Johnson-Lindenstrauss con monedas binarias que realiza esta proyección de manera aleatoria, que funciona bastante bien en la práctica.

Ahora, ciertamente, su función de similitud no es exactamente igual a algo que encajaría en el teorema de JL. Sin embargo, parece una función de distancia y quizás algo de la teoría anterior pueda ayudar.