Publication: Computing the Similarity Estimate Using Approximate Memory
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 | Reviriego Vasallo, Pedro | |
dc.contributor.author | Ertl, Otmar | |
dc.contributor.author | Liu, Shanshan | |
dc.contributor.author | Niknia, Farzad | |
dc.contributor.author | Lombardi, Fabrizio | |
dc.contributor.funder | Comunidad de Madrid | es |
dc.contributor.funder | Agencia Estatal de Investigación (España) | es |
dc.date.accessioned | 2022-09-21T09:28:26Z | |
dc.date.available | 2022-09-21T09:28:26Z | |
dc.date.issued | 2022-09-01 | |
dc.description.abstract | In many computing applications there is a need to compute the similarity of sets of elements. When the sets have many elements or comparison involves many sets, computing the similarity requires significant computational effort and storage capacity. As in most cases, a reasonably accurate estimate is sufficient, many algorithms for similarity estimation have been proposed during the last decades. Those algorithms compute signatures for the sets and use them to estimate similarity. However, as the number of sets that need to be compared grows, even these similarity estimation algorithms require significant memory with its associated power dissipation. This article for the first time considers the use of approximate memories for similarity estimation. A theoretical analysis and simulation results are provided; initially it is shown that similarity sketches can tolerate large bit error rates and thus, they can benefit from using approximate memories without substantially compromising the accuracy of the similarity estimate. An understanding of the effect of errors in the stored signatures on the similarity estimate is pursued. A scheme to mitigate the impact of errors is presented; the proposed scheme tolerates even larger bit error rates and does not need additional memory. For example, bit error rates of up to 10 4 have less than a 1% impact on the accuracy of the estimate when the memory is unprotected, and larger bit errors rates can be tolerated if the memory is parity protected. These findings can be used for voltage supply scaling and increasing the refresh time in SRAMs and DRAMs. Based on those initial results, an enhanced implementation is further proposed for unprotected memories that further extends the range of tolerated BERs and enables power savings of up to 61.31% for SRAMs. In conclusion, this article shows that the use of approximate memories in sketches for similarity estimation provides significant benefits with a negligible impact on accuracy. | en |
dc.description.sponsorship | This work was supported by ACHILLES project PID2019-104207RB-I00 and Go2Edge network RED2018-102585-T funded by the Spanish Agencia Estatal de Investigación (AEI) 10.13039/501100011033 and by the Madrid Community research project TAPIR-CM under Grant P2018/TCS-4496. The research of S. Liu and F. Lombardi was supported by NSF under Grants CCF-1953961 and 1812467. | en |
dc.format.extent | 12 | |
dc.identifier.bibliographicCitation | Reviriego, P., Liu, S., Ertl, O., Niknia, F. & Lombardi, F. (2022, 1 julio). Computing the Similarity Estimate Using Approximate Memory. IEEE Transactions on Emerging Topics in Computing, 10(3), 1593-1604. | en |
dc.identifier.doi | https://doi.org/10.1109/TETC.2021.3109559 | |
dc.identifier.issn | 2168-6750 | |
dc.identifier.publicationfirstpage | 1593 | |
dc.identifier.publicationissue | 3 | |
dc.identifier.publicationlastpage | 1604 | |
dc.identifier.publicationtitle | IEEE Transactions on Emerging Topics in Computing | en |
dc.identifier.publicationvolume | 10 | |
dc.identifier.uri | https://hdl.handle.net/10016/35753 | |
dc.identifier.uxxi | AR/0000028293 | |
dc.language.iso | eng | |
dc.publisher | IEEE | en |
dc.relation.projectID | Gobierno de España. PID2019-104207RB-I00 | es |
dc.relation.projectID | Gobierno de España. RED2018-102585-T | es |
dc.relation.projectID | Comunidad de Madrid. P2018/TCS-4496 | es |
dc.rights | © 2021 IEEE | en |
dc.rights.accessRights | open access | en |
dc.subject.eciencia | Informática | es |
dc.subject.other | Similarity | en |
dc.subject.other | Approximate computing | en |
dc.subject.other | Minhash | en |
dc.subject.other | Memories | en |
dc.title | Computing the Similarity Estimate Using Approximate Memory | en |
dc.type | research article | * |
dc.type.hasVersion | AM | * |
dspace.entity.type | Publication |
Files
Original bundle
1 - 1 of 1