2

I have several thousand large datasets that are too big to fit into memory at once, so I need to keep them separate. It is easy enough to get the count, mean, std dev, min and max for the whole dataset, but I also need the percentiles for P1, P5, P10, ..., P90, P95, and P99.

I can generate these numbers (or basically any stat) for each individual dataset. If I have this information for each individual dataset can I then combine the information needed post facto?

I have read many similar questions on here, but I feel I have an advantage since I do have all the original data and not just a small number of summary stats.

Note all datasets have different sample sizes, and distribution is not necessarily normal.

user1563247
  • 131
  • 6
  • You could adapt methods of on-line percentile computation. Start with the links at https://stats.stackexchange.com/questions/508202. Beware! Your datasets likely do not all follow the same distribution, so you shouldn't just process them sequentially. Sample randomly from them to establish highly probable bounds for each percentile, and then you may be able to process the remaining unsampled values one dataset at a time. Another approach would be to approximate the distribution of each dataset accurately and combine the approximations: see https://stats.stackexchange.com/a/35268/919. – whuber Feb 07 '21 at 16:11
  • 1
    Can you explain exactly what you want to do? It sounds like you want to aggregate percentiles across database sets. What sort of aggregation do you need to do? it's hard to do unless your data sets are independent of each other. – seanv507 Feb 07 '21 at 16:50

3 Answers3

1

It turns out there is a vast body of literature focused on this problem in the context of streaming data. This site provides an excellent overview of several methods. In addition there are libraries such as DDSketch and T-Digest that handle this exact category of problem. None of the solutions are exact, but they do guarantee accuracy within a given tolerance, and you can reduce that by keeping more samples (bit still trivial number relative to the total number of samples).

user1563247
  • 131
  • 6
0

As I understand it, you want to combine all the datasets together and get the percentiles for the entire dataset (single variable?), but it doesn't fit in memory.

I can't think of any way that one can "aggregate" percentiles so I would approach it as a technical problem.

Depending on the tech / software you're using, are there any tools to sort the variable in-place? Is it possible to increase the virtual memory?

If not, you may have to think of ways to manually hack your data into batches and preprocess it step by step, without loading everything into memory (I used to do this a lot for particle physics experiments with insanely huge datasets).

For example, do you have a lot of repeated values? Then you could think of a kind of compression - scan the datasets one by one and store the counts for each value you encounter (rather than the values themselves).

If that's not the case, you could estimate some "breakpoints" in your data, and start scanning the datasets and splitting them up and writing them into roughly "ordered" datasets. Once you have the rough datasets, you can do some more sorting & refining on that until you get something that's ordered and fits in memory nicely so you can get P1 to P5... then move onto the next part of the data, and so on.

Or, depending on how accurate your results need to be, you could make the data more coarse by reducing e.g. the decimal precision (making it more easy to count similar values), or some other sort of "binning" (like a histogram, though it would be a fine-tuning job to choose such a binning that can give you reasonably accurate percentiles).

It's a bit vague but that kind of thing (essentially, pre-processing steps to cut down your data volume while retaining the essential info) might help.

Euan Richard
  • 23
  • 3
0

You can't aggregate percentiles without loss of accuracy. As long as you know the number of samples that went into each set of percentiles, you can approximate the combined percentiles reasonably well, however.

This could be done several ways. Since information has been lost when computing percentiles, you have to make some kind of assumption to approximate the original data from the percentiles and then calculate new combined percentiles. One alternative would be to assume that data points are only present at the percentiles (and accept fractional counts). Another would be to assume that the data is uniformly spread out between percentiles in some way.

Let's go with the first assumption as the base for our approximation. If you have two sets of percentile measure available with a known count of samples for each, then you have the values of the percentiles for each and you can assign a frequency of 1/100th of the total count (which may not be an integer). Now, you just sum the total counts and calculate the number of samples per percentile in the new aggregate. Starting from the bottom, you then go through the combined data points (lower to higher) and assign them to your new percentiles until each fill up and then continue to the next and so on. The new percentiles will line up perfectly with a subset of the original percentiles with this method.

Another option would be to instead summarize each data set as a much more fine-grained histogram. The same method can be used based on that and the buckets can be made to line up between all the data sets from the start. This will work the same, but errors can be made smaller.

The approximation errors will depend only on actual samples being approximated incorrectly by at most one bucket's width. In other words, the smaller buckets (size of percentiles or similar) you start out with, the smaller the error. The error can be made arbitrarily small by using more memory.

Hampus
  • 101
  • 2
  • It's not necessary to lose accuracy. There is, however, a tradeoff between accepting some inaccuracy and taking a chance of being wrong. Even that can be mitigated by allowing multiple passes over the data. Take a look at the solutions described in some of the related threads I link to in comments to the question. – whuber Feb 08 '21 at 18:27
  • It depends. If only percentiles for each dataset are used as input, then losing accuracy is generally unavoidable. The full information isn't there. Otherwise, exact percentiles can be calculated by simply concatenating all the data and treating it as one larger dataset. That can be done on disk even, but it no longer aggregates percentiles. – Hampus Feb 09 '21 at 18:09
  • You make an invalid assumption by supposing "only" percentiles are available. That is not assumed in this question. It's simple enough to bracket the percentiles, as is done in many of the online algorithms, and use that to assure accuracy. – whuber Feb 09 '21 at 19:00
  • It's true that the question says that there's potential access to all the data. It also asks specifically if summarizing each data set independently using e.g. percentiles makes it possible to then aggregate those percentiles into percentiles for all the data. Neither this approach nor a streaming solution can calculate exact percentiles, as far as I can tell. Exact solutions require access to all the data, which would work here too. We're both suggesting approximations instead, which is possible both in a streaming way or the way hinted at in the question and is common in practice. – Hampus Feb 10 '21 at 11:04
  • I could have added a solution for exact percentile calculation too. I think partial merge sort on disk (with small batches sorted in RAM) is reasonable efficient for this. Savings can be made by only sorting partially, since only the elements at the percentiles matter. It's common to sort datasets larger than RAM, so that's another practical possibility. Good approximations are likely enough, however, and would be quicker. – Hampus Feb 10 '21 at 11:13