This paper presents Sample-Efficient Stratified Graph Sampling (SESGS), a novel algorithm that addresses the challenge of high sampling overhead in QoS metrics estimation. SESGS uses importance-weighted stratification of network flows, combining graph centrality heuristics with adaptive Neyman allocation to reduce sampling requirements while maintaining statistical guarantees. The evaluation shows SESGS achieves 85% confidence interval coverage with competitive accuracy and efficiency.
Key findings
SESGS achieves 85% confidence interval coverage, superior to baselines.
The algorithm exhibits O(m log n) time complexity and O(n) space complexity.
SESGS maintains stable performance across challenging graph structures.
Limitations & open questions
Evaluation uses synthetic datasets due to dataset accessibility constraints.
Assumes fixed network topology; dynamic graphs require further study.
Focused on p99 latency; joint estimation of multiple metrics is future work.