Sketching Algorithms in Clojure

Installation

sketchy is available as a Maven artifact from Clojars.

Overview

This library contains various sketching/hash-based algorithms useful for building compact summaries of large datasets.

All the sketches are composed using vanilla Clojure data structures. That means immutability and easy serialization but humble performance. stream-lib is a good alternative for those in need of speed.

General Utilities:

• MurmurHash
• Immutable Bitset

Sketching/hash-based algorithms:

• Bloom Filter
• Min Hash
• Hyper-LogLog
• Count-Min

As we review each section, feel free to follow along in the REPL. Note that bigml.sketchy.test.demo loads Hamlet and A Midsummer Night's Dream into memory for our code examples.

user> (ns test
        (:use [bigml.sketchy.test.demo])
        (:require (bigml.sketchy [murmur :as murmur]
                                 [bits :as bits]
                                 [bloom :as bloom]
                                 [min-hash :as min-hash]
                                 [hyper-loglog :as hll]
                                 [count-min :as count-min])))

MurmurHash

The bigml.sketchy.murmur namespace makes it easy to generate seeded Murmur hashes. Murmur hashes are popular as they are reasonably quick to produce and adequately random.

These Murmur hashes are all produced as 64 bit longs. A simple example hashing the string "foo" to a long:

test> (murmur/hash "foo")
6231696022289519434

Anything that clojure.core/hash accepts may also be used with this hash fn:

test> (murmur/hash {:foo "bar"})
-7720779806311024803

An optional seed parameter selects a unique hashing function. Anything that's hashable by clojure.core/hash is valid as a seed.

test> (murmur/hash "foo" 0)
6231696022289519434
test> (murmur/hash "foo" 42)
-8820575662888368925
test> (murmur/hash "foo" :bar)
-8527955061573093315

The truncate function can be used to truncate the number of bits (must be less than 64 and more than 0).

test> (murmur/truncate (murmur/hash "foo") 32)
3972535114
test> (murmur/truncate (murmur/hash "foo") 16)
4938
test> (murmur/truncate (murmur/hash "foo") 8)
74

If you need multiple unique hashes for a value, hash-seq is a convenience function for that. It applies an infinite sequence of unique hash functions (always in the same order), so take as many as you need.

test> (take 3 (murmur/hash-seq "foo"))
(6231696022289519434 -1965669315023635442 -4826411765733908310)

Immutable Bitset

Besides being my favorite name for a namespace, bigml.sketchy.bits provides an immutable bitset supporting bit-level operations for any number of bits. The bitset is backed by a vector of longs.

The create function builds a bitset given the desired number of bits. Every bit will be initialized as clear (all zero).

The set function sets the bits at the given indicies. The test function returns true if the bit at the given index is set.

test> (def my-bits (-> (bits/create 256)
                       (bits/set 2 48 58 184 233)))
test> (bits/test my-bits 47)
false
test> (bits/test my-bits 48)
true

The set-seq function returns the indicies of every set bit. Alternatively, clear-seq returns all the clear bits.

test> (bits/set-seq my-bits)
(2 48 58 184 233)

The clear function complements set by clearing the bits for the given indices. Similarly, the flip function reverses a bit's state.

test> (bits/set-seq (bits/clear my-bits 48))
(2 58 184 233)
test> (bits/set-seq (bits/flip my-bits 48))
(2 58 184 233)

Moreover, the namespace offers functions to and and or two bitsets. You can also measure hamming-distance, jaccard-similarity, or cosine-similarity.

Bloom Filter

bigml.sketchy.bloom contains an implementation of a Bloom filter, useful for testing set membership. When checking set membership for an item, false positives are possible but false negatives are not.

You may create a Bloom filter by providing the expected number of items to be inserted into the filter and the acceptable false positive rate.

After creating the filter, you may either insert individual items or add an entire collection of items into the Bloom filter.

test> (def hamlet-bloom
        (reduce bloom/insert
                (bloom/create (count hamlet-tokens) 0.01)
                hamlet-tokens))

test> (def midsummer-bloom
        (bloom/into (bloom/create (count midsummer-tokens) 0.01)
                    midsummer-tokens))

Item membership is tested with contains?.

test> (bloom/contains? hamlet-bloom "puck")
false
test> (bloom/contains? midsummer-bloom "puck")
true

The Bloom filters are also merge friendly as long as they are initialized with the same parameters.

test> (def summerham-bloom
        (let [total (+ (count hamlet-tokens) (count midsummer-tokens))]
          (bloom/merge (bloom/into (bloom/create total 0.01) midsummer-tokens)
                       (bloom/into (bloom/create total 0.01) hamlet-tokens))))
test> (bloom/contains? summerham-bloom "puck")
true
test> (bloom/contains? summerham-bloom "yorick")
true
test> (bloom/contains? summerham-bloom "henry")
false

