# 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, 2014 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, 2014 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, 2014 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}$. Aug 29, 2014 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. Aug 30, 2014 at 7:02