Finding similar vectors in subquadratic time

Question

Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function. Examples of similarity function are cosine distance, $l_2$ norm, Hamming distance, Jaccard similarity, etc.

Consider $n$ binary vectors of length $k$: $\vec{v} \in (\{0,1\}^k)^n$.

Our goal is to group vectors which are similar. More formally, we want to compute a similarity graph where nodes are the vectors and edges represent vectors which are similar ($d(v,u) \leq \epsilon$).

$n$ and $k$ are very large numbers, and comparing two length $k$ vectors is expensive, we cannot do all brute-force $O(n^2)$ operations. We want to compute the similarity graph with significantly less operations.

Is this possible? If not can we compute an approximation to the graph which contains all edges in the similarity graph plus possibly at most $O(1)$ other edges?

Answer 1

There may be a way to shoe horn the Johnson-Lindenstrauss theorem into this problem. Essentially, J-L states that you can project high dimensional data into lower dimensional spaces in such a way that the pairwise distances are nearly preserved. More practically, Achlioptas has a paper called Database-friendly random projections: Johnson-Lindenstrauss with binary coins that does this projection in a random way, which works pretty well in practice.

Now, certainly, your similarity function is not exactly the same as something that would fit into the J-L theorem. However, it looks like a distance function and perhaps some of the theory above may help.