TP-Sketch: A Light-Weight Methodology for Persistent Item Lookup in Data Streams

Detecting persistent items that recur across multiple time windows is essential for identifying anomalies in high-speed data streams. However, performing such detection under tight memory constraints and high-speed data streams remains a challenge. Existing approaches often suffer from severe hash collisions because they store much redundant information in sketches, which increases hash collisions of persistent items and degrades both accuracy and processing speed. In this paper, we propose TP-Sketch, a novel approximate data structure that efficiently addresses these issues. Instead of recording additional item statistics, TP-Sketch classifies items as promising or unpromising based on a dynamic global threshold; it then protects promising persistent items from eviction while probabilistically replacing unpromising ones. This strategy improves both accuracy and speed. We provide a formal error-bound analysis to establish the theoretical soundness of TP-Sketch. Extensive trace-driven experiments show that TP-Sketch consistently outperforms state-of-the-art methods in both accuracy and throughput across a variety of tests. For example, compared with P-Sketch, TP-Sketch improves the average F1-score by 16.27% and the average throughput by 113.21% on the MAWI 1 dataset. Overall, TP-Sketch achieves the best accuracy and throughput among state-of-the-art algorithms.