I have a few bins of data. From each bin(which has a few thousand data points), I can compute the total number of data points, the mean of the data points, etc.. I can probably compute any/most statistical entities(mean, median, etc.) of each bin(computationally easy). However, I want to find the 95th percentile of all the data points. The total number of buckets are not that many(~90), so again, I have some room for computation amongst individual statistical entities of each bin.
For finding the 95th percentile, I would generally sort all the data points and pick out the one at the 95th percentile. That won't work in my case(too many data points, computationally intensive). Is there any close approximation to the 95th percentile that I can compute?
There are two phases in my problem - one when I can compute statistical entities for each bin, and the second when I do something with the statistical entities of each bin. Phase 1 and phase 2 happen in different locations, and I can't pass too much data across the two of them.
This is turning out to be a mix of a statistical and computer systems design problem. Please let me know if there is a better place for such a problem. :/