# Finding similar vectors in subquadratic time

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?

• Should it be $\leq \epsilon$ rather than $\geq \epsilon$? – usul Aug 27 '14 at 12:35
• @usul Thanks for your comment:) Here, we interested to group items which are highly similar. I have edited the question, I hope it is clear now. – Ram Aug 27 '14 at 16:26
• Sounds to me like you could use Similarity Preserving Hashing (arxiv.org/pdf/1311.7662v1.pdf) to reduce the problem dimension. – R B Aug 28 '14 at 5:40
• This question is not well-defined at all, please provide more details. E.g., if $d$ is given by an oracle, then you obviously cannot do better than ${n\choose 2}$. – domotorp Aug 29 '14 at 19:40
• Do you work for twitter?blog.twitter.com/2014/all-pairs-similarity-via-dimsum Seriously, even detecting if there is an edge in this graph (I.e. that it's not an independent set of vertices) is going to be very hard to do faster than $O(n^2)$ for an arbitrary similarity function. – Ryan Williams Aug 30 '14 at 7:02

## 1 Answer

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.