The Stair Sketch: Bringing more Clarity to Memorize Recent Events

Data stream processing has become fundamental in computer science, with a wide range of applications, such as in databases, data mining, and security. Memorizing when an item appears in the data stream is one important task in stream processing. Because the older data is, the less value it has, memorizing recent events with higher accuracy is desirable.

To achieve this, we propose a novel data stream processing structure named the Stair sketch. Our key idea is to organize the memory used by different time periods in the shape of stairs. We deploy the Stair sketch on Bloom filters, CM sketches, and CU sketches as case studies. Experiment results show that our approach outperforms state-of-the-art algorithms by more than 5× in accuracy while providing comparable efficiency. The source code of the Stair sketch is available at GitHub.

• Error gradualness. Our scheme needs to be more accurate when performing estimation over more recent periods. This makes better use of the memory available.

• Time stability. The estimation error for the recent past needs to be stable within a well-defined bound. This supports the long-term deployment and use of the scheme. These two concepts are formally defined in Section III.