title: Java Structure that is able to determine approximate number of elements less then x in an ordered set which is updated concurrently
body: <p>Suppose <em>U</em> is an ordered set of elements, <em>S</em> &sube;<em>U</em>, and <em>x</em>   &isin; <em>U</em>. <b> <em>S</em> is being updated concurrently</b>.   I want to get an estimate of the number of elements in <em>S</em> that is less <em>x</em> in O(log(|<em>S</em>|) time.   </p>
  
  <p><em>S</em> is being maintained by another software component that I cannot change. However, whenever <em>e</em> is inserted (or deleted) into <em>S</em> I get a message <code>e inserted (deleted)</code>.  I don't want to maintain my own version of <em>S</em> since memory is limited.  I am looking for a structure, <em>ES</em>, (perhaps using O(log(|S|) space) where I can get a reasonable estimate of the number of elements less than any give <em>x</em>. Assume that the entire set <em>S</em> can periodically be sampled to recreate or update <em>ES</em>. </p>
  
  <p>Update:  I think that this problem statement must include more specific values for <em>U</em>.  One obvious case is where <em>U</em> are numbers (int, double,etc). Another case is where <em>U</em> are strings ordered lexigraphically. </p>
  
  <p>In the case of numbers one could use a probability distribution (but how can that be determined?).  </p>
  
  <p>I am wondering if the set <em>S</em> can be scanned periodically.  Place the entire set into an array and sort.  Then pick the log(n) values at n/log(n), 2n/log(n) ... n where n = |<em>S</em>|.   Then draw a histogram based on those values?</p>
  
  <p>More generally how can one find the appropriate probability distribution from <em>S</em>?</p>
  
  <p>Not sure what the unit of measure would be for strings lexigraphically ordered?</p>