Gentle-Sketch: a high-performance and compact invertible sketch for top-K estimation

Area of Science:

• Computer Science
• Network Data Stream Processing

Background:

• Top-k estimation is crucial for network data stream processing but faces challenges with high-speed traffic and limited resources.
• Existing invertible sketch algorithms often exhibit high memory access overhead, hindering performance.

Purpose of the Study:

• To propose Gentle-Sketch, a high-performance, compact invertible sketch for accurate top-k estimation.
• To address memory utilization and access overhead issues in current sketch algorithms.

Main Methods:

• Gentle-Sketch utilizes an adaptive structure with multiple buckets, tailoring entry sizes to stream distribution.
• It employs flexible relocation of overflowing flows to optimize memory usage and preserve flow characteristics.
• The algorithm hashes each flow to multiple buckets for efficient processing.

Main Results:

• Gentle-Sketch achieves invertibility with high accuracy and throughput in top-k estimation.
• It demonstrates superior performance compared to existing sketch algorithms, including Double-Anonymous Sketch.
• Specifically, it improves estimation precision by over 20% and doubles throughput.

Conclusions:

• Gentle-Sketch provides a high-performance and memory-efficient solution for top-k estimation in network data streams.
• Its adaptive design and flow relocation mechanism enhance accuracy and throughput, making it suitable for resource-constrained environments.