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?

  • $\begingroup$ Should it be $\leq \epsilon$ rather than $\geq \epsilon$? $\endgroup$
    – usul
    Aug 27, 2014 at 12:35
  • $\begingroup$ @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. $\endgroup$
    – Ram
    Aug 27, 2014 at 16:26
  • $\begingroup$ Sounds to me like you could use Similarity Preserving Hashing (arxiv.org/pdf/1311.7662v1.pdf) to reduce the problem dimension. $\endgroup$
    – R B
    Aug 28, 2014 at 5:40
  • 4
    $\begingroup$ 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}$. $\endgroup$
    – domotorp
    Aug 29, 2014 at 19:40
  • 5
    $\begingroup$ 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. $\endgroup$ Aug 30, 2014 at 7:02

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.