Affordable Access

Access to the full text

Fast and fully-automated histograms for large-scale data sets

Authors
  • Mendizábal, Valentina Zelaya
  • Boullé, Marc
  • Rossi, Fabrice
Type
Published Article
Publication Date
Dec 27, 2022
Submission Date
Dec 27, 2022
Identifiers
DOI: 10.1016/j.csda.2022.107668
Source
arXiv
License
Yellow
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times