title: Cosine Similarity of Vectors, with < O(n^2) complexity
body: <p>Having looked around this site for similar issues, I found this: <a href="http://math.nist.gov/javanumerics/jama/" rel="noreferrer">http://math.nist.gov/javanumerics/jama/</a> and this: <a href="http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html" rel="noreferrer">http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html</a></p>
  
  <p>However, it seems these run in O(n^2). I've been doing some document clustering and noticed this level of complexity wasn't feasible when dealing with even small document sets. Given, for the dot product, we only need the vector terms contained in both vectors it should be possible to put the vectors in a tree and thus compute the dot product with n log n complexity, where n is the lowest number of unique terms in 1 of the 2 documents. </p>
  
  <p>Am I missing something? Is there a java library which does this? </p>
  
  <p>thanks</p>