SketchConf: A Framework for Automatic Sketch Configuration
Authors:
- 1 April 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2022-2035
Abstract
Sketches have risen as promising solutions for frequency estimation, which is one of the most fundamental tasks in approximate data stream processing. In many scenarios, users have a strong demand to apply sketches under the expected error constraints. In this paper, we explore how to configure sketch parameters to satisfy user-defined error constraints. We propose SketchConf, an automatic sketch configuration framework, which efficiently generates memory-optimal configurations for the first time. We show that SketchConf can be applied to order-independent sketches, including CM, Count, Tower, and Nitro sketches. We further discuss how to deal with the unknown and changeable workloads when applying SketchConf to the real scenarios of streaming data processing. Experimental results show that SketchConf can be up to 715.51 times faster than the baseline algorithm, and the outputted configurations save up to 99.99% memory and achieve up to 27.44 times throughput, compared with the theory-based configurations. The code is open sourced at Github.Keywords
Funding Information
- Research and Development
- National Natural Science Foundation of China
This publication has 34 references indexed in Scilit:
- Persistent Data Sketching2015
- Improved Concentration Bounds for Count-Sketch2013
- Efficient Iceberg Query Processing in Sensor NetworksThe Computer Journal, 2013
- Sketch-based geometric monitoring of distributed stream queriesProceedings of the VLDB Endowment, 2013
- Methods for finding frequent items in data streamsThe VLDB Journal, 2009
- Statistical analysis of sketch estimators2007
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- Data streaming algorithms for efficient and accurate estimation of flow size distributionACM SIGMETRICS Performance Evaluation Review, 2004
- Detecting Change in Data Streams2004
- Monte Carlo and quasi-Monte Carlo methodsActa Numerica, 1998