WIXLIB

Bloom Filters, Count Sketches and Adaptive SketchesRice UniversityAnshumali Shrivastavaanshumali@rice.edu29th August 2016Anshumali Shrivastava (COMP 640)Sketching29th August 20161 / 22

Basics: Universal HashingBasic tool for shuffling and sampling from any set of objectsO {1, 2, ., n}.h : O {1, 2, ., m}Pr (h(x) h(y )) 1miff x 6 y .Some implementationsPick a random number a and b, a large enough prime, returnh(x) ax b mod p mod mFastest Trick: Choose m 2M to be power of 2, choose a randomodd integer return h(x) ax (32 M)Problems:Given a set O, randomly assign it to m bins.Randomly sample 1/m fraction of the data.Activity: Suppose m n How to sample one element randomlyfrom OAnshumali Shrivastava (COMP 640)Sketching29th August 20162 / 22

Bloom Filters Set UpA common Task: How to know whether some event occurred (before) ornot without storing the event information? The number of possible eventsare huge. The following list is from WikipediaAkamai web servers use Bloom filters to prevent ”one-hit-wonders”from being stored in its disk caches. One-hit-wonders are web objectsrequested by users just once.Google BigTable, Apache HBase and Apache Cassandra, andPostgresql use Bloom filters to reduce the disk lookups fornon-existent rows or columns. Avoiding costly disk lookupsconsiderably increases the performance of a database query operation.The Google Chrome web browser used to use a Bloom filter toidentify malicious URLs.The Squid Web Proxy Cache uses Bloom filters for cache digestsBitcoin uses Bloom filters to speed up wallet synchronization.many more.Anshumali Shrivastava (COMP 640)Sketching29th August 20163 / 22

The Bloom Filter Algorithm and AnalysisA Dynamic Data Structure of m bit arrays BPick k universal hash function hi : O {1, 2, ., m}i {1, 2, ., k}.Insert oj : Set all the bits B(hi (oj )) 1. i {1, 2, ., k}Query oj : If B(hi (oj )) 1 i {1, 2, ., k} RETURN True ELSEfalsePropertiesIf an item is present, the algorithm is always correct. No falsenegative.If an item is not present, the algorithm may return true with smallprobability.Cannot delete items easily.Analysis On-BoardAnshumali Shrivastava (COMP 640)Sketching29th August 20164 / 22

Generalized Bloom Filters: Count-Min SketchOn a network, a lot of events keep happening. Cannot afford to storeevent information.Bloom Filters: Keep track of whether an given event has alreadyhappened or not.Count Min Sketches (or Count Sketches): Keep track of thefrequency of the frequent events (heavy hitters).Instead of bits keep CountersUsually, to avoid collisions among different hashes, they are hashed intodifferent arrays. (Hence we get Matrix)Anshumali Shrivastava (COMP 640)Sketching29th August 20165 / 22

The Classical (Non-Adaptive) Approximate Counting:Setting:We are given a huge number of items (co-variate) i I to track overtime t {1, 2, ., T }. T can be large as well.We only see increments (i, t, v ), the increment v to item i at time t.Goal: In limited space (hopefully O(log I T )), we want toPoint Queries: Estimate the counts (increments) of item i at time t.Range Queries: Estimate the counts (increments) of item i duringthe given range [t1 , t2 ].Classical Sketching: Count-Sketch, Count-Min Sketch (CMS), LossyCounting, etc.Anshumali Shrivastava (COMP 640)Sketching29th August 20166 / 22

FrequencyIdea: Power Law Everywhere in PracticeEventsExample: We want to cache answers to frequent queries on a server.All queries are just too much to keep track of.How to identify very frequent queries? (Note, we cannot counteverything.)We dont even know which ones are frequent, we only see somequeries within a given time set.Anshumali Shrivastava (COMP 640)Sketching29th August 20167 / 22

Counting Heavy Hitters on Data StreamsReal Problem: How to identify significant event (frequent) withouthaving to count all of them. (sub-linear)Anshumali Shrivastava (COMP 640)Sketching29th August 20168 / 22

Counting Heavy Hitters on Data StreamsReal Problem: How to identify significant event (frequent) withouthaving to count all of them. (sub-linear)Classical Formalism (Turnstile Model)Assume we have a very long vector v (Dim D), we cannot materialize.We only see increments to its coordinates. E.g. co-ordinate i isincremented by 10 at time t.Goal: Find s heaviest coordinate, using space k DAnshumali Shrivastava (COMP 640)Sketching29th August 20168 / 22

