[
https://issues.apache.org/jira/browse/CASSANDRA-6474?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13883565#comment-13883565
]
Jonathan Ellis commented on CASSANDRA-6474:
-------------------------------------------
So I'm running the numbers and it's not 100% obvious to me that minhash
actually does better here:
# HLL of p=15 is about 10KB and has an error rate of 0.5%
# According to http://en.wikipedia.org/wiki/MinHash the expected error for
minhash is 1/sqrt(k) for k hashes so to get to 0.5% error rate we'd need 40,000
hashes (160KB)
So, for a relatively low error rate HLL wins. Does it just not "scale down" as
well as minhash? How well would HLL do with a 1600 byte estimate, which
minhash would give us 5% error on? What about 400 bytes?
How accurate do we need the estimate to be, to be useful to compaction?
Incidentally, I'm not sure how hash size affects the 1/sqrt(k) computation,
surely an 8-byte hash would give more accurate results than a 2-byte hash?
> Compaction strategy based on MinHash
> ------------------------------------
>
> Key: CASSANDRA-6474
> URL: https://issues.apache.org/jira/browse/CASSANDRA-6474
> Project: Cassandra
> Issue Type: New Feature
> Components: Core
> Reporter: Yuki Morishita
> Assignee: sankalp kohli
> Labels: compaction
> Fix For: 3.0
>
>
> We can consider an SSTable as a set of partition keys, and 'compaction' as
> de-duplication of those partition keys.
> We want to find compaction candidates from SSTables that have as many same
> keys as possible. If we can group similar SSTables based on some measurement,
> we can achieve more efficient compaction.
> One such measurement is [Jaccard
> Distance|http://en.wikipedia.org/wiki/Jaccard_index],
> !http://upload.wikimedia.org/math/1/8/6/186c7f4e83da32e889d606140fae25a0.png!
> which we can estimate using technique called
> [MinHash|http://en.wikipedia.org/wiki/MinHash].
> In Cassandra, we can calculate and store MinHash signature when writing
> SSTable. New compaction strategy uses the signature to find the group of
> similar SSTable for compaction candidates. We can always fall back to STCS
> when such candidates are not exists.
> This is just an idea floating around my head, but before I forget, I dump it
> here. For introduction to this technique, [Chapter 3 of 'Mining of Massive
> Datasets'|http://infolab.stanford.edu/~ullman/mmds/ch3.pdf] is a good start.
--
This message was sent by Atlassian JIRA
(v6.1.5#6160)
