Cluster-Reduce: Compressing Sketches for Distributed Data Streams

Zhao，Yikai1; Zhong，Zheng1; Li，Yuanpeng1; Zhou，Yi1; Zhu，Yifan3; Chen，Li4; Wang，Yi2,5; Yang，Tong1,2

10.1145/3447548.3467217

2021-08-14

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

2316-2326

Sketches, a type of probabilistic algorithms, have been widely accepted as the approximate summary of data streams. Compressing sketches is the best choice in distributed data streams to reduce communication overhead. The ideal compression algorithm should meet the following three requirements: high efficiency of compression procedure, support of direct query without decompression, and high accuracy of compressed sketches. However, no prior work can meet these requirements at the same time. Especially, the accuracy is poor after compression using existing methods. In this paper, we propose Cluster-Reduce, a framework for compressing sketches, which can meet all three requirements. Our key technique nearness clustering rearranges the adjacent counters with similar values in the sketch to significantly improve the accuracy. We use Cluster-Reduce to compress four kinds of sketches in two use-cases: distributed data streams and distributed machine learning. Extensive experimental results show that Cluster-Reduce can achieve up to 60 times smaller error than prior works. The source codes of Cluster-Reduce are available at Github anonymously[1].

distributed data streams distributed ml sketch compression

其他

英语

EI

20213810905446

Data mining ; Data streams

Data Processing and Image Processing:723.2

2-s2.0-85114933154

Scopus

1.Department of Computer Science and Technology,National Engineering Laboratory for Big Data Analysis Technology and Application,Peking University,China
2.Peng Cheng Laboratory,Shenzhen,China
3.School of Software and Microelectrionics,Peking University,China
4.Huawei Theory Lab,Shenzhen,China
5.Southern University of Science and Technology,Shenzhen,China

Zhao，Yikai,Zhong，Zheng,Li，Yuanpeng,et al. Cluster-Reduce: Compressing Sketches for Distributed Data Streams[C],2021:2316-2326.