Counting Heavy Hitters on Data StreamsReal Problem: How to identify significant event (frequent) withouthaving to count all of them. (sub-linear)Classical Formalism (Turnstile Model)Assume we have a very long vector v (Dim D), we cannot materialize.We only see increments to its coordinates. E.g. co-ordinate i isincremented by 10 at time t.Goal: Find s heaviest coordinate, using space k DSeems Hopeless !Anshumali Shrivastava (COMP 640)Sketching29th August 20168 / 22

Uncertainty is the Refuge of Hope.—Henri Frederic Amiel (1821-81)Anshumali Shrivastava (COMP 640)Sketching29th August 20169 / 22

Basic Idea behind Sketching.Randomly assign items to a small number of counters.It works! AMS 85, Moody 89, Charikar 99, MuthuKrishnana 02, etc.If no collisions, counts exact.iH(i)Use Random Hash FunctionHandling Time:Treat each pair (i, t) (item, time) as different item.Hash pairs (i, t), instead of just items.Time only increases the number of items to I T .Anshumali Shrivastava (COMP 640)Sketching29th August 201610 / 22

What happens during Collision ?The Good We typically care about heavy hitters.Anshumali Shrivastava (COMP 640)Sketching29th August 2016 11 / 22

What happens during Collision ?The GoodTheIrrelevant We typically care about heavy hitters.Anshumali Shrivastava (COMP 640)Sketching29th August 2016 11 / 22

What happens during Collision ?The GoodTheIrrelevantTheUnlucky We typically care about heavy hitters.Anshumali Shrivastava (COMP 640)Sketching29th August 2016 11 / 22

Maximizing Luck : Count-Min Sketch (CMS)Idea:We always overestimate, if unlucky, by a lot.Repeat independently d times and take minimum of all overestimates.Unless unlucky all d times, it will work. (d log 1δ , w 1 )Theoretical Guaranteec ĉ c MT with probability 1 δ, where MT is sum of allcounts in the stream.Space O(log I T )Anshumali Shrivastava (COMP 640)Sketching29th August 201612 / 22

New Requirement: Time AdaptabilityIn Practice:Recent trends are more important.A burst in the number of clicks in the past few minutes moreinformative than similar burst last month.Expectation: Time Adaptive Counting.Classical sketches do not take temporal effect into consideration.Smart Tradeoff: Given the same space, trade errors of recent countswith that of older ones.Like our memory, forget slowly.Anshumali Shrivastava (COMP 640)Sketching29th August 201613 / 22

Existing Solution: Hokusai1t T (𝑨𝑻 )t T-1 (𝑨𝑻 𝟏 )t T-2 (𝑨𝑻 𝟐 )t T-3 (𝑨𝑻 𝟑 )t T-4 (𝑨𝑻 𝟒 )t T-5 (𝑨𝑻 𝟓 )t T-6 (𝑨𝑻 𝟔 )Idea: Disproportionate allocation over time.Accuracy of CMS dependent on memory allocated.More space for recent sketches and less for older.Keep a CMS sketch for every time. Shrink sketch size on fly.Clever Idea: Exploit Rollover.1Matusevych, Smola and Ahmad 2012Anshumali Shrivastava (COMP 640)Sketching29th August 201614 / 22

Existing Solution: Hokusai1t T (𝑨𝑻 )t T-1 (𝑨𝑻 𝟏 )t T-2 (𝑨𝑻 𝟐 )t T-3 (𝑨𝑻 𝟑 )t T-4 (𝑨𝑻 𝟒 )t T-5 (𝑨𝑻 𝟓 )t T-6 (𝑨𝑻 𝟔 )Idea: Disproportionate allocation over time.Accuracy of CMS dependent on memory allocated.More space for recent sketches and less for older.Keep a CMS sketch for every time. Shrink sketch size on fly.Clever Idea: Exploit Rollover.1Matusevych, Smola and Ahmad 2012Anshumali Shrivastava (COMP 640)Sketching29th August 201614 / 22

Existing Solution: Hokusai1t T (𝑨𝑻 )t T-1 (𝑨𝑻 𝟏 )t T-2 (𝑨𝑻 𝟐 )t T-3 (𝑨𝑻 𝟑 )t T-4 (𝑨𝑻 𝟒 )t T-5 (𝑨𝑻 𝟓 )t T-6 (𝑨𝑻 𝟔 )Idea: Disproportionate allocation over time.Accuracy of CMS dependent on memory allocated.More space for recent sketches and less for older.Keep a CMS sketch for every time. Shrink sketch size on fly.Clever Idea: Exploit Rollover.1Matusevych, Smola and Ahmad 2012Anshumali Shrivastava (COMP 640)Sketching29th August 201614 / 22

