Encontrar vetores semelhantes em tempo subquadrático

Seja $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ uma função à qual nos referimos como função de similaridade . Exemplos de funções de similaridade são distância cosseno, norma $l_2$ , distância de Hamming, similaridade de Jaccard, etc.

Considere $n$ vectores binários de comprimento $k$ : $\vec{v} \in (\{0,1\}^k)^n$ .

Nosso objetivo é agrupar vetores semelhantes. Mais formalmente, queremos calcular um gráfico de similaridade em que os nós são os vetores e as arestas representam vetores que são semelhantes ( $d(v,u) \leq \epsilon$ ).

$n$ e$k$ são números muito grandes, e comparar doisvetores comprimento$k$é caro, não podemos realizar todas asoperações deforça bruta$O(n^2)$ . Queremos calcular o gráfico de similaridade com significativamente menos operações.

Isso é possível? Se não, podemos calcular uma aproximação ao gráfico que contém todas as arestas no gráfico de similaridade e possivelmente no máximo $O(1)$ outras arestas?

Pode haver uma maneira de inserir o teorema de Johnson-Lindenstrauss nesse problema. Essencialmente, JL afirma que você pode projetar dados de alta dimensão em espaços dimensionais inferiores, de maneira que as distâncias em pares sejam quase preservadas. Mais praticamente, Achlioptas possui um documento chamado projeções aleatórias amigáveis ​​ao banco de dados: Johnson-Lindenstrauss com moedas binárias que faz essa projeção de maneira aleatória, o que funciona muito bem na prática.

Agora, certamente, sua função de similaridade não é exatamente a mesma que algo que se encaixaria no teorema da JL. No entanto, parece uma função de distância e talvez parte da teoria acima possa ajudar.