Detecting persistent items in large-scale data streams efficiently and accurately is a significant challenge, particularly when working with limited memory. Current state-of-the-art methods often require substantial memory resources to maintain high detection accuracy. To address this limitation, we present LightFinder (LF), which leverages a Conservative-Update (CU) strategy to minimize hash collision errors by selectively updating the smallest active counter. Additionally, LF supports detection across varying persistence windows, enhancing detection accuracy and flexibility in skewed data streams. Our analysis reveals that LF excels in detecting persistent items with high accuracy even under stringent memory constraints. Our approach effectively estimates item persistence and maintains robust performance across various persistence windows. Notably, when operating with just 10% of the memory required by On-Off Sketch (OO), LF achieves an Average Absolute Error (AAE) nearly half that of OO (up to 1.5 times lower), and its Average Relative Error (ARE) is reduced by an order of magnitude. This demonstrates LF significantly outperforms existing methods in terms of space efficiency. Our codes are open-sourced on GitHub [1].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

LightFinder: Finding Persistent Items with Small Memory

  • Lu Cao,
  • Weiqiang Xiao,
  • Weizhe Zhang

摘要

Detecting persistent items in large-scale data streams efficiently and accurately is a significant challenge, particularly when working with limited memory. Current state-of-the-art methods often require substantial memory resources to maintain high detection accuracy. To address this limitation, we present LightFinder (LF), which leverages a Conservative-Update (CU) strategy to minimize hash collision errors by selectively updating the smallest active counter. Additionally, LF supports detection across varying persistence windows, enhancing detection accuracy and flexibility in skewed data streams. Our analysis reveals that LF excels in detecting persistent items with high accuracy even under stringent memory constraints. Our approach effectively estimates item persistence and maintains robust performance across various persistence windows. Notably, when operating with just 10% of the memory required by On-Off Sketch (OO), LF achieves an Average Absolute Error (AAE) nearly half that of OO (up to 1.5 times lower), and its Average Relative Error (ARE) is reduced by an order of magnitude. This demonstrates LF significantly outperforms existing methods in terms of space efficiency. Our codes are open-sourced on GitHub [1].