Existing Solution: Hokusai1t T (𝑨𝑻 )t T-1 (𝑨𝑻 𝟏 )t T-2 (𝑨𝑻 𝟐 )t T-3 (𝑨𝑻 𝟑 )t T-4 (𝑨𝑻 𝟒 )t T-5 (𝑨𝑻 𝟓 )t T-6 (𝑨𝑻 𝟔 )Idea: Disproportionate allocation over time.Accuracy of CMS dependent on memory allocated.More space for recent sketches and less for older.Keep a CMS sketch for every time. Shrink sketch size on fly.Clever Idea: Exploit Rollover.1Matusevych, Smola and Ahmad 2012Anshumali Shrivastava (COMP 640)Sketching29th August 201614 / 22

Problems with HokusaiIssues:Discontinuity. If time t is empty, we still have to shrink sketch size forolder times.O(T) memory. One for each t.Shrinking overhead. Shrink log t sketches for every transition from tto t 1.No flexibility.Anshumali Shrivastava (COMP 640)Sketching29th August 201615 / 22

Detour: Dolby Noise Reduction (1960s)High Level ViewIn digital recording, the music signal compete with tape hiss(background noise).if Signal to Noise (SNR) ratio is high, the recording is noise free.While recording the frequencies in the music is artificially inflated(Pre-Emphasis).During playback a reverse transformation is applied which cancelspre-emphasis. (De-Emphasis)Overall effect of noise is minimized.Anshumali Shrivastava (COMP 640)Sketching29th August 201616 / 22

Proposal: (Adaptive)Ada-SketchesAnalogy with Dolby Noise Reduction:Sketches preserves heavier counts more accurately.Artificially inflate recent counts (Pre-emphasis).Inflated counts will be preserved with less error.Deflate by exact same amount during estimation. (De-emphasis)Anshumali Shrivastava (COMP 640)Sketching29th August 201617 / 22

Proposal: (Adaptive)Ada-SketchesAnalogy with Dolby Noise Reduction:Sketches preserves heavier counts more accurately.Artificially inflate recent counts (Pre-emphasis).Inflated counts will be preserved with less error.Deflate by exact same amount during estimation. (De-emphasis)Multiplyby 𝒇(𝒕)DataStreamInsertQuerySKETCHDivide byapt 𝒇(𝒕)RESULTDe-emphasisPre-emphasisProposalLet f (t) be any (pre-defined) monotonically increasing sequence.(f (t) can be chosen wisely)Multiply the count of (i, t) with f (t) and then add to the sketch.While querying (i,t), get the estimate and divide by f (t)Anshumali Shrivastava (COMP 640)Sketching29th August 201617 / 22

Why it works ?ObservationIf no collision then exact.During collision, errors or recent counts decrease due to greaterde-emphasis.ErrorVanilla Anshumali Shrivastava (COMP 640)Sketching29th August 201618 / 22

Why it works ?ObservationIf no collision then exact.During collision, errors or recent counts decrease due to greaterde-emphasis.Adaptive Pre-Emphasis Anshumali Shrivastava (COMP 640)Sketching29th August 201618 / 22

Why it works ?ObservationIf no collision then exact.During collision, errors or recent counts decrease due to greaterde-emphasis.ErrorAdaptive De-EmphasisPre-Emphasis Anshumali Shrivastava (COMP 640)Sketching29th August 201618 / 22

AdvantagesNo Discontinuity. If time t is empty, no addition, no extra collisions,no extra errors.O(log I T ) memory just like CMS.No shrinking overhead. Minimum modification to CMS. (StrictGeneralization)Provable Time Adaptive GuaranteesTheoremFor w d e e and d log 1δ , given any (i, t) we havecit cbit cit β twith probability 1 δ. Here β t monotonically decreasing with t.Anshumali Shrivastava (COMP 640)qPTqMT2t 0 0 (f (tf (t)Sketching0 ))2is the time adaptive factor29th August 201619 / 22

More.Works with any Sketching AlgorithmAdaptive Count Sketches, Adaptive Lossy Counting etc.Provable Time Adaptive Guarantees for all of them.Anshumali Shrivastava (COMP 640)Sketching29th August 201620 / 22