LETFramework: Let the Universal Sketch be Accurate

Sketching algorithms are considered as promising solutions for approximate query tasks on large volumes of data streams. An ideal general-purpose data processing engine requires a sketch to achieve (1) high genericness in supporting a broad range of query tasks; (2) high fidelity in providing accuracy guarantee; and (3) high performance in practice. Although the universal sketch achieves high genericness and fidelity, its accuracy falls short of expectations. In this paper, we propose LETFramework (short for Lossless ExTraction Framework) to optimize the performance of the universal sketch. With the key technique of lossless extraction, LETFramework losslessly extracts the main body of the frequent items and stores the remaining information in the universal sketch, thereby achieving higher accuracy while maintaining high fidelity. We further introduce a unified methodology to incorporate the substitution strategies from top-k algorithms into LETFramework. Experiment results show that, LETFramework outperforms the universal sketch, achieving accuracy improvements ranging from 1 to 3 orders of magnitude on most query tasks and up to 15.73 times higher throughput. All the related source code is open-sourced and available at Github.