Publication: Single Event Transient Tolerant Count Min Sketches
dc.affiliation.dpto | UC3M. Departamento de IngenierÃa Telemática | es |
dc.affiliation.grupoinv | UC3M. Grupo de Investigación: Network Technologies | es |
dc.contributor.author | Zhu, Jinhua | |
dc.contributor.author | Jin, Jie | |
dc.contributor.author | Gao, Zhen | |
dc.contributor.author | Reviriego Vasallo, Pedro | |
dc.contributor.funder | Comunidad de Madrid | es |
dc.contributor.funder | Ministerio de Ciencia, Innovación y Universidades (España) | es |
dc.date.accessioned | 2022-03-21T11:42:14Z | |
dc.date.available | 2024-02-01T00:00:04Z | |
dc.date.issued | 2022-02 | |
dc.description.abstract | 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. | en |
dc.description.sponsorship | 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). | en |
dc.description.status | Publicado | es |
dc.format.extent | 8 | |
dc.identifier.bibliographicCitation | Microelectronics Reliability, (2022), v.129, 114486. | en |
dc.identifier.doi | https://doi.org/10.1016/j.microrel.2022.114486 | |
dc.identifier.issn | 0026-2714 | |
dc.identifier.publicationtitle | MICROELECTRONICS RELIABILITY | en |
dc.identifier.publicationvolume | 129 | |
dc.identifier.uri | https://hdl.handle.net/10016/34427 | |
dc.identifier.uxxi | AR/0000028967 | |
dc.language.iso | eng | en |
dc.publisher | Elsevier | |
dc.relation.projectID | Comunidad de Madrid. Y2018/TCS-5046/EMPATIA-CM | es |
dc.relation.projectID | Gobierno de España. PID2019-104207RB-I00/ACHILLES | es |
dc.relation.projectID | Gobierno de España. RED2018-102585-T/Go2Edge | es |
dc.rights | © 2022 Elsevier Ltd. All rights reserved. | en |
dc.rights | Atribución-NoComercial-SinDerivadas 3.0 España | * |
dc.rights.accessRights | open access | en |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ | * |
dc.subject.eciencia | Telecomunicaciones | es |
dc.subject.other | Count Min Sketch | en |
dc.subject.other | Fault tolerance | en |
dc.subject.other | Frequency estimation | en |
dc.subject.other | Single Event Transients | en |
dc.title | Single Event Transient Tolerant Count Min Sketches | en |
dc.type | research article | * |
dc.type.hasVersion | AM | * |
dspace.entity.type | Publication |
Files
Original bundle
1 - 1 of 1