Finding similar vectors in subquadratic time
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.