Computing the Similarity Estimate Using Approximate Memory

In many computing applications there is a need to compute the similarity of sets of elements. When the sets have many elements or comparison involve 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 estimate 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 estimate algorithms require significant memory with its associated power dissipation. This paper for the first time considers the use of approximate memories for similarity estimate. A theoretical analysis and simulation results are provided showing that the use of approximate memories in sketches for similarity estimate provides significant benefits with a negligible impact on accuracy.