AlignSketch: A Framework for Aligning Theoretical and Practical Estimation Errors

Sketches are widely used in data streams and approximate query processing for their low memory and acceptable errors. They can be categorized into non-classificationbased and classification-based sketches. While the latter typically provide higher accuracy, they often involve fragmented stream processing, which increases the complexity of theoretical analysis and leads to a widened gap between theoretical bounds and practical estimation errors. To address the challenge, we propose AlignSketch, a general classification framework for data stream processing with provable theoretical guarantees. It achieves tight and verifiable alignment between theoretical error bounds and practical estimation errors. The framework ensures each stream item is recorded at only one tier at any given time, and that estimation errors do not accumulate across tiers but originate from a single one. An important strength of our design is its ability to leverage theoretical results on LRU and LFU miss rates, which have not been explored in existing sketches, to derive tight error bounds. Extensive experiments show that AlignSketch achieves closer alignment between theoretical and practical estimation errors compared to state-of-the-art methods while reducing practical estimation errors by nearly 1 to 2 orders of magnitude. The source code is available on GitHub 11https://anonymous.4open.science/r/AlignSketch.