Can I read Randomized Admission Policy for Efficient Top-k and Frequency Estimation on EtoBox?

Randomized Admission Policy for Efficient Top-k and Frequency Estimation by Basat, Ran Ben; Einziger, Gil; Friedman, Roy; Kassner, Yaron is a scholarly article available to read on EtoBox.

What is Randomized Admission Policy for Efficient Top-k and Frequency Estimation about?

Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) - a novel algorithm for the frequency and top-k estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the skew of the workload. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. Additionally, we present d-Way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.

Author

Basat, Ran Ben; Einziger, Gil; Friedman, Roy; Kassner, Yaron

Published

2016

Language

EN