<p><em>Answer from @user172818, converted from comment:</em></p>
<p>My understanding is that you can't compute Jaccard similarity given two count-min sketches. You can with two histosketches, though I don't know exactly how yet.</p>

CC BY-SA 4.0
2021-07-04T04:19:24.237Z
2021-07-04T04:19:24.237Z
gringer
<p>A preprint describing a new tool and its application to microbiome analysis was recently <a href="https://www.biorxiv.org/content/early/2018/09/04/408070" rel="nofollow noreferrer">published in bioRxiv</a><sup>[1]</sup>. At the core of this new tool, HULK, is a new data structure called a histosketch<sup>[2]</sup> which is similar in spirit to CountMin sketches and MinHash sketches that have become quite popular in bioinformatics in the last several years.</p>

<p>One of the main advantages the histosketch authors claim over CountMin sketch is that CountMin sketches do not preserve similarity. From section II of their paper<sup>[2]</sup> (emphasis mine):</p>

<blockquote>
  <p>It is practically difficult to compute histograms for data streams with typically unknown cardinality and which thus require and unbound amount of memory to maintain the histogram. In this context, the count sketch and the count-min sketch and other online histogram building methods were proposed to approximate the frequency table of elements (i.e., histograms) from a data stream with a fixed-size data structure. However, <strong>the resulting sketches do not preserve similarity between different data streams</strong>.</p>
</blockquote>

<p>In what sense does the CountMin sketch not preserve similarity between streams? Does this refer to similarity at intermediate states (while data is still streaming) or does it refer to inherent characteristics of the data structure itself?</p>

<hr>

<p><sup>[1]</sup> Rowe WPM, Carrieri AP, Alcon-Giner C, Caim S, Shaw A, Sim K, Kroll JS, Hall L, Pyzer-Knapp EO, Winn MD (2018) Streaming histogram sketching for rapid microbiome analytics. <em>bioRxiv</em>, 408070, <a href="https://doi.org/10.1101/408070" rel="nofollow noreferrer">doi:10.1101/408070</a>.</p>

<p><sup>[2]</sup> Yang D, Li B, Rettig L, Cudré-Mauroux P (2017) HistoSketch: Fast similarity-preserving sketching of streaming histograms with concept drift. <em>Proc. IEEE Int. Conf. Data Mining</em>, <a href="https://doi.org/10.1109/ICDM.2017.64" rel="nofollow noreferrer">doi:10.1109/ICDM.2017.64</a>.</p>

<k-mer><algorithms><sketch>
Histosketch vs Count-Min sketch: preserving similarity
# Histosketch vs Count-Min sketch: preserving similarity

(Asked by: username_0 on 2018-09-26)

A preprint describing a new tool and its application to microbiome analysis was recently [published in bioRxiv](https://www.biorxiv.org/content/early/2018/09/04/408070)[1]. At the core of this new tool, HULK, is a new data structure called a histosketch[2] which is similar in spirit to CountMin sketches and MinHash sketches that have become quite popular in bioinformatics in the last several years.

One of the main advantages the histosketch authors claim over CountMin sketch is that CountMin sketches do not preserve similarity. From section II of their paper[2] (emphasis mine):

> It is practically difficult to compute histograms for data streams with typically unknown cardinality and which thus require and unbound amount of memory to maintain the histogram. In this context, the count sketch and the count-min sketch and other online histogram building methods were proposed to approximate the frequency table of elements (i.e., histograms) from a data stream with a fixed-size data structure. However, **the resulting sketches do not preserve similarity between different data streams**.

In what sense does the CountMin sketch not preserve similarity between streams? Does this refer to similarity at intermediate states (while data is still streaming) or does it refer to inherent characteristics of the data structure itself?

---

[1] Rowe WPM, Carrieri AP, Alcon-Giner C, Caim S, Shaw A, Sim K, Kroll JS, Hall L, Pyzer-Knapp EO, Winn MD (2018) Streaming histogram sketching for rapid microbiome analytics. *bioRxiv*, 408070, [doi:10.1101/408070](https://doi.org/10.1101/408070).

[2] Yang D, Li B, Rettig L, Cudré-Mauroux P (2017) HistoSketch: Fast similarity-preserving sketching of streaming histograms with concept drift. *Proc. IEEE Int. Conf. Data Mining*, [doi:10.1109/ICDM.2017.64](https://doi.org/10.1109/ICDM.2017.64).

**Tags:** k-mer, algorithms, sketch

---

## 1 answers

### Answer by username_1 on 2021-07-04. Score: 1

*Answer from @user172818, converted from comment:*

My understanding is that you can't compute Jaccard similarity given two count-min sketches. You can with two histosketches, though I don't know exactly how yet.


---

