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