2024/04/27 by Philip T. Labo, Labo, Philip T. · 1 citation
Chemistry · Engineering · Computer Science · #Spectroscopy and Chemometric Analyses #Industrial Vision Systems and Defect Detection #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2404.18024
Exponential histograms, with bins of the form \ (ρk-1,ρk]\ k∈ℤ, for ρ>1, straightforwardly summarize the quantiles of streaming data sets (Masson et al. 2019). While they guarantee the relative accuracy of their estimates, they appear to use only log n values to summarize n inputs. We study four aspects of exponential histograms -- size, accuracy, occupancy, and largest gap size -- when inputs are i.i.d. Exp(λ) or i.i.d. Pareto(ν,β), taking Exp(λ) (or, Pareto(ν,β)) to represent all light- (or, heavy-) tailed distributions. We show that, in these settings, size grows like log n and takes on a Gumbel distribution as n grows large. We bound the missing mass to the right of the histogram and the mass of its final bin and show that occupancy grows apace with size. Finally, we approximate the size of the largest number of consecutive, empty bins. Our study gives a deeper and broader view of this low-memory approach to quantile estimation.