RT Journal Article
T1 Single Event Transient Tolerant Count Min Sketches
A1 Zhu, Jinhua
A1 Jin, Jie
A1 Gao, Zhen
A1 Reviriego Vasallo, Pedro
AB Frequency estimation is a common operation in big data processing. In many big data applications, computing the exact data frequency is not practical as it requires a large computational effort. Instead, a reasonably accurate estimate is commonly used. The Count Min Sketch (CMS) is a popular method for frequency estimation due to its simple implementation and low memory requirements. However, Single Event Transients (SETs) can affect the logic functions of the CMS. Based on our previous research, nearly half of the SETs will lead to CMS estimation errors in the worst case. Moreover, the most frequent elements are more likely to be underestimated when SETs occur, which is not acceptable in practice. Therefore, this paper proposes several fault-tolerant schemes to protect the CMS against SETs, especially to avoid underestimation. In particular, space redundancy-based schemes and partial time redundancy-based schemes are proposed, and the probabilities for underestimation and overestimation are analyzed theoretically. Experiments are performed to compare the reliability of the CMS protected by different schemes and validate the theoretical predictions. Finally, the selection of the best CMS parameters for practical applications is discussed with a comprehensive analysis of the overhead and performance of the different protection schemes.
PB Elsevier
SN 0026-2714
YR 2022
FD 2022-02
LK https://hdl.handle.net/10016/34427
UL https://hdl.handle.net/10016/34427
LA eng
NO This work is supported in part by the National Natural Science Foundation of China (NSFC) under Grant 62171313, in part by the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and in part by the Department of Research and Innovation of Madrid Regional Authority with the EMPATIA-CM Research Project (Reference Y2018/TCS-5046).
DS e-Archivo
RD 27 jul. 2024