A Novel Incremental Quantile Estimator Using the Magnitude of the Observations

Abstract

Incremental quantile estimators like the the deterministic multiplicative incremental quantile estimator by Yazidi and Hammer (2017) are simple and efficient algorithms to estimate and track quantiles when data are received sequentially. The estimators merely relying on the sign of the difference between the quantile estimate and the current observation which seems like a waste of information from the data stream. In this paper we suggest a novel incremental estimator that rather use the magnitude of the observations. The intuition behind our approach is that the magnitude is more informative than the sign of the difference. Extensive experiments show that our estimators clearly outperform legacy state-of-the-art quantile estimators.