Lasso: Accurate and Efficient Detection of Long-Lived Sparse Items in High-Speed Data Streams

Abstract

In high-speed data streams, identifying long-lived (also referred to as persistent) sparse items is critical, as such patterns may indicate stealthy or low-rate threats yet remain largely underexplored. Although recent studies have begun to examine this problem, existing approaches either suffer from low lookup accuracy due to coarse update strategies or rely on complex data structures with costly update operations, overlooking the practical requirement of deployability. These limitations hinder scalability, particularly as programmable switches and FPGAs are increasingly adopted as data-processing substrates that sustain high-speed processing under strict resource and operational constraints. To address these challenges, we propose Lasso, a lightweight and hardware-conscious approach that achieves high detection accuracy under tight memory budgets while sustaining high processing throughput on industry-grade hardware, including Tofino-1 programmable switches and FPGA platforms. Lasso leverages the observation that long-lived sparse items exhibit a small gap between persistence and frequency, evicting items with large deviations to prioritize promising candidates. In addition, Lasso incorporates fine-grained, temporally aware protection to prevent long-lived items from being prematurely displaced by abundant short-lived items in highly skewed data streams. We further develop a formal analytical model to establish the theoretical soundness of Lasso. Extensive evaluations across CPU, Tofino, and FPGA platforms demonstrate that Lasso delivers high accuracy and throughput while operating within strict resource constraints.