title: Percentiles of Live Data Capture
body: <p>I am looking for an algorithm that determines percentiles for live data capture.</p>
  
  <p>For example, consider the development of a server application.</p>
  
  <p>The server might have response times as follows:
  17 ms
  33 ms
  52 ms
  60 ms
  55 ms
  etc.</p>
  
  <p>It is useful to report the 90th percentile response time, 80th percentile response time, etc.</p>
  
  <p>The naive algorithm is to insert each response time into a list. When statistics are requested, sort the list and get the values at the proper positions.</p>
  
  <p>Memory usages scales linearly with the number of requests.</p>
  
  <p>Is there an algorithm that yields "approximate" percentile statistics given limited memory usage? For example, let's say I want to solve this problem in a way that I process millions of requests but only want to use say one kilobyte of memory for percentile tracking (discarding the tracking for old requests is not an option since the percentiles are supposed to be for all requests).</p>
  
  <p>Also require that there is no a priori knowledge of the distribution. For example, I do not want to specify any ranges of buckets ahead of time.</p>