title: Data structures to Implement Hierarchical clustering
body: <p>If I were to implement a Hierarchical clustering algorithm, say in C/C++ or Java - given the functions for computing distance between&amp; within  clusters -</p>
  
  <p><strong>1</strong>.  what would be my choice(along with other options) to <strong>implement the data structures</strong> on storing the results of the computed clusters in each "pass" from the proximity metric which is defined as n^2 below. </p>
  
  <blockquote>
  <pre><code>        Corresponding Proximity matrix
     p1 p2 p3 p4 .... and hence n*n 
  p1 d11 d12 d13 d14
  p2 ...
  p3...
  p4 ...
  </code></pre>
  </blockquote>
  
  <p><strong>2</strong>. Would the choice of data structures <strong>differ if I were to use top down as opposed to bottom up</strong> building of the corresponding dendograms?</p>
  
  <p><img src="https://i.stack.imgur.com/70vYJ.png" alt="enter image description here"></p>
  
  <p>An example of bottom up dendogram(source, Wiki)</p>
  
  <p><strong>3.</strong> Since the problem of computing the clusters &amp; the centroid thereof is <strong>computationally intensive</strong>(Greedy algorithm ?) - will this get better with the choice of data structures- what are the abstract choices that you can think of ?</p>
  
  <p><strong>4.</strong> Is there really such a thing as <strong>sparse matrix</strong> [post having calculated the proximity of 2 points, which then grow on to assimilate more neighboring points, there will be less points, if we were to store our "new" distances  in a new matrix] in this context ? 
  <strong>Will the data-structure shrink/grow wrt this need ?</strong> </p>
  
  <p><strong>5.</strong> Can this matrix exist <strong>in memory</strong>, or parts of the cluster thereof - If not, what do we have to re-load into memory before computing every next cluster (agglomerative clustering, or otherwise)</p>
  
  <p><em>+1 if you stick with a conceptual(&amp; hopefully intuitive) answer/or redirect me in that direction</em></p>
  
  <p>PPS : I don't NEED a function to help me implement this - <em>just want to understand</em> this from a memory management &amp; conceptual point of view wrt large datasets. I have very little knowledge on this subject, so ignore if this sounds too primitive .</p>