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|| > .8 ||d1||$ and $||d2|| < ||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|| <= ||d1|| / cos I get the computational speed I need