SplitSketch: Achieving Accurate Quantile Estimation under Highly Dynamic Traffic Distribution

Quantiles over data stream have been recognized to be an essential feature in network traffic. To provide accurate estimation results, current quantile estimation approaches are preconfigured according to traffic distributions such as log-normal and Pareto distributions. In most practical applications, however, the traffic distributions are not known a priori or are highly dynamic, disturbing estimation results. In this paper, we propose SplitSketch, a sketch-based mechanism that aims to accurately estimate quantiles over data stream without any prior knowledge of traffic distributions. SplitSketch adjusts its estimation granularity according to the changing process of the traffic distribution. The granularities with denser distribution will be recorded with the finer granularity to provide more accurate estimation results. Experimental results demonstrate that, compared to existing approaches, SplitSketch reduces the absolute error in quantile estimation by 59.1% for heavy-tailed distributions and 79.2% for general distributions.