Implementation and Evaluation of Learning-Based Frequency Estimation

Accurate frequency estimation in data streams is essential for applications like network monitoring. Classical sketches such as the Count–Min Sketch and the Count Sketch provide sublinear-space estimates of item counts. However, collisions in these sketches can inflate errors—particularly when “heavy hitters” (very frequent items) collide. To address this, we implement learning-augmented sketches that use neural predictors to identify heavy hitters. In the learned Count–Min sketch, predicted heavy-hitter items are removed from the hash table and given dedicated counters. Our implementation includes (a) the classical Count–Min and Count Sketch algorithms, (b) a learned Count–Min sketch using an ideal oracle (perfectly identifying heavy hitters), (c) a learned Count–Min sketch with a trained neural oracle, and (d) a lookup-table baseline that memorizes heavy hitters from training data. Recurrent models (LSTM/RNNs) are trained on flow-level features to predict item frequencies; for example, two RNNs encode source/destination IP address bit patterns to forecast each network flow’s packet count. Experiments on real Internet traffic (CAIDA backbone traces of millions of packets per minute) and synthetic streams show the hybrid sketch dramatically outperforms classical methods. In particular, the learned Count–Min sketch reduces estimation error by roughly 32–42% (for 0.5–1.0 MB sketches) and the learned Count Sketch by about 52%, compared to their non-learning counterparts. These results demonstrate that combining traditional sketches with neural heavy-hitter prediction yields significantly lower error in streaming frequency estimation.

Una stima accurata della frequenza nei flussi di dati `e fondamentale per applicazioni come il monitoraggio di rete. Le strutture di tipo sketch, come il Count–Min Sketch e il Count Sketch, forniscono stime degli item in spazio sublineare. Tuttavia, le collisioni tra elementi — in particolare tra gli heavy hitters (elementi molto frequenti) — possono incrementare significativamente l’errore di stima. Per risolvere il problema, proponiamo l’uso di sketch potenziati da modelli di apprendimento automatico, in cui predittori neurali vengono impiegati per identificare gli heavy hitters. Nel Count–Min Sketch appreso, gli item previsti come heavy hitters vengono esclusi dalla tabella hash e gestiti tramite contatori dedicati. La nostra implementazione comprende: (a) le versioni classiche di Count–Min Sketch e Count Sketch; (b) un Count–Min Sketch appreso con un oracolo ideale (che identifica perfettamente gli heavy hitters); (c) un Count–Min Sketch appreso con un oracolo neurale addestrato; (d) una baseline con tabella di lookup che memorizza gli heavy hitters dai dati di training. Modelli ricorrenti (LSTM/RNN) sono addestrati su feature a livello di flusso per predire la frequenza degli item; ad esempio, due RNN codificano i pattern di bit degli indirizzi IP sorgente/destinazione per stimare il numero di pacchetti per ciascun flusso di rete. Esperimenti condotti su tracce di traffico Internet reale (dati CAIDA, backbone con milioni di pacchetti al minuto) e su flussi sintetici dimostrano che lo sketch ibrido ha prestazioni superiori rispetto a quelle delle tecniche classiche. In particolare, il Count–Min Sketch appreso riduce l’errore di stima di circa il 32–42% (per sketch da 0.5–1.0 MB), mentre il Count Sketch appreso migliora del 52% rispetto alle rispettive versioni non apprese. Questi risultati dimostrano che combinare sketch tradizionali con predizione neurale degli heavy hitters consente una stima delle frequenze in streaming molto pi`u accurata.