Min-Hash

bigml.sketchy.min-hash contains an implementation of the MinHash algorithm, useful for comparing the Jaccard similarity of two sets.

This implementation includes the improvements recommended in "Improved Densification of One Permutation Hashing", which greatly reduces the algorithmic complexity for building a MinHash.

To create a MinHash, you may provide a target error rate for similarity (default is 0.05). After that, you can either insert individual values or add collections into the MinHash.

In the following example we break A Midsummer Night's Dream into two halves (midsummer-part1 and midsummer-part2) and build a MinHash for each. We then compare the two parts together to see if they are more similar than a MinHash of Hamlet.

As we'd expect, the two halves of A Midsummer Night's Dream are more alike than Hamlet.

test> (def hamlet-hash (min-hash/into (min-hash/create) hamlet-tokens))
test> (def midsummer1-hash (min-hash/into (min-hash/create) midsummer-part1))
test> (def midsummer2-hash (min-hash/into (min-hash/create) midsummer-part2))
test> (min-hash/jaccard-similarity midsummer1-hash midsummer2-hash)
0.2852
test> (min-hash/jaccard-similarity midsummer1-hash hamlet-hash)
0.2012

The MinHashes are merge friendly as long as they're initialized with the same target error rate.

test> (def midsummer-hash (min-hash/into (min-hash/create) midsummer-tokens))
test> (min-hash/jaccard-similarity midsummer-hash
                                   (min-hash/merge midsummer1-hash
                                                   midsummer2-hash))
1.0

Hyper-LogLog

bigml.sketchy.hyper-loglog contains an implementation of the HyperLogLog sketch, useful for estimating the number of distinct items in a set. This is a technique popular for tracking unique visitors over time.

To create a HyperLogLog sketch, you may provide a target error rate for distinct item estimation (default is 0.05). After that, you can either insert individual values or add collections into the sketch.

test> (def hamlet-hll (hll/into (hll/create 0.01) hamlet-tokens))
test> (def midsummer-hll (hll/into (hll/create 0.01) midsummer-tokens))
test> (count (distinct hamlet-tokens)) ;; actual
4793
test> (hll/distinct-count hamlet-hll)  ;; estimated
4868
test> (count (distinct midsummer-tokens)) ;; actual
3034
test> (hll/distinct-count midsummer-hll) ;; estimated
3018

HyperLogLog sketches may be merged if they're initialized with the same error rate.

test> (count (distinct (concat hamlet-tokens midsummer-tokens))) ;; actual
6275
test> (hll/distinct-count (hll/merge hamlet-hll midsummer-hll)) ;; estimated
6312

Similar to MinHash, HyperLogLog sketches can also provide an estimate of the Jaccard similarity between two sets.

test> (def midsummer1-hll (hll/into (hll/create 0.01) midsummer-part1))
test> (def midsummer2-hll (hll/into (hll/create 0.01) midsummer-part2))
test> (hll/jaccard-similarity midsummer1-hll midsummer2-hll)
0.2833001988071571
test> (hll/jaccard-similarity midsummer1-hll hamlet-hll)
0.201231310466139

Count-Min

bigml.sketchy.count-min provides an implementation of the Count-Min sketch, useful for estimating frequencies of arbritrary items in a stream.

To create a count-min sketch you may define the desired number of hash-bits and the number of independent hash functions. The total number of counters maintained by the sketch will be (2^hash-bits)*hashers, so choose these values carefully.

After creating a sketch, you may either insert individual values or add collections into the sketch.

In the example below we build a Count-Min sketch that uses 1500 counters to estimate frequencies for the 4800 unique tokens in Hamlet.

test> (def hamlet-cm (count-min/into (count-min/create :hash-bits 9)
                                     hamlet-tokens))
test> (count (:counters hamlet-cm))
1536
test> ((frequencies hamlet-tokens) "hamlet")
77
test> (count-min/estimate-count hamlet-cm "hamlet")
87
test> ((frequencies hamlet-tokens) "rosencrantz")
7
test> (count-min/estimate-count hamlet-cm "rosencrantz")
15

As with the other sketching algorithms, Count-Min sketches may be merged if they're initialized with the same parameters.

test> (def midsummer1-cm (count-min/into (count-min/create :hash-bits 9)
                                         midsummer-part1))
test> (def midsummer2-cm (count-min/into (count-min/create :hash-bits 9)
                                         midsummer-part2))
test> ((frequencies midsummer-tokens) "love") ;; actual count
98
test> (count-min/estimate-count (count-min/merge midsummer1-cm midsummer2-cm)
                                "love")
104

License

Copyright (C) 2013 BigML Inc.

Distributed under the Apache License, Version 2.0.