johnynek

Unifying Sketch Monoids

As I discussed in Algebra for Analytics, many sketch monoids, such as Bloom filters, HyperLogLog, and Count-min sketch, can be described as a hashing (projection) of items into a sparse space, then using two different commutative monoids to read and write respectively. Finally, the read monoids always have the property that (a + b) <= a, b and the write monoids has the property that (a + b) >= a, b.

##Some questions:

1. Note how similar CMS and Bloom filters are. The difference: bloom hashes k times onto the same space, CMS hashes k times onto a k orthogonal subspaces. Why the difference? Imagine a fixed space bloom that hashes onto k orthogonal spaces, or an overlapping CMS that hashes onto k * m length space. How do the error asymptotics change?
2. CMS has many query modes (dot product, etc...) can those generalize to other sketchs (HLL, Bloom)?
3. What other sketch or non-sketch algorithms can be expressed in this dual mo

tlockney

Vagrant.configure("2") do |config|

  config.vm.box = "dummy"
  
  config.vm.provider :aws do |aws, override|
    aws.access_key_id = "..."
    aws.secret_access_key = "..."
    # you'll need to create the EC2 keypair used here -- I called it vagrant for easy tracking
    aws.keypair_name = "vagrant"
    # you'll want to use a group that has at least SSH open

ceteri

12/05/14 14:42:57 INFO multitool.Main: key: source
12/05/14 14:42:58 INFO multitool.Main: key: expr
12/05/14 14:42:58 INFO multitool.Main: key: gen
12/05/14 14:42:58 INFO multitool.Main: key: group
12/05/14 14:42:58 INFO multitool.Main: key: count
12/05/14 14:42:58 INFO multitool.Main: key: group
12/05/14 14:42:58 INFO multitool.Main: key: sink
12/05/14 14:43:01 INFO util.HadoopUtil: resolving application jar from found main method on: multitool.Main
12/05/14 14:43:01 INFO planner.HadoopPlanner: using application jar: /Users/paco/src/concur/cascading.multitool/./build/multitool.jar
12/05/14 14:43:01 INFO property.AppProps: using app.id: 1C9D0188E5018B980067AAC12AE43BBA

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String inPath = args[ 0 ];
    String outPath = args[ 1 ];

    Properties properties = new Properties();

ceteri

bash-3.2$ elastic-mapreduce --create --name "Sample Recommender" \
>   --jar s3n://temp.cascading.org/sample/recommender.jar \
>     --arg s3n://temp.cascading.org/sample/en.stop \
>     --arg s3n://temp.cascading.org/sample/tweets/ \
>     --arg s3n://temp.cascading.org/sample/out/token \
>     --arg s3n://temp.cascading.org/sample/out/similarity
Created job flow j-2HA2BVCBJGMVX
bash-3.2$ elastic-mapreduce --list
j-2HA2BVCBJGMVX     STARTING                                                         Sample Recommender
   PENDING        Example Jar Step              

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String docPath = args[ 0 ];
    String wcPath = args[ 1 ];

    Properties properties = new Properties();

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String docPath = args[ 0 ];
    String wcPath = args[ 1 ];

    Properties properties = new Properties();

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String docPath = args[ 0 ];
    String wcPath = args[ 1 ];
    String stopPath = args[ 2 ];
    String tfidfPath = args[ 3 ];

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String docPath = args[ 0 ];
    String wcPath = args[ 1 ];
    String stopPath = args[ 2 ];

ceteri

public class
  Main
  {
  public static void
  main( String[] args )
    {
    String docPath = args[ 0 ];
    String wcPath = args[ 1 ];
    String stopPath = args[ 2 ];
    String tfidfPath = args[ 3 ];