Merging extended P² quantile estimators, Part 1

P² quantile estimator is a streaming quantile estimator with \(\mathcal{O}(1)\) memory footprint and an extremely fast update procedure. Several days ago, I learned that it was adopted for the new Paint.NET GPU-based Median Sketch effect (the description is here). While P² meets the basic problem requirement (streaming median approximation without storing all the values), the algorithm performance is still not acceptable without additional adjustments. A significant performance improvement can b...

Submit