5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bnaul
    Commented Nov 23, 2010 at 23:14
  • 1
    $\begingroup$ 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%. $\endgroup$
    – whuber ♦
    Commented Nov 23, 2010 at 23:33

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think this will definitely work...in my head I was so attached to the idea of a proper CDF that this didn't even occur to me. Thanks! $\endgroup$
    – bnaul
    Commented Nov 23, 2010 at 23:46
3
$\begingroup$

Here's a possible computing solution to your problem.

If the pdf is sparse (by sparse I mean that long stretches are zero) as your graph indicates, then you could perhaps exploit that structure.

For example, you could have one vector which gives the pdf for non-zero regions and another vector indicating where the non-zero regions begin and end.

You could extend this idea if you have a large number of constant areas in your pdf.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.