Efficient Empirical CDF Computation / Storage

I'm trying to precompute the distributions of several random variables. In particular, these random variables are the results of functions evaluated at locations in a genome, so there will be on the order of 10^8 or 10^9 values for each. The functions are pretty smooth, so I don't think I'll lose much accuracy by only evaluating at every 2nd/10th/100th? base or so, but regardless there will be a large number of samples. My plan is to precompute quantile tables (maybe percentiles) for each function and reference these in the execution of my main program to avoid having to compute these distribution statistics in every run.

But I don't really see how I can easily do this: storing, sorting, and reducing an array of 10^9 floats isn't really feasible, but I can't think of another way that doesn't lose information about the distribution. Is there a way of measuring the quantiles of a sample distribution that doesn't require storing the whole thing in memory?

• Further info: the functions represent different measures of proximity to various types of genes. I want to try out different metrics, but they all can be boiled down to "(some kind of) distance to the nearest gene of type X". So the values would probably look something like this graph repeated over and over again (with different shapes), and a histogram could have pretty much any shape, depending on how far apart the relevant genes are. Using the CDF, I could compute a score for a position and the probability of getting this high a score by chance. Nov 23, 2010 at 23:14
• It sounds like you really need only to store one tail accurately. That could simplify your precalculations somewhat. After all, there's little practical difference between a p-value of 50% and 25%, but a huge difference between 5% and 0.001%.
– whuber
Nov 23, 2010 at 23:33

Why not create bins a priori to cover the expected range of a variable, scan through the data once to record all the bin counts, and then estimate the percentiles via interpolation of the EDF? If the bins are evenly distributed, locating the bin for a value is a $O(1)$ operation; in the worst case it's a binary search costing $O(\log(k))$ operations for $k$ bins.