Publication:
Single Event Transient Tolerant Count Min Sketches

Simple item page
dc.affiliation.dptoUC3M. Departamento de Ingeniería Telemáticaes
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Network Technologieses
dc.contributor.authorZhu, Jinhua
dc.contributor.authorJin, Jie
dc.contributor.authorGao, Zhen
dc.contributor.authorReviriego Vasallo, Pedro
dc.contributor.funderComunidad de Madrides
dc.contributor.funderMinisterio de Ciencia, Innovación y Universidades (España)es
dc.date.accessioned2022-03-21T11:42:14Z
dc.date.available2024-02-01T00:00:04Z
dc.date.issued2022-02
dc.description.abstractFrequency 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.sponsorshipThis 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.statusPublicadoes
dc.format.extent8
dc.identifier.bibliographicCitationMicroelectronics Reliability, (2022), v.129, 114486.en
dc.identifier.doihttps://doi.org/10.1016/j.microrel.2022.114486
dc.identifier.issn0026-2714
dc.identifier.publicationtitleMICROELECTRONICS RELIABILITYen
dc.identifier.publicationvolume129
dc.identifier.urihttps://hdl.handle.net/10016/34427
dc.identifier.uxxiAR/0000028967
dc.language.isoengen
dc.publisherElsevier
dc.relation.projectIDComunidad de Madrid. Y2018/TCS-5046/EMPATIA-CMes
dc.relation.projectIDGobierno de España. PID2019-104207RB-I00/ACHILLESes
dc.relation.projectIDGobierno de España. RED2018-102585-T/Go2Edgees
dc.rights© 2022 Elsevier Ltd. All rights reserved.en
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España*
dc.rights.accessRightsopen accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subject.ecienciaTelecomunicacioneses
dc.subject.otherCount Min Sketchen
dc.subject.otherFault toleranceen
dc.subject.otherFrequency estimationen
dc.subject.otherSingle Event Transientsen
dc.titleSingle Event Transient Tolerant Count Min Sketchesen
dc.typeresearch article*
dc.type.hasVersionAM*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
single_MR_2022_ps.pdf
Size:
801.03 KB
Format:
Adobe Portable Document Format
Download
Collections
DIT - RYSC - Artículos en Revistas Internacionales / International Journals