1、1,Improvements to A-Priori,Bloom Filters Park-Chen-Yu Algorithm Multistage Algorithm Approximate Algorithms Compacting Results,2,Aside: Hash-Based Filtering,Simple problem: I have a set S of one billion strings of length 10. I want to scan a larger file F of strings and output those that are in S. I

2、 have 1GB of main memory. So I cant afford to store S in memory.,3,Solution (1),Create a bit array of 8 billion bits, initially all 0s. Choose a hash function h with range 0, 8*109), and hash each member of S to one of the bits, which is then set to 1. Filter the file F by hashing each string and ou

3、tputting only those that hash to a 1.,4,Solution (2),Filter,File F,0010001011000,h,5,Solution (3),As at most 1/8 of the bit array is 1, only 1/8th of the strings not in S get through to the output. If a string is in S, it surely hashes to a 1, so it always gets through. Can repeat with another hash

4、function and bit array to reduce the false positives by another factor of 8.,6,Solution Summary,Each filter step costs one pass through the remaining file F and reduces the fraction of false positives by a factor of 8. Actually 1/(1-e -1/8). Repeat passes until few false positives. Either accept som

5、e errors, or check the remaining strings. e.g., divide surviving F into chunks that fit in memory and make a pass though S for each.,7,Aside: Throwing Darts,A number of times we are going to need to deal with the problem: If we throw k darts into n equally likely targets, what is the probability that a target gets at least one dart? Example: targets = bits, darts = hash values of elements.,8,Throwing Darts (2),9,Throwing Darts (3),If k s.,31,All (Or Most) Frequent Itemsets In 0). Stores not only frequent information, but exact counts.,49,Example: Maximal/Closed,Count Maximal (