Build a histogram from a very large data sample

Question

I want to calculate a histogram from an array of size N. N is very large.

I know 2 ways to do so:

1. The naive approach is to find the maximum and the minimum in the first traverse and to split the range into equal bin ranges then to fill bins during the second traverse. However this approach produces degenerate histograms where most of data is piled in one bin if the sample has outliers.
2. The way to counter degenerate histograms is to calculate IRQ or MAD, then calculate range based on this robust measure of scale, and then fill bins in one traverse. However calculation of IRQ or MAD may be slow and requires random access to the array.

I'm intrested if there is a way to build a histogram in between this extreme approaches fulfilling conditions:

• some loss of quality is acceptable
• the array doesn't fit in RAM so random access is the thing I want to avoid
• low time complexity, i'm ready to trade space ~log(N) for time

Answer 1

One reasonable method is to choose a random sample of, say, 1000 items from the array. This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data).

Compute a histogram of those 1000 items, and use that to select bin ranges.

Then, perform a second linear pass on the entire dataset where you accumulate counts in those bins, using those bin ranges.

This will be efficient (nearly as efficient as the naive approach), and help you avoid degenerate histograms.

---

There are more sophisticated methods that are possible as well, from the literatures on streaming algorithms. For instance, you can use a streaming algorithm to estimate the quantiles of the data, which lets you estimate the IQR in a single pass through the data, then you use these estimated information to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins. There are also streaming algorithms to estimate the histogram counts, then you can use that to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins. There's a beautiful literature on this subject. See, e.g., Tracking Quantiles of Network Data Streams with Dynamic Operations by Cao et al, Approximate Frequency Counts over Data Streams by Manku et al, and many others. That said, while this is principled and elegant, it might also be more complex than necessary -- simple random sampling might be good enough for your needs.