Fast and fully-automated histograms for large-scale data sets
This work provides an incremental improvement for data scientists and analysts dealing with large-scale data sets by automating histogram construction with faster computational efficiency.
The authors tackled the problem of constructing histograms for large-scale data sets by introducing G-Enum histograms, a fast and fully automated method that uses the Minimum Description Length principle to achieve linearithmic time complexity, compared to polynomial time in previous works, and demonstrated its effectiveness on synthetic and real-world data.
G-Enum histograms are a new fast and fully automated method for irregular histogram construction. By framing histogram construction as a density estimation problem and its automation as a model selection task, these histograms leverage the Minimum Description Length principle (MDL) to derive two different model selection criteria. Several proven theoretical results about these criteria give insights about their asymptotic behavior and are used to speed up their optimisation. These insights, combined to a greedy search heuristic, are used to construct histograms in linearithmic time rather than the polynomial time incurred by previous works. The capabilities of the proposed MDL density estimation method are illustrated with reference to other fully automated methods in the literature, both on synthetic and large real-world data sets.