.png){kind=icon}
.png){kind=icon}
Return
Per-Flow Quantile Estimation Using M4 Framework
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2025.3573812.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper introduces a novel framework, M4, designed to estimate per-flow quantiles in data streams accurately. M4 is a versatile framework that can be integrated with a wide array of single-flow quantile estimation algorithms, thereby enabling them to perform per-flow estimation. The framework employs a sketch-based approach to provide a space-efficient method for recording and extracting distribution information. M4 incorporates two techniques: <i>MINIMUM</i> and <i>SUM</i>. The <i>MINIMUM</i> technique minimizes the noise on a flow from other flows caused by hash collisions, while the <i>SUM</i> technique efficiently categorizes flows based on their sizes and customizes treatment strategies accordingly. We demonstrate the application of M4 on three single-flow quantile estimation algorithms (DDSketch, <inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula>-digest, and ReqSketch), detailing the specific implementation of the <i>MINIMUM</i> and <i>SUM</i> techniques. We provide theoretical proof that M4 delivers high accuracy while utilizing limited memory. Additionally, we conduct extensive experiments to evaluate the performance of M4 regarding accuracy and speed. The experimental results indicate that across all three example algorithms, M4 significantly outperforms two comparison frameworks in terms of accuracy for per-flow quantile estimation while maintaining comparable speed.
Keywords:
Per-flow
quantile estimation
data streams
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W
View more organizations