title: K-D Tree vs R-Tree for small, dynamic data
body: <p>I have been reading several SO posts regarding K-D Trees vs. R-Trees but I still have some questions regarding my specific application.</p>
  
  <p>For my Java application, I want to maintain a relatively small number of spatial data points (a few hundred thousand).  The key is that data insertion will not be bulk loaded, but rather, frequently and incrementally inserted.  I should also mention that I will be performing a good number of periodic range queries on sub-regions of the spatial domain.</p>
  
  <p>I have read that K-D Trees do not typically support incremental building and that R-trees are more suitable for this since they maintain a balanced state.  </p>
  
  <p>However, after looking into the solutions suggested here:
  <a href="https://stackoverflow.com/questions/7435645/java-commercial-friendly-r-tree-implementation">Java commercial-friendly R-tree implementation?</a></p>
  
  <p>I did not find that the implementations were easy to work with for returning a list of points in range searches.  However, I have found: <a href="http://java-ml.sourceforge.net/" rel="nofollow noreferrer">http://java-ml.sourceforge.net/</a> to have a very nice implementation of a K-D Tree that works quickly and outperforms standard array storage for a test set of points (~25K).  Additionally, I have read that R-trees store redundant information when dealing with points (since a point is a rectangle with min=max).</p>
  
  <p>Since I am working with a smaller number of points, are the differences between the two structures less important than, say, if I was working with a database application storing millions of points?</p>