Abstract | ||
---|---|---|
The Count-Min sketch and its variations are widely used to solve the frequency estimation problem due to its sub-linear space cost. However, the collisions between high-frequency and low-frequency items introduce a significant estimation error. In this paper, we propose two learned sketches called the Learned Count-Min sketch and Learned Augmented sketch. We combine the machine learning methods with the traditional Count-Min sketch and Augmented sketch to improve the performance. We used a regression model trained from historical data to predict the frequencies and separate the high-frequency items and low-frequency items. The experimental results indicated that our learned sketches outperform the traditional Count-Min sketch and Augmented sketch. The learned sketches can provide a more accurate estimation with a more compact synopsis size. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.ins.2019.08.045 | Information Sciences |
Keywords | Field | DocType |
Sketches,Frequency estimation,Query processing | Regression analysis,Artificial intelligence,Machine learning,Mathematics,Sketch | Journal |
Volume | ISSN | Citations |
507 | 0020-0255 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Meifan Zhang | 1 | 0 | 1.69 |
Hongzhi Wang | 2 | 421 | 73.72 |
Jianzhong Li | 3 | 3196 | 304.46 |
Hong Gao | 4 | 1086 | 120.07 |