1、Improvements to A-PrioriBloom FiltersPark-Chen-Yu AlgorithmMultistage AlgorithmApproximate AlgorithmsCompacting Results1Aside: Hash-Based FilteringuSimple problem: I have a set S of one billion strings of length 10.uI want to scan a larger file F of strings and output those that are in S.uI have 1GB
2、 of main memory.wSo I cant afford to store S in memory.2Solution (1)uCreate a bit array of 8 billion bits, initially all 0s.uChoose 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.uFilter the file F by hashing each string and outputting on
3、ly those that hash to a 1.3Solution (2)FilterFile F0010001011000To output;may be in S.hDrop; surelynot in S.4Solution (3)uAs at most 1/8 of the bit array is 1, only 1/8th of the strings not in S get through to the output.uIf a string is in S, it surely hashes to a 1, so it always gets through.uCan r
4、epeat with another hash function and bit array to reduce the false positives by another factor of 8.5Solution SummaryuEach filter step costs one pass through the remaining file F and reduces the fraction of false positives by a factor of 8.wActually 1/(1-e -1/8).uRepeat passes until few false positi
5、ves.uEither accept some errors, or check the remaining strings.we.g., divide surviving F into chunks that fit in memory and make a pass though S for each.6Aside: Throwing DartsuA 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
6、 the probability that a target gets at least one dart?uExample: targets = bits, darts = hash values of elements.7Throwing Darts (2)(1 1/n)Probablitytarget not hitby one dartk1 -Probability atleast one darthits targetn( /n)EquivalentEquals 1/eas n 1 ek/n8Throwing Darts (3)uIf k n, then e-k/n can be a
7、pproximated by the first two terms of its Taylor expansion: 1 k/n.uExample: 109 darts, 8*109 targets.wTrue value: 1 e-1/8 = .1175.wApproximation: 1 (1 1/8) = .125.9Improvement: Superimposed Codes (Bloom Filters)uWe could use two hash functions, and hash each member of S to two bits of the bit array.uNow, around of the array is 1s.uBut we transmit a string in F to the output only if both its bits are 1, i.e., only 1/16th are false positives.wActually (1-e -1/4)2 = 0.0493.10
