
 200519: WorkloadOptimal Histograms on Streams (Site not responding. Last check: 20071010) 
  Consider the case when the workload is explicitly stored and the input data is streamed in the time series modelthe input is a vector of N components, and we are presented with the components, one at a time, in order. 
  We present an algorithm that uses polylogarithmic space, processes each new item in constant time, and, in polylogarithmic postprocessing time, determines a (1+epsilon)approximation to the optimal histogram. 
  This matches the space complexity, up to polylogarithmic factors, of the histogram construction on the stream when workload is uniform [Guha, Indyk, Muthukrishnan, and Strauss]. 
 dimacs.rutgers.edu /TechnicalReports/abstracts/2005/200519.html (291 words) 
