<p>There may be a way to shoe horn the <a href="https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma">Johnson-Lindenstrauss</a> 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 <a href="http://users.soe.ucsc.edu/~optas/papers/jl.pdf">Database-friendly random projections: Johnson-Lindenstrauss with binary coins</a> that does this projection in a random way, which works pretty well in practice.</p>

<p>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.</p>

CC BY-SA 3.0
2014-08-30T00:04:50.587Z
2014-08-30T00:04:50.587Z
wyer33
<p>Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the <em>similarity function</em>.
Examples of similarity function are 
cosine distance, $l_2$ norm, Hamming distance, Jaccard similarity, etc.</p>

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

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

<p>$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.</p>

<p>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?</p>

CC BY-SA 3.0
2014-08-27T12:35:02.587Z
Should it be $\leq \epsilon$ rather than $\geq \epsilon$?
usul
CC BY-SA 3.0
2014-08-27T16:26:47.357Z
@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
CC BY-SA 3.0
2014-08-28T05:40:03.407Z
Sounds to me like you could use Similarity Preserving Hashing (http://arxiv.org/pdf/1311.7662v1.pdf) to reduce the problem dimension.
R B
CC BY-SA 3.0
2014-08-29T12:38:17.890Z
Can you specify the "size" of the involved quantities $n,k,\epsilon$?
Marzio De Biasi
CC BY-SA 3.0
2014-08-29T12:51:15.170Z
Assume bigger than you can compute by brute force in your life time :).
Rob
CC BY-SA 3.0
2014-08-29T14:19:18.960Z
A simple approach that can be used for example with the Hamming distance is preprocessing the vectors and counting the number of $1$s (or subdividing them into a feasible amount of "zones" and count the number of $1$s in each zone), in order to filter out quickly those vectors for which $d(v,u) > \epsilon$
Marzio De Biasi
CC BY-SA 3.0
2014-08-29T19:40:42.903Z
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
CC BY-SA 3.0
2014-08-30T05:01:50.253Z
@domotorp Thanks for your comment! Yes, comparison of two strings is given by an oracle, but we are not looking for exact graph. The goal to compute an approximated graph s.t number of edges for which $d(u,v)<\epsilon$ is bounded.
Ram
CC BY-SA 3.0
2014-08-30T07:02:48.743Z
Do you work for twitter?https://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
CC BY-SA 3.0
2014-08-31T14:56:10.120Z
@RyanWilliams  Thanks for your comment. I don't work for twitter :) Recently, I found a related work in this regard. Pls see  www.cs.princeton.edu/cass/papers/www11.pdf. This paper talks about constructing an approximated K-Nearest Neighbor Graph (K-NNG) in subqudratic time.
Ram
<ds.algorithms><graph-algorithms><clustering>
Finding similar vectors in subquadratic time
Ram
# Finding similar vectors in subquadratic time

(Asked by: username_0 on 2014-08-27)

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?

**Tags:** ds.algorithms, graph-algorithms, clustering
> **Comments:**
> **username_1**: Should it be $\leq \epsilon$ rather than $\geq \epsilon$?  
> **username_0**: @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.  
> **username_2**: Sounds to me like you could use Similarity Preserving Hashing (http://arxiv.org/pdf/1311.7662v1.pdf) to reduce the problem dimension.  
> **username_3**: Can you specify the "size" of the involved quantities $n,k,\epsilon$?  
> **username_4**: Assume bigger than you can compute by brute force in your life time :).  
> **username_3**: A simple approach that can be used for example with the Hamming distance is preprocessing the vectors and counting the number of $1$s (or subdividing them into a feasible amount of "zones" and count the number of $1$s in each zone), in order to filter out quickly those vectors for which $d(v,u) > \epsilon$  
> **username_5**: 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}$.  
> **username_0**: @domotorp Thanks for your comment! Yes, comparison of two strings is given by an oracle, but we are not looking for exact graph. The goal to compute an approximated graph s.t number of edges for which $d(u,v)<\epsilon$ is bounded.  
> **username_6**: Do you work for twitter?https://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.  
> **username_0**: @RyanWilliams  Thanks for your comment. I don't work for twitter :) Recently, I found a related work in this regard. Pls see  www.cs.princeton.edu/cass/papers/www11.pdf. This paper talks about constructing an approximated K-Nearest Neighbor Graph (K-NNG) in subqudratic time.  

---

## 1 answers

### Answer by username_7 on 2014-08-30. Score: 5 | Accepted answer

There may be a way to shoe horn the [Johnson-Lindenstrauss](https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) 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](http://users.soe.ucsc.edu/~optas/papers/jl.pdf) 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.


---

