Vector space model cosine tf-idf for finding similar documents Have corpus of over million documents     

For a given document want to find similar documents using cosine as in vector space model

$d_1 \cdot d_2 / ( ||d_1|| ||d_2|| )$

All tf have been normalized using augmented frequency, to prevent a bias towards longer documents as in this tf-idf:

$tf(t,d)=0.5+0.5\frac{f(t,d)}{\mathrm{max}\{f(t,d): t\in d\}}$

Have pre-calculated all $||d||$
Have the values for the denominator pre-calculated
So for a given $d1$ need to score over 1 million $d2$
Have a threshold of 0.6 cosine for similarity  

I can observe that for a given $||d_1||$ there is a fairly narrow range of $||d_2||$ for cosine $\ge$ 0.6
For example in one search for similar for a cosine of $\ge$ 0.6 and a $||d_1||$ of 7.7631 then $||d_2||$ range from 7.0867 to 8.8339
Where outside the threshold of cosine 0.6 $||d_2||$ range from to 0.7223 to 89.3395
This was with standard tf document normalization
It is looking at a LOT of $||d_2||$ that don't have a chance of being a cosine 0.6 match     

Finally the question:
For a give $||d_1||$ and cosine of >= 0.6 how can determine the range of $||d_2||$ that have a chance?
Which $||d_2||$ can I safely eliminate?     

I also know the number of terms in $d_1$ and $d_2$ if there is term count range.

Via experimentation
$||d2|| &gt; .8 ||d1||$ and $||d2|| &lt; ||d1|| / .8 $
seems to be safe but hopefully there is range that is proven to be safe  

Created some test cases with a very some unique terms, some not so unique, and some common.  Sure enough you can take the most unique term and increase that frequency in the compare.  The numerator will (dot product) go up and so will ||compare|| and will get a cosine very close to 1. 

Kind of related and NOT the question.
I am also using the tf-idf to group documents into groups. 
The customer base I am selling into are used to near near dup groups. 
There I am taking a related approach in I look as the smallest term count and evaluate it against term count up to 3x.  So a term count of 10 looks at 10  thru 30 (4-9 already had their shot at 10).  Here I can afford to miss one have it picked up in another.  I am 10% done and the biggest ratio is 1.8.  

Please identify the flaws in this analysis
As pointed out by AN6U5 there is a flaw in this analysis
It is no longer a cosine if the document is normalized on weighted
And as pointed out by Mathew also cannot conclude  d1⋅d2≤d1⋅d1
I am still hoping for something to give me a hard bound but people that seems to know this stuff are telling me no
I don't want to change the question so just ignore this
I will do some analysis and maybe post a separate question on document normalization
For the purpose of this question assume the document is normalized on raw tf
Sorry but I am just not good with what ever markup is used to make the   equations
So in my notation
||d1|| = sqrt(sum(w1 x w1))
d1 dot d2 = sum(w1 X w2)
Assume d1 is the shorter document
The very best d1 dot d2 that can be achieved is d1 dot d1
If d1 is marry 100 paul 20
And d2 is marry 100 paul 20 peter 1
Normalized
d1 is marry 1 paul 1/5
d2 is marry 1 paul 1/5  peter 1/100
Clearly marry and paul have the same idf in both documents
The best possible d1 dot d2 is d1 dot d1
The maximum possible match to d1 is d1
cos = d1 dot d1 / ||d1|| ||d2||
square both sides
cos X cos = (d1 dot d1) X (d1 dot d1) / ( (d1 dot d1) X (d2 dot d2) ) 
cos X cos = (d1 dot d1) / (d2 dot d2)
take the square root of both side
cos = ||d1|| / ||d2||
is ||d2|| not bounded by the cos?
If I just use ||d2|| >= cos ||d1|| and ||d2|| &lt;= ||d1|| / cos I get the computational speed I need
Unfortunately, the math simplifies to show that you can't rigorously justify restricting the cosine similarity comparison of the vectors based on their lengths.  

The key point is that the cosine similarity metric normalizes based on length, so that only the unit vectors are considered.  I know this isn't necessarily the answer that you wanted, but the math clearly shows that the cosine similarity metrics is agnostic to vector length.

Lets look at the math in more detail:

You are applying a cosine similarity metric and requiring that that metric be larger than 0.6:

$$similarity=\cos{(\theta)}=\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||}\geq0.6$$.

But the scalar lengths on the bottom can be distributed into the cross products above (distributive property):

$$\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||} = \frac{\mathbf{A}}{||A||}\cdot\frac{\mathbf{B}}{||B||}=\hat{\mathbf{A}}\cdot\hat{\mathbf{B}}$$.

Now $\hat{\mathbf{A}}$ and $\hat{\mathbf{B}}$ are vectors that point in the same direction as $\mathbf{A}$ and $\mathbf{B}$ but they have been normalized to length one.  So the definition of the cosine similarity metric is the take the original vectors, normalize them to length one, and then measure the dot product of the unit vectors.

Therefor: 

$$similarity=\cos{(\theta)}=\frac{\mathbf{d1}\cdot\mathbf{d2}}{||d1|| ||d2||}=\hat{\mathbf{d1}}\cdot\hat{\mathbf{d2}}\geq0.6$$

depends only on the orientation of the vectors and not on their magnitude (i.e. length).

Reconciling this with what you are doing:

Despite what the results of the linear algebra show, you might still be seeing a statistically significant result.  Practically speaking you may be finding that the statistics show that length restrictions are valid for your data.  For instance, you might be finding that tweets never share a cosine similarity $\geq0.6$ when compared with Tolstoy's "War and Peace".  If your statistics look good for using $||d2|| &gt; .8 ||d1||$ and $||d2|| &lt; ||d1|| / .8$ then I suggest you go with it as these type of canopy restrictions are very useful in saving computing time.

You can perhaps reconcile what you have been doing with distance metrics by also considering the Euclidean distance.  Where as the cosine similarity only returns a value between -1 and 1 based on the angle between the two vectors, the Euclidean distances will return values that depend on the lengths of the two vectors.  In some sense, you are combining aspects of the Euclidean distance with cosine similarity.  

It makes fairly good sense to require that the relative lengths be within 25% of one another in the sense that this combines an aspect of Euclidean distance to create group-by canopies, which cuts computation time, then length agnostic cosine similarity can be used as the final determinant.

Note that 1/.8 =1.25, so d2>=.8d1 is a tighter restriction than d2&lt;=d1/.8.  I suggest using d2>=.75d1 and d2&lt;=1.25d1 as this is symmetric.

Hope this helps!