A preprint describing a new tool and its application to microbiome analysis was recently published in bioRxiv[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.

[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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.