[jira] [Updated] (CASSANDRA-6474) Compaction strategy based on MinHash

2018-11-18 Thread C. Scott Andreas (JIRA)


 [ 
https://issues.apache.org/jira/browse/CASSANDRA-6474?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

C. Scott Andreas updated CASSANDRA-6474:

Component/s: Compaction

> Compaction strategy based on MinHash
> 
>
> Key: CASSANDRA-6474
> URL: https://issues.apache.org/jira/browse/CASSANDRA-6474
> Project: Cassandra
>  Issue Type: New Feature
>  Components: Compaction
>Reporter: Yuki Morishita
>Assignee: sankalp kohli
>Priority: Major
>  Labels: compaction
> Fix For: 4.x
>
>
> 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
(v7.6.3#76005)

-
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org



[jira] [Updated] (CASSANDRA-6474) Compaction strategy based on MinHash

2013-12-11 Thread Jonathan Ellis (JIRA)

 [ 
https://issues.apache.org/jira/browse/CASSANDRA-6474?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Jonathan Ellis updated CASSANDRA-6474:
--

  Component/s: Core
 Priority: Major  (was: Minor)
Fix Version/s: 3.0
   Labels: compaction  (was: )

> 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
>  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.4#6159)