title: What is an efficient way to compute the Dice coefficient between 900,000 strings?
body: <p>I have a corpus of 900,000 strings.  They vary in length, but have an average character count of about 4,500.  I need to find the most efficient way of computing the <a href="https://en.wikipedia.org/wiki/Dice_coefficient" rel="noreferrer">Dice coefficient</a> of every string as it relates to every other string.  Unfortunately, this results in the Dice coefficient algorithm being used some 810,000,000,000 times.</p>
  
  <p>What is the best way to structure this program for increased efficiency?  Obviously, I can prevent computing the Dice of sections A and B, and then B and A--but this only halves the work required.  Should I consider taking some shortcuts or creating some sort of binary tree?</p>
  
  <p>I'm using the following implementation of the Dice coefficient algorithm in Java:</p>
  
  <pre><code>public static double diceCoefficient(String s1, String s2) {
      Set&lt;String&gt; nx = new HashSet&lt;String&gt;();
      Set&lt;String&gt; ny = new HashSet&lt;String&gt;();
  
      for (int i = 0; i &lt; s1.length() - 1; i++) {
          char x1 = s1.charAt(i);
          char x2 = s1.charAt(i + 1);
          String tmp = "" + x1 + x2;
          nx.add(tmp);
      }
      for (int j = 0; j &lt; s2.length() - 1; j++) {
          char y1 = s2.charAt(j);
          char y2 = s2.charAt(j + 1);
          String tmp = "" + y1 + y2;
          ny.add(tmp);
      }
  
      Set&lt;String&gt; intersection = new HashSet&lt;String&gt;(nx);
      intersection.retainAll(ny);
      double totcombigrams = intersection.size();
  
      return (2 * totcombigrams) / (nx.size() + ny.size());
  }
  </code></pre>
  
  <p>My ultimate goal is to output an ID for every section that has a Dice coefficient of greater than 0.9 with another section.</p>
  
  <p>Thanks for any advice that you can provide!</p>