Effective Space Saving
Roy Friedman, Or Goaz, Ori Rottenstreich · 2020
In computer networks, it is important to analyze the traffic and provide insights about flows sending packets through the network, e.g., to prevent overloads and DDoS attacks. In this paper, we introduce Effective Space Saving (ESS), a novel algorithm for Top-K identification, a fundamental problem in network monitoring and management. ESS can identify Top-K flows in the network and answer queries regarding flows’ frequency estimation while guaranteeing a small error and a small memory footprint.