I want to calculate a histogram from an array of size
N is very large.
I know 2 ways to do so:
- 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.
- 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