# The Bloom Filter > A working engineer's introduction to the Bloom filter. It starts with the membership problem when the set of seen items is far too large to keep, then builds the structure a bit at a time: one row of bits, k hash functions, and three items inserted so that two of them end up sharing a bit. A fourth item that nobody inserted then comes back as present, because three unrelated items happened to cover its pattern. From there the false positive rate is derived from the number of hash functions, the size of the bit array and the number of insertions, and the trade off is drawn as a curve with a visible optimum rather than quoted. It closes on why a bit may never be cleared, and on a crawler that keeps a billion visited URLs in a gigabyte and a quarter. - Canonical watch page: [The Bloom Filter](https://academa.ai/lectures/bloom-filters) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-28T18:45:02.106Z - Updated: 2026-08-28T18:45:02.106Z - Duration: PT857S (14 minutes 17 seconds) - Chapters: 5 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TX4X2AEBCN974JH81ZCHZ/0/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TX4X2AEBCN974JH81ZCHZ/0/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TX4X2AEBCN974JH81ZCHZ/0/dark/poster.jpg) ## Description How a Bloom filter tests membership in a few bits per item, why false positives happen, how to pick k, and why deletion is forbidden. ## Chapters - [00:00–02:5.445 · A Set You Cannot Afford to Keep](https://academa.ai/lectures/bloom-filters?t=0) - [02:5.445–05:5.848 · Setting the Bits](https://academa.ai/lectures/bloom-filters?t=125.44514583333334) - [05:5.848–08:21.557 · The False Positive](https://academa.ai/lectures/bloom-filters?t=305.84783333333337) - [08:21.557–11:24.416 · Choosing the Hash Functions](https://academa.ai/lectures/bloom-filters?t=501.55745833333333) - [11:24.416–14:17 · No Deletions, and One Real Use](https://academa.ai/lectures/bloom-filters?t=684.4156458333333) ## Transcript ### [00:00 · A Set You Cannot Afford to Keep](https://academa.ai/lectures/bloom-filters?t=0) Here is a problem that turns up in almost every large system. Items arrive one at a time, and for each one you have to answer a single question. Have I seen this one before? A crawler asks it of every link it discovers, and a cache asks it of every key. So here is the question this lecture answers. Have I seen this item before, when the set of items I have seen is far too large to keep? The second half of that sentence is where all of the difficulty lives. The obvious answer is to keep the set. Every item you have seen goes into a hash set, and every new one gets looked up. Across the bottom here is n, the number of items, counted in millions. Up the side is memory, in gigabytes. URLs are not small. Sixty four bytes each is a kind estimate, and this red line is what that costs you. A billion of them is sixty four gigabytes, and it is a straight line, because an exact set charges you for every item, forever. The dashed line is the memory the machine actually has. Eight gigabytes. The red line crosses it here, at about a hundred and twenty five million URLs, and past that point the structure does not fit and the process dies. The blue line is where we are going. The same billion URLs, about ten bits each, and the whole structure is a gigabyte and a quarter. Fifty times smaller, and it never stores a single URL. You do not get that for free. What you give up is certainty, in one direction only. A Bloom filter answers two ways: definitely not in the set, or probably in the set. The second of those is sometimes wrong. Two things to hold on to before we build it. It never stores the items, so you can never ask it what is in there. And the mistakes only ever go one way. It will never tell you an item is absent when you did in fact insert it. ### [02:5.445 · Setting the Bits](https://academa.ai/lectures/bloom-filters?t=125.44514583333334) So we are not going to store the items. We are going to store a fixed row of bits, and nothing else. Here is one: sixteen bits, numbered zero to fifteen, and every single one of them is zero. Call the length m. In a real filter m is not sixteen, it is a few billion. Sixteen is a size you can see. And notice what is missing here. There is no list of items anywhere in this picture, no copy of anything that was ever inserted. There are only bits. So take an item. Call it x. We hash it, not once, but k times, with k independent hash functions. Here k is three, and the first of them hands back position two. The second gives seven, and the third gives eleven. Three positions, three bits, and we set all three of them to one. That is the whole of the insert operation. Notice what did not happen there. We did not store x. We did not store a hash of x, or a pointer to x, or how long it was. Three bits went from zero to one, and the item itself is gone. Insert a second item. Its three hashes come out four, seven, and thirteen, so we set those. And look at position seven. It was already a one, set by the first item, and it stays a one. The row has no idea that two different items are now leaning on that single bit. Hold on to that. A third item, and its positions are one, nine, and fourteen. Three items are in the filter now, and eight of the sixteen bits are ones. That is the entire state. So now the other half of the job. How do you ask a question? To test an item you hash it exactly the same way, and you look at the k bits it names. Here is the second item again. Four, seven, thirteen. All three of them are ones. So the filter says: probably present. And it is right, we did insert that one. But look at what it actually checked. It never compared the item to anything at all. It read three bits. Now an item that was never inserted. Its positions come out zero, nine, and fourteen. The bit at nine is a one, the bit at fourteen is a one, and the bit at zero is not. And that settles it. If this item had ever been inserted, every one of its bits would have been set at that moment, and bits in this row are never cleared. A single zero anywhere is proof of absence. Definitely not in the set. That answer is exact, and it is the one guarantee the structure gives you. It is worth more than it sounds. Most of the time the thing you are asking about really is new, and you get told so for three bit lookups and no disk at all. ### [05:5.848 · The False Positive](https://academa.ai/lectures/bloom-filters?t=305.84783333333337) Here is that same row, with those same three items in it, and now I am going to ask about an item that nobody ever inserted. Call it v. Its three positions come out two, four, and nine. Two is a one. The first item set it. Four is a one. The second item set that. Nine is a one, and the third item set that. So all k bits are ones, and the filter says: probably present. And it is wrong. No item set that pattern. Three different items each happened to set one of its bits, and between them they covered it. That is a false positive. It is not a bug, and there is no clever fix for it. It is what you bought when you decided to store bits instead of items. The bits do not remember who set them. What you can do is work out how often it happens, before you ship anything, and then choose how often you are willing to let it happen. So let us count it. Fix one bit in the row and follow it. Call P nought the chance that this bit is still a zero, and P one the chance that something has set it. A single hash function picks a position uniformly out of m, so it misses our bit with probability one minus one over m. Inserting one item runs k hashes. Inserting n items runs k times n of them, and if the hash functions are independent our bit survives every one of them, with probability one minus one over m, all raised to the power k n. That form is awkward to think with, so use the standard approximation. When m is large it is very close to e to the minus k n over m. Same number, and far easier to see what it does. Turn it around. The chance that a given bit has been set is one minus that. And this curve is exactly that number, for our sixteen bit row with three hash functions, as n climbs. With three items in, the formula says about forty three percent of the bits are ones. We counted eight out of sixteen, which is fifty. With only sixteen bits that is the sort of luck you get. Now push n up to twelve. Nearly ninety percent of the row is ones, and at that point almost any pattern you ask about is already covered by something. The false positive rate climbs with n, and this is the reason why. So now the query itself. An item that was never inserted names k bits. Each one is a one with probability P one, and if we treat those as independent, all k of them are ones with probability P one to the k. There it is. The false positive rate, epsilon, is one minus e to the minus k n over m, all raised to the k. Read the exponent as the total number of bits you have set, k of them for each of n items, divided by the room you gave them to spread out in. Read the rest of it the way an engineer reads it. n is handed to you by the problem. m is what you are willing to pay for. And k is the one you actually get to choose, and it is not at all obvious which way to push it. ### [08:21.557 · Choosing the Hash Functions](https://academa.ai/lectures/bloom-filters?t=501.55745833333333) So, choosing k. Fix the budget at ten bits an item, which is the number you will see quoted everywhere, and the rate depends on k and nothing else. Here it is, plotted against the number of hash functions. With one hash function, each item sets a single bit, and the rate is about nine and a half percent. Nearly one query in ten comes back wrong. Two hash functions: three point three percent. Three: one point seven. Every extra hash function is another bit that has to be a one by accident, and that gets rapidly less likely. Five hash functions gets you under one percent. Seven gets you eight in a thousand, and that is the best this budget can do. Now watch what happens if you keep going. Ten hash functions is worse than seven. Fourteen is worse than three. The curve turns around and climbs back up. And the reason is sitting in the formula. Every extra hash function is one more bit a query has to match, which helps you. But it is also one more bit set on every insert, so the exponent grows and the row fills up faster, which hurts you. Past a point the second effect wins. The minimum is where those two balance, and it lands somewhere clean. The best k is m over n times the natural log of two, which for ten bits an item is six point nine. So you use seven. And there is a check you can run in production. At the optimal k the row ends up with almost exactly half its bits set. Half ones, half zeros. If your filter is much fuller than half, you are running too many hash functions. Which leaves the budget itself. Substitute that optimal k back into the rate, and the whole expression collapses into one number raised to the bits per item. About zero point six two, to the power m over n. So here is the curve an engineer actually wants. Bits per item across the bottom, false positive rate up the side. At eight bits an item, two percent. At ten bits, eight in a thousand. At fourteen, about one in a thousand. At twenty bits an item you are down to seven in a hundred thousand, and you are still using less than three bytes a URL. Every extra bit per item multiplies the error by roughly zero point six two. That is what makes ten the number people quote. It is the first place the curve is properly flat, and it is under one percent. And look at the shape of it. Going from three bits an item to eight is cheap, and it buys you an enormous amount. After that it gets expensive, because you are paying linearly for an error that is shrinking exponentially. ### [11:24.416 · No Deletions, and One Real Use](https://academa.ai/lectures/bloom-filters?t=684.4156458333333) One more property, and it is the one that catches people out. You cannot remove anything from a Bloom filter. Here is why, on the row we already have, with the same three items in it. Suppose we want to take the first item back out. Its bits were two, seven, and eleven, so the obvious move is to clear those three. Now ask about the second item, which is still very much in the set. Its bits are four, seven, and thirteen. Four is a one. Thirteen is a one. And seven is now a zero, because we just cleared it. So the filter says definitely absent, about an item that is definitely present. That is a false negative, and it is the single answer this structure promised you it would never get wrong. The bit at seven was never the first item's bit to give back. It was shared, and nothing in the row records how many items are leaning on it. So we put it back, and we do not do that again. Which gives us the rule, and it is worth stating plainly. A Bloom filter supports insert, and it supports query, and it does not support delete. If the things you are tracking ever go away again, this is the wrong structure for them. There is a variant that fixes it. Replace each bit with a small counter, increment on insert, decrement on delete, and now the shared position knows that two items are leaning on it. You pay for that. Four bit counters make the whole thing four times bigger, which was most of the reason you reached for a Bloom filter in the first place. So where does this earn its keep? A crawler is the clean case. You pull a URL off the frontier, and before you spend a network round trip on it, you ask whether you have fetched it already. The filter answers in the two ways we know. Definitely new, and you fetch it. Probably seen, and you drop it on the floor. A billion URLs at ten bits each is a gigabyte and a quarter, which fits in memory on any machine you would run a crawler on. The exact set was sixty four gigabytes, and a disk seek for every link on every page. At seven hash functions the rate is eight in a thousand, so about eight million URLs out of a billion get reported as seen when they never were, and never get fetched. On a web that size, that is a rounding error in your coverage. And notice which way the errors fall. What cannot happen is a page you have already fetched coming back as new. That is the one that puts a crawler in a loop, and it is precisely the answer the filter is exact about. So that is the whole structure. Bits instead of items. k hash functions instead of a comparison. A false positive rate you can compute before you ship. And no deletions, ever. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TX4X2AEBCN974JH81ZCHZ/0/semantic.json) Record version: 1. Render attempt: 0. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [A Set You Cannot Afford to Keep](https://academa.ai/lectures/bloom-filters?t=0) Span: 00:00–02:5.445 (0s–125.44514583333334s). #### Objects - bloom\_line: a FunctionPlot \[blue\] labelled "upright("Bloom filter")" drawn in memory (function=\) - budget: a Line \[yellow\] labelled "upright("RAM")" drawn in memory (start=(0.0, 8.0), end=(1000.0, 8.0), dashed=True) - card: a Title that says "Data Structures for Systems — The Bloom Filter" - cost: a Table \[text\] that says "Structure $10^9$ URLs Exact hash set 64 GB Bloom filter 1.25 GB" (rows=(('Structure', '$10^9$ URLs'), ('Exact hash set', '64 GB'), ('B…, header=True) - exact\_line: a FunctionPlot \[red\] labelled "upright("exact set")" drawn in memory (function=\) - memory: an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0) - point: a Point \[yellow\] drawn in memory (location=(125.0, 8.0)) - point\_2: a Point \[yellow\] drawn in memory (location=(900.0, 1.125)) - promise: a Panel that says "A Bloom filter answers two ways: definitely not in the set, or probably in the set. It never stores the items themselves." - question: a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?" #### Beats ##### [00:00](https://academa.ai/lectures/bloom-filters?t=0) Narration: Here is a problem that turns up in almost every large system. Items arrive one at a time, and for each one you have to answer a single question. Have I seen this one before? A crawler asks it of every link it discovers, and a cache asks it of every key. Board: Empty. Actions: - [00:00](https://academa.ai/lectures/bloom-filters?t=0): card is shown on the screen, written out. - [00:1.5](https://academa.ai/lectures/bloom-filters?t=1.5): card: enter:write-left-to-right. - [00:17.322](https://academa.ai/lectures/bloom-filters?t=17.322): card is hidden from the screen — left the board. ##### [00:18.522](https://academa.ai/lectures/bloom-filters?t=18.522) Narration: So here is the question this lecture answers. Have I seen this item before, when the set of items I have seen is far too large to keep? The second half of that sentence is where all of the difficulty lives. Board: Unchanged from the preceding beat in this scene. Actions: - [00:19.695](https://academa.ai/lectures/bloom-filters?t=19.695): question is shown on the screen, written out. - [00:31.061](https://academa.ai/lectures/bloom-filters?t=31.0615): question moves to a new place on the board. ##### [00:31.661](https://academa.ai/lectures/bloom-filters?t=31.661499999999997) Narration: The obvious answer is to keep the set. Every item you have seen goes into a hash set, and every new one gets looked up. Across the bottom here is n, the number of items, counted in millions. Up the side is memory, in gigabytes. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?" Actions: - [00:31.661](https://academa.ai/lectures/bloom-filters?t=31.661499999999997): memory is shown on the screen, written out. ##### [00:47.702](https://academa.ai/lectures/bloom-filters?t=47.702) Narration: URLs are not small. Sixty four bytes each is a kind estimate, and this red line is what that costs you. A billion of them is sixty four gigabytes, and it is a straight line, because an exact set charges you for every item, forever. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?"; memory — an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0) Actions: - [00:53.275](https://academa.ai/lectures/bloom-filters?t=53.27499999999999): exact\_line is shown on the screen, drawn. - [00:55.876](https://academa.ai/lectures/bloom-filters?t=55.876): memory moves to a new place on the board. - [00:55.876](https://academa.ai/lectures/bloom-filters?t=55.876): cost is shown on the screen, written out. - [00:56.276](https://academa.ai/lectures/bloom-filters?t=56.275999999999996): cost is shown on the screen, written out. ##### [01:4.302](https://academa.ai/lectures/bloom-filters?t=64.3015) Narration: The dashed line is the memory the machine actually has. Eight gigabytes. The red line crosses it here, at about a hundred and twenty five million URLs, and past that point the structure does not fit and the process dies. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?"; memory — an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0); exact\_line — a FunctionPlot \[red\] labelled "upright("exact set")" drawn in memory (function=\) Actions: - [01:4.893](https://academa.ai/lectures/bloom-filters?t=64.893): budget is shown on the screen, written out. - [01:11.581](https://academa.ai/lectures/bloom-filters?t=71.58100000000002): point is shown on the screen, grown. - [01:13.581](https://academa.ai/lectures/bloom-filters?t=73.58100000000002): point is hidden from the screen. ##### [01:20.575](https://academa.ai/lectures/bloom-filters?t=80.575) Narration: The blue line is where we are going. The same billion URLs, about ten bits each, and the whole structure is a gigabyte and a quarter. Fifty times smaller, and it never stores a single URL. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?"; memory — an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0); exact\_line — a FunctionPlot \[red\] labelled "upright("exact set")" drawn in memory (function=\); budget — a Line \[yellow\] labelled "upright("RAM")" drawn in memory (start=(0.0, 8.0), end=(1000.0, 8.0), dashed=True) Actions: - [01:21.306](https://academa.ai/lectures/bloom-filters?t=81.30600000000001): bloom\_line is shown on the screen, drawn. - [01:28.946](https://academa.ai/lectures/bloom-filters?t=88.94600000000001): cost is shown on the screen, written out. ##### [01:35.014](https://academa.ai/lectures/bloom-filters?t=95.01400000000001) Narration: You do not get that for free. What you give up is certainty, in one direction only. A Bloom filter answers two ways: definitely not in the set, or probably in the set. The second of those is sometimes wrong. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?"; memory — an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0); exact\_line — a FunctionPlot \[red\] labelled "upright("exact set")" drawn in memory (function=\); budget — a Line \[yellow\] labelled "upright("RAM")" drawn in memory (start=(0.0, 8.0), end=(1000.0, 8.0), dashed=True); bloom\_line — a FunctionPlot \[blue\] labelled "upright("Bloom filter")" drawn in memory (function=\) Actions: - [01:42.479](https://academa.ai/lectures/bloom-filters?t=102.47900000000001): promise is shown on the screen, written out. ##### [01:51.032](https://academa.ai/lectures/bloom-filters?t=111.03200000000001) Narration: Two things to hold on to before we build it. It never stores the items, so you can never ask it what is in there. And the mistakes only ever go one way. It will never tell you an item is absent when you did in fact insert it. Board: question — a Panel that says "Have I seen this item before, when the set of items I have seen is far too large to keep?"; promise — a Panel that says "A Bloom filter answers two ways: definitely not in the set, or probably in the set. It never stores the items themselves."; memory — an Axes (x\_range=(0.0, 1000.0), y\_range=(0.0, 70.0), x\_ticks\_every=200.0); exact\_line — a FunctionPlot \[red\] labelled "upright("exact set")" drawn in memory (function=\); budget — a Line \[yellow\] labelled "upright("RAM")" drawn in memory (start=(0.0, 8.0), end=(1000.0, 8.0), dashed=True); bloom\_line — a FunctionPlot \[blue\] labelled "upright("Bloom filter")" drawn in memory (function=\) Actions: - [01:55.002](https://academa.ai/lectures/bloom-filters?t=115.00200000000001): promise (the "never stores the items" part) is emphasized. - [01:58.392](https://academa.ai/lectures/bloom-filters?t=118.39200000000001): promise (the "never stores the items" part) is no longer emphasized. - [02:1.991](https://academa.ai/lectures/bloom-filters?t=121.99100000000001): point\_2 is shown on the screen, grown. - [02:3.991](https://academa.ai/lectures/bloom-filters?t=123.99100000000001): point\_2 is hidden from the screen. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): cost is hidden from the screen — left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): memory is hidden from the screen — left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): exact\_line is hidden from the screen — memory left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): budget is hidden from the screen — memory left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): bloom\_line is hidden from the screen — memory left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): promise is hidden from the screen — left the board. - [02:4.403](https://academa.ai/lectures/bloom-filters?t=124.40347916666667): question is hidden from the screen — left the board. ### Scene 2: [Setting the Bits](https://academa.ai/lectures/bloom-filters?t=125.44514583333334) Span: 02:5.445–05:5.848 (125.44514583333334s–305.84783333333337s). #### Objects - bits: a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)) - cells: a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False) - cells\_10: a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False) - cells\_11: a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False) - cells\_12: a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False) - cells\_13: a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False) - cells\_14: a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False) - cells\_15: a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False) - cells\_16: a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False) - cells\_2: a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False) - cells\_3: a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False) - cells\_4: a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False) - cells\_5: a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False) - cells\_6: a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False) - cells\_7: a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False) - cells\_8: a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False) - cells\_9: a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False) - h1: a Math \[text\] that says "$h\_1(x) = 2$" - h2: a Math \[text\] that says "$h\_2(x) = 7$" - h3: a Math \[text\] that says "$h\_3(x) = 11$" - head\_array: a Heading that says "The Whole Data Structure" - head\_insert: a Heading that says "Inserting an Item" - head\_query: a Heading that says "Asking a Question" - ones: a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75) - ones\_2: a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75) - ones\_3: a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75) - ones\_4: a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75) - ones\_5: a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75) - ones\_6: a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75) - ones\_7: a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75) - ones\_8: a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75) - point: a Point \[yellow\] drawn in bits (location=(3.5, 0.5)) - point\_10: a Point \[yellow\] drawn in bits (location=(9.5, 0.5)) - point\_11: a Point \[yellow\] drawn in bits (location=(11.5, 0.5)) - point\_12: a Point \[yellow\] drawn in bits (location=(13.5, 0.5)) - point\_13: a Point \[yellow\] drawn in bits (location=(14.5, 0.5)) - point\_2: a Point \[yellow\] drawn in bits (location=(11.5, 0.5)) - point\_3: a Point \[yellow\] drawn in bits (location=(2.5, 0.5)) - point\_4: a Point \[yellow\] drawn in bits (location=(7.5, 0.5)) - point\_5: a Point \[yellow\] drawn in bits (location=(11.5, 0.5)) - point\_6: a Point \[yellow\] drawn in bits (location=(1.5, 0.5)) - point\_7: a Point \[yellow\] drawn in bits (location=(2.5, 0.5)) - point\_8: a Point \[yellow\] drawn in bits (location=(4.5, 0.5)) - point\_9: a Point \[yellow\] drawn in bits (location=(7.5, 0.5)) - tags: a Math \[gray\] that says "$0$" drawn in bits - tags\_10: a Math \[gray\] that says "$9$" drawn in bits - tags\_11: a Math \[gray\] that says "$10$" drawn in bits - tags\_12: a Math \[gray\] that says "$11$" drawn in bits - tags\_13: a Math \[gray\] that says "$12$" drawn in bits - tags\_14: a Math \[gray\] that says "$13$" drawn in bits - tags\_15: a Math \[gray\] that says "$14$" drawn in bits - tags\_16: a Math \[gray\] that says "$15$" drawn in bits - tags\_2: a Math \[gray\] that says "$1$" drawn in bits - tags\_3: a Math \[gray\] that says "$2$" drawn in bits - tags\_4: a Math \[gray\] that says "$3$" drawn in bits - tags\_5: a Math \[gray\] that says "$4$" drawn in bits - tags\_6: a Math \[gray\] that says "$5$" drawn in bits - tags\_7: a Math \[gray\] that says "$6$" drawn in bits - tags\_8: a Math \[gray\] that says "$7$" drawn in bits - tags\_9: a Math \[gray\] that says "$8$" drawn in bits - verdict: a Math \[text\] that says "$upright("probably present")$" #### Beats ##### [02:5.445](https://academa.ai/lectures/bloom-filters?t=125.44514583333334) Narration: So we are not going to store the items. We are going to store a fixed row of bits, and nothing else. Here is one: sixteen bits, numbered zero to fifteen, and every single one of them is zero. Call the length m. Board: Empty. Actions: - [02:5.445](https://academa.ai/lectures/bloom-filters?t=125.44514583333334): head\_array is shown on the screen, written out. - [02:5.445](https://academa.ai/lectures/bloom-filters?t=125.44514583333334): bits is shown on the screen, written out. - [02:9.3](https://academa.ai/lectures/bloom-filters?t=129.30014583333335): cells is shown on the screen, written out. - [02:9.35](https://academa.ai/lectures/bloom-filters?t=129.35014583333333): cells\_2 is shown on the screen, written out. - [02:9.4](https://academa.ai/lectures/bloom-filters?t=129.40014583333334): cells\_3 is shown on the screen, written out. - [02:9.45](https://academa.ai/lectures/bloom-filters?t=129.45014583333335): cells\_4 is shown on the screen, written out. - [02:9.5](https://academa.ai/lectures/bloom-filters?t=129.50014583333333): cells\_5 is shown on the screen, written out. - [02:9.55](https://academa.ai/lectures/bloom-filters?t=129.55014583333335): cells\_6 is shown on the screen, written out. - [02:9.6](https://academa.ai/lectures/bloom-filters?t=129.60014583333333): cells\_7 is shown on the screen, written out. - [02:9.65](https://academa.ai/lectures/bloom-filters?t=129.65014583333334): cells\_8 is shown on the screen, written out. - [02:9.7](https://academa.ai/lectures/bloom-filters?t=129.70014583333335): cells\_9 is shown on the screen, written out. - [02:9.75](https://academa.ai/lectures/bloom-filters?t=129.75014583333333): cells\_10 is shown on the screen, written out. - [02:9.8](https://academa.ai/lectures/bloom-filters?t=129.80014583333335): cells\_11 is shown on the screen, written out. - [02:9.85](https://academa.ai/lectures/bloom-filters?t=129.85014583333333): cells\_12 is shown on the screen, written out. - [02:9.9](https://academa.ai/lectures/bloom-filters?t=129.90014583333334): cells\_13 is shown on the screen, written out. - [02:9.95](https://academa.ai/lectures/bloom-filters?t=129.95014583333335): cells\_14 is shown on the screen, written out. - [02:10](https://academa.ai/lectures/bloom-filters?t=130.00014583333333): cells\_15 is shown on the screen, written out. - [02:10.05](https://academa.ai/lectures/bloom-filters?t=130.05014583333335): cells\_16 is shown on the screen, written out. - [02:14.431](https://academa.ai/lectures/bloom-filters?t=134.43114583333335): tags is shown on the screen, written out. - [02:14.471](https://academa.ai/lectures/bloom-filters?t=134.47114583333334): tags\_2 is shown on the screen, written out. - [02:14.511](https://academa.ai/lectures/bloom-filters?t=134.51114583333333): tags\_3 is shown on the screen, written out. - [02:14.551](https://academa.ai/lectures/bloom-filters?t=134.55114583333335): tags\_4 is shown on the screen, written out. - [02:14.591](https://academa.ai/lectures/bloom-filters?t=134.59114583333334): tags\_5 is shown on the screen, written out. - [02:14.631](https://academa.ai/lectures/bloom-filters?t=134.63114583333333): tags\_6 is shown on the screen, written out. - [02:14.671](https://academa.ai/lectures/bloom-filters?t=134.67114583333336): tags\_7 is shown on the screen, written out. - [02:14.711](https://academa.ai/lectures/bloom-filters?t=134.71114583333335): tags\_8 is shown on the screen, written out. - [02:14.751](https://academa.ai/lectures/bloom-filters?t=134.75114583333334): tags\_9 is shown on the screen, written out. - [02:14.791](https://academa.ai/lectures/bloom-filters?t=134.79114583333333): tags\_10 is shown on the screen, written out. - [02:14.831](https://academa.ai/lectures/bloom-filters?t=134.83114583333335): tags\_11 is shown on the screen, written out. - [02:14.871](https://academa.ai/lectures/bloom-filters?t=134.87114583333334): tags\_12 is shown on the screen, written out. - [02:14.911](https://academa.ai/lectures/bloom-filters?t=134.91114583333334): tags\_13 is shown on the screen, written out. - [02:14.951](https://academa.ai/lectures/bloom-filters?t=134.95114583333333): tags\_14 is shown on the screen, written out. - [02:14.991](https://academa.ai/lectures/bloom-filters?t=134.99114583333335): tags\_15 is shown on the screen, written out. - [02:15.031](https://academa.ai/lectures/bloom-filters?t=135.03114583333334): tags\_16 is shown on the screen, written out. ##### [02:21.08](https://academa.ai/lectures/bloom-filters?t=141.07964583333333) Narration: In a real filter m is not sixteen, it is a few billion. Sixteen is a size you can see. And notice what is missing here. There is no list of items anywhere in this picture, no copy of anything that was ever inserted. There are only bits. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); head\_array — a Heading that says "The Whole Data Structure"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [02:30.321](https://academa.ai/lectures/bloom-filters?t=150.32114583333333): point is shown on the screen, grown. - [02:32.318](https://academa.ai/lectures/bloom-filters?t=152.31814583333335): point\_2 is shown on the screen, grown. - [02:32.321](https://academa.ai/lectures/bloom-filters?t=152.32114583333333): point is hidden from the screen. - [02:34.318](https://academa.ai/lectures/bloom-filters?t=154.31814583333335): point\_2 is hidden from the screen. - [02:38.321](https://academa.ai/lectures/bloom-filters?t=158.32064583333334): bits moves to a new place on the board. - [02:38.321](https://academa.ai/lectures/bloom-filters?t=158.32064583333334): head\_array is hidden from the screen — left the board. ##### [02:38.921](https://academa.ai/lectures/bloom-filters?t=158.92064583333334) Narration: So take an item. Call it x. We hash it, not once, but k times, with k independent hash functions. Here k is three, and the first of them hands back position two. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [02:38.921](https://academa.ai/lectures/bloom-filters?t=158.92064583333334): head\_insert is shown on the screen, written out. - [02:49.95](https://academa.ai/lectures/bloom-filters?t=169.95014583333335): h1 is shown on the screen, written out. - [02:51.46](https://academa.ai/lectures/bloom-filters?t=171.46014583333334): ones is shown on the screen, faded in. ##### [02:52.931](https://academa.ai/lectures/bloom-filters?t=172.93064583333333) Narration: The second gives seven, and the third gives eleven. Three positions, three bits, and we set all three of them to one. That is the whole of the insert operation. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; head\_insert — a Heading that says "Inserting an Item"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75) Actions: - [02:54.045](https://academa.ai/lectures/bloom-filters?t=174.04514583333335): h2 is shown on the screen, written out. - [02:54.045](https://academa.ai/lectures/bloom-filters?t=174.04514583333335): ones\_2 is shown on the screen, faded in. - [02:55.589](https://academa.ai/lectures/bloom-filters?t=175.58914583333336): h3 is shown on the screen, written out. - [02:55.589](https://academa.ai/lectures/bloom-filters?t=175.58914583333336): ones\_3 is shown on the screen, faded in. ##### [03:4.525](https://academa.ai/lectures/bloom-filters?t=184.52514583333334) Narration: Notice what did not happen there. We did not store x. We did not store a hash of x, or a pointer to x, or how long it was. Three bits went from zero to one, and the item itself is gone. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; head\_insert — a Heading that says "Inserting an Item"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75) Actions: - [03:14.045](https://academa.ai/lectures/bloom-filters?t=194.04514583333332): point\_3 is shown on the screen, grown. - [03:14.37](https://academa.ai/lectures/bloom-filters?t=194.37014583333337): point\_4 is shown on the screen, grown. - [03:16.045](https://academa.ai/lectures/bloom-filters?t=196.04514583333332): point\_3 is hidden from the screen. - [03:16.37](https://academa.ai/lectures/bloom-filters?t=196.37014583333337): point\_4 is hidden from the screen. - [03:17.644](https://academa.ai/lectures/bloom-filters?t=197.64414583333337): point\_5 is shown on the screen, grown. ##### [03:18.999](https://academa.ai/lectures/bloom-filters?t=198.99864583333334) Narration: Insert a second item. Its three hashes come out four, seven, and thirteen, so we set those. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; head\_insert — a Heading that says "Inserting an Item"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); point\_5 — a Point \[yellow\] drawn in bits (location=(11.5, 0.5)) Actions: - [03:19.644](https://academa.ai/lectures/bloom-filters?t=199.64414583333337): point\_5 is hidden from the screen. - [03:22.47](https://academa.ai/lectures/bloom-filters?t=202.47014583333336): h1 becomes "$h\_1(y) = 4$". - [03:22.47](https://academa.ai/lectures/bloom-filters?t=202.47014583333336): ones\_4 is shown on the screen, faded in. - [03:23.05](https://academa.ai/lectures/bloom-filters?t=203.05014583333337): h2 becomes "$h\_2(y) = 7$". - [03:23.677](https://academa.ai/lectures/bloom-filters?t=203.67714583333336): h3 becomes "$h\_3(y) = 13$". - [03:23.677](https://academa.ai/lectures/bloom-filters?t=203.67714583333336): ones\_5 is shown on the screen, faded in. ##### [03:26.077](https://academa.ai/lectures/bloom-filters?t=206.07714583333336) Narration: And look at position seven. It was already a one, set by the first item, and it stays a one. The row has no idea that two different items are now leaning on that single bit. Hold on to that. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; head\_insert — a Heading that says "Inserting an Item"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75) Actions: - [03:27.389](https://academa.ai/lectures/bloom-filters?t=207.38914583333337): The point (7.5, 0.5) in bits is lit up. - [03:37.164](https://academa.ai/lectures/bloom-filters?t=217.16414583333335): bits: retire a lit point (unemphasize\_point). ##### [03:38.995](https://academa.ai/lectures/bloom-filters?t=218.99514583333337) Narration: A third item, and its positions are one, nine, and fourteen. Board: Unchanged from the preceding beat in this scene. Actions: - [03:41.108](https://academa.ai/lectures/bloom-filters?t=221.10814583333337): h1 becomes "$h\_1(z) = 1$". - [03:41.108](https://academa.ai/lectures/bloom-filters?t=221.10814583333337): ones\_6 is shown on the screen, faded in. - [03:41.607](https://academa.ai/lectures/bloom-filters?t=221.6071458333334): h2 becomes "$h\_2(z) = 9$". - [03:41.607](https://academa.ai/lectures/bloom-filters?t=221.6071458333334): ones\_7 is shown on the screen, faded in. - [03:42.176](https://academa.ai/lectures/bloom-filters?t=222.17614583333335): h3 becomes "$h\_3(z) = 14$". - [03:42.176](https://academa.ai/lectures/bloom-filters?t=222.17614583333335): ones\_8 is shown on the screen, faded in. ##### [03:43.717](https://academa.ai/lectures/bloom-filters?t=223.71714583333335) Narration: Three items are in the filter now, and eight of the sixteen bits are ones. That is the entire state. So now the other half of the job. How do you ask a question? Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; head\_insert — a Heading that says "Inserting an Item"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75) Actions: - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_6 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_7 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_8 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_9 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_10 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_11 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_12 is shown on the screen, grown. - [03:46.108](https://academa.ai/lectures/bloom-filters?t=226.10814583333337): point\_13 is shown on the screen, grown. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_6 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_7 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_8 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_9 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_10 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_11 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_12 is hidden from the screen. - [03:47.608](https://academa.ai/lectures/bloom-filters?t=227.60814583333337): point\_13 is hidden from the screen. - [03:55.431](https://academa.ai/lectures/bloom-filters?t=235.43114583333335): bits moves to a new place on the board. - [03:55.431](https://academa.ai/lectures/bloom-filters?t=235.43114583333335): h1 moves to a new place on the board. - [03:55.431](https://academa.ai/lectures/bloom-filters?t=235.43114583333335): h2 moves to a new place on the board. - [03:55.431](https://academa.ai/lectures/bloom-filters?t=235.43114583333335): h3 moves to a new place on the board. - [03:55.431](https://academa.ai/lectures/bloom-filters?t=235.43114583333335): head\_insert is hidden from the screen — left the board. ##### [03:56.031](https://academa.ai/lectures/bloom-filters?t=236.03114583333337) Narration: To test an item you hash it exactly the same way, and you look at the k bits it names. Here is the second item again. Four, seven, thirteen. All three of them are ones. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75) Actions: - [03:56.031](https://academa.ai/lectures/bloom-filters?t=236.03114583333337): head\_query is shown on the screen, written out. - [04:4.158](https://academa.ai/lectures/bloom-filters?t=244.15814583333338): h1 becomes "$h\_1(y) = 4$". - [04:4.158](https://academa.ai/lectures/bloom-filters?t=244.15814583333338): The point (4.5, 0.5) in bits is lit up. - [04:4.669](https://academa.ai/lectures/bloom-filters?t=244.66914583333335): h2 becomes "$h\_2(y) = 7$". - [04:4.669](https://academa.ai/lectures/bloom-filters?t=244.66914583333335): The point (7.5, 0.5) in bits is lit up. - [04:5.145](https://academa.ai/lectures/bloom-filters?t=245.14514583333334): h3 becomes "$h\_3(y) = 13$". - [04:5.145](https://academa.ai/lectures/bloom-filters?t=245.14514583333334): The point (13.5, 0.5) in bits is lit up. ##### [04:9.089](https://academa.ai/lectures/bloom-filters?t=249.08864583333337) Narration: So the filter says: probably present. And it is right, we did insert that one. But look at what it actually checked. It never compared the item to anything at all. It read three bits. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); head\_query — a Heading that says "Asking a Question" Actions: - [04:10.9](https://academa.ai/lectures/bloom-filters?t=250.90014583333337): verdict is shown on the screen, written out. ##### [04:22.541](https://academa.ai/lectures/bloom-filters?t=262.5406458333334) Narration: Now an item that was never inserted. Its positions come out zero, nine, and fourteen. The bit at nine is a one, the bit at fourteen is a one, and the bit at zero is not. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits; h1 — a Math \[text\] that says "$h\_1(x) = 2$"; h2 — a Math \[text\] that says "$h\_2(x) = 7$"; h3 — a Math \[text\] that says "$h\_3(x) = 11$"; ones — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); verdict — a Math \[text\] that says "$upright("probably present")$"; head\_query — a Heading that says "Asking a Question" Actions: - [04:22.541](https://academa.ai/lectures/bloom-filters?t=262.5406458333334): bits: retire a lit point (unemphasize\_point). - [04:22.541](https://academa.ai/lectures/bloom-filters?t=262.5406458333334): bits: retire a lit point (unemphasize\_point). - [04:22.541](https://academa.ai/lectures/bloom-filters?t=262.5406458333334): bits: retire a lit point (unemphasize\_point). - [04:26.929](https://academa.ai/lectures/bloom-filters?t=266.9291458333334): h1 becomes "$h\_1(w) = 0$". - [04:27.556](https://academa.ai/lectures/bloom-filters?t=267.5561458333334): h2 becomes "$h\_2(w) = 9$". - [04:28.195](https://academa.ai/lectures/bloom-filters?t=268.1951458333334): h3 becomes "$h\_3(w) = 14$". - [04:30.377](https://academa.ai/lectures/bloom-filters?t=270.3771458333334): The point (9.5, 0.5) in bits is lit up. - [04:32.037](https://academa.ai/lectures/bloom-filters?t=272.0371458333334): The point (14.5, 0.5) in bits is lit up. - [04:34.069](https://academa.ai/lectures/bloom-filters?t=274.0691458333334): The point (0.5, 0.5) in bits is lit up. ##### [04:36.098](https://academa.ai/lectures/bloom-filters?t=276.09764583333333) Narration: And that settles it. If this item had ever been inserted, every one of its bits would have been set at that moment, and bits in this row are never cleared. A single zero anywhere is proof of absence. Definitely not in the set. Board: Unchanged from the preceding beat in this scene. Actions: - [04:48.822](https://academa.ai/lectures/bloom-filters?t=288.82214583333337): verdict becomes "$upright("definitely absent")$". ##### [04:51.094](https://academa.ai/lectures/bloom-filters?t=291.09364583333337) Narration: That answer is exact, and it is the one guarantee the structure gives you. It is worth more than it sounds. Most of the time the thing you are asking about really is new, and you get told so for three bit lookups and no disk at all. Board: Unchanged from the preceding beat in this scene. Actions: - [04:51.094](https://academa.ai/lectures/bloom-filters?t=291.09364583333337): bits: retire a lit point (unemphasize\_point). - [04:51.094](https://academa.ai/lectures/bloom-filters?t=291.09364583333337): bits: retire a lit point (unemphasize\_point). - [04:51.094](https://academa.ai/lectures/bloom-filters?t=291.09364583333337): bits: retire a lit point (unemphasize\_point). - [04:52.15](https://academa.ai/lectures/bloom-filters?t=292.1501458333334): A box is drawn around verdict. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): bits is hidden from the screen — left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_2 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_3 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_4 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_5 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_6 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_7 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_8 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_9 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_10 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_11 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_12 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_13 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_14 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_15 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): cells\_16 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_2 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_3 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_4 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_5 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_6 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_7 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_8 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_9 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_10 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_11 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_12 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_13 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_14 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_15 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): tags\_16 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_2 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_3 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_4 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_5 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_6 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_7 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): ones\_8 is hidden from the screen — bits left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): h1 is hidden from the screen — left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): h2 is hidden from the screen — left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): h3 is hidden from the screen — left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): head\_query is hidden from the screen — left the board. - [05:4.806](https://academa.ai/lectures/bloom-filters?t=304.8061666666667): verdict is hidden from the screen — left the board. ### Scene 3: [The False Positive](https://academa.ai/lectures/bloom-filters?t=305.84783333333337) Span: 05:5.848–08:21.557 (305.84783333333337s–501.55745833333333s). #### Objects - bits: a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)) - cells: a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False) - cells\_10: a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False) - cells\_11: a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False) - cells\_12: a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False) - cells\_13: a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False) - cells\_14: a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False) - cells\_15: a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False) - cells\_16: a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False) - cells\_2: a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False) - cells\_3: a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False) - cells\_4: a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False) - cells\_5: a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False) - cells\_6: a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False) - cells\_7: a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False) - cells\_8: a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False) - cells\_9: a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False) - defs: a Text \[text\] that says "Write $P\_0$ for the chance that one chosen bit is still zero, and $P\_1$ for the chance that something has set it." - fill: an Axes (x\_range=(0.0, 12.0), x\_ticks\_every=3.0, y\_ticks\_every=0.25) - head\_fp: a Heading that says "An Item Nobody Inserted" - head\_math: a Heading that says "How Often Does That Happen?" - n\_live: a VariableNumber (initial\_value=3.0, format\_spec='.0f') - ones: a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75) - ones\_2: a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75) - ones\_3: a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75) - ones\_4: a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75) - ones\_5: a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75) - ones\_6: a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75) - ones\_7: a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75) - ones\_8: a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75) - probe: a PlotPoint \[yellow\] labelled "3" drawn in fill (target='share', x=\) - q1: a Math \[text\] that says "$h\_1(v) = 2$" - q2: a Math \[text\] that says "$h\_2(v) = 4$" - q3: a Math \[text\] that says "$h\_3(v) = 9$" - share: a FunctionPlot \[blue\] drawn in fill (function=\) - tags: a Math \[gray\] that says "$0$" drawn in bits - tags\_10: a Math \[gray\] that says "$9$" drawn in bits - tags\_11: a Math \[gray\] that says "$10$" drawn in bits - tags\_12: a Math \[gray\] that says "$11$" drawn in bits - tags\_13: a Math \[gray\] that says "$12$" drawn in bits - tags\_14: a Math \[gray\] that says "$13$" drawn in bits - tags\_15: a Math \[gray\] that says "$14$" drawn in bits - tags\_16: a Math \[gray\] that says "$15$" drawn in bits - tags\_2: a Math \[gray\] that says "$1$" drawn in bits - tags\_3: a Math \[gray\] that says "$2$" drawn in bits - tags\_4: a Math \[gray\] that says "$3$" drawn in bits - tags\_5: a Math \[gray\] that says "$4$" drawn in bits - tags\_6: a Math \[gray\] that says "$5$" drawn in bits - tags\_7: a Math \[gray\] that says "$6$" drawn in bits - tags\_8: a Math \[gray\] that says "$7$" drawn in bits - tags\_9: a Math \[gray\] that says "$8$" drawn in bits - verdict: a Math \[text\] that says "$upright("probably present")$" - work: a Derivation \[text\] that says "$P\_0 &= (1 - 1 slash m)^(k n) \\ &approx e^(-k n slash m) \\ P\_1 &approx 1 - e^(-k n slash m) \\ epsilon &approx (1 - e^(-k n slash m))^k$" #### Beats ##### [05:5.848](https://academa.ai/lectures/bloom-filters?t=305.84783333333337) Narration: Here is that same row, with those same three items in it, and now I am going to ask about an item that nobody ever inserted. Call it v. Its three positions come out two, four, and nine. Board: Empty. Actions: - [05:5.848](https://academa.ai/lectures/bloom-filters?t=305.84783333333337): head\_fp is shown on the screen, written out. - [05:5.848](https://academa.ai/lectures/bloom-filters?t=305.84783333333337): bits is shown on the screen, written out. - [05:6.823](https://academa.ai/lectures/bloom-filters?t=306.8228333333334): cells is shown on the screen, faded in. - [05:6.863](https://academa.ai/lectures/bloom-filters?t=306.86283333333336): cells\_2 is shown on the screen, faded in. - [05:6.903](https://academa.ai/lectures/bloom-filters?t=306.9028333333334): cells\_3 is shown on the screen, faded in. - [05:6.943](https://academa.ai/lectures/bloom-filters?t=306.9428333333334): cells\_4 is shown on the screen, faded in. - [05:6.983](https://academa.ai/lectures/bloom-filters?t=306.98283333333336): cells\_5 is shown on the screen, faded in. - [05:7.023](https://academa.ai/lectures/bloom-filters?t=307.0228333333334): cells\_6 is shown on the screen, faded in. - [05:7.063](https://academa.ai/lectures/bloom-filters?t=307.06283333333334): cells\_7 is shown on the screen, faded in. - [05:7.103](https://academa.ai/lectures/bloom-filters?t=307.10283333333336): cells\_8 is shown on the screen, faded in. - [05:7.143](https://academa.ai/lectures/bloom-filters?t=307.1428333333334): cells\_9 is shown on the screen, faded in. - [05:7.183](https://academa.ai/lectures/bloom-filters?t=307.18283333333335): cells\_10 is shown on the screen, faded in. - [05:7.223](https://academa.ai/lectures/bloom-filters?t=307.22283333333337): cells\_11 is shown on the screen, faded in. - [05:7.263](https://academa.ai/lectures/bloom-filters?t=307.2628333333334): cells\_12 is shown on the screen, faded in. - [05:7.303](https://academa.ai/lectures/bloom-filters?t=307.30283333333335): cells\_13 is shown on the screen, faded in. - [05:7.343](https://academa.ai/lectures/bloom-filters?t=307.3428333333334): cells\_14 is shown on the screen, faded in. - [05:7.383](https://academa.ai/lectures/bloom-filters?t=307.3828333333334): cells\_15 is shown on the screen, faded in. - [05:7.423](https://academa.ai/lectures/bloom-filters?t=307.42283333333336): cells\_16 is shown on the screen, faded in. - [05:8.495](https://academa.ai/lectures/bloom-filters?t=308.49483333333336): ones is shown on the screen, faded in. - [05:8.545](https://academa.ai/lectures/bloom-filters?t=308.5448333333334): ones\_2 is shown on the screen, faded in. - [05:8.595](https://academa.ai/lectures/bloom-filters?t=308.5948333333334): ones\_3 is shown on the screen, faded in. - [05:8.645](https://academa.ai/lectures/bloom-filters?t=308.6448333333334): ones\_4 is shown on the screen, faded in. - [05:8.695](https://academa.ai/lectures/bloom-filters?t=308.69483333333335): ones\_5 is shown on the screen, faded in. - [05:8.735](https://academa.ai/lectures/bloom-filters?t=308.73483333333337): tags is shown on the screen, written out. - [05:8.745](https://academa.ai/lectures/bloom-filters?t=308.74483333333336): ones\_6 is shown on the screen, faded in. - [05:8.765](https://academa.ai/lectures/bloom-filters?t=308.76483333333334): tags\_2 is shown on the screen, written out. - [05:8.795](https://academa.ai/lectures/bloom-filters?t=308.7948333333334): tags\_3 is shown on the screen, written out. - [05:8.795](https://academa.ai/lectures/bloom-filters?t=308.7948333333334): ones\_7 is shown on the screen, faded in. - [05:8.825](https://academa.ai/lectures/bloom-filters?t=308.82483333333334): tags\_4 is shown on the screen, written out. - [05:8.845](https://academa.ai/lectures/bloom-filters?t=308.8448333333334): ones\_8 is shown on the screen, faded in. - [05:8.855](https://academa.ai/lectures/bloom-filters?t=308.8548333333334): tags\_5 is shown on the screen, written out. - [05:8.885](https://academa.ai/lectures/bloom-filters?t=308.88483333333335): tags\_6 is shown on the screen, written out. - [05:8.915](https://academa.ai/lectures/bloom-filters?t=308.9148333333334): tags\_7 is shown on the screen, written out. - [05:8.945](https://academa.ai/lectures/bloom-filters?t=308.94483333333335): tags\_8 is shown on the screen, written out. - [05:8.975](https://academa.ai/lectures/bloom-filters?t=308.9748333333334): tags\_9 is shown on the screen, written out. - [05:9.005](https://academa.ai/lectures/bloom-filters?t=309.00483333333335): tags\_10 is shown on the screen, written out. - [05:9.035](https://academa.ai/lectures/bloom-filters?t=309.0348333333334): tags\_11 is shown on the screen, written out. - [05:9.065](https://academa.ai/lectures/bloom-filters?t=309.06483333333335): tags\_12 is shown on the screen, written out. - [05:9.095](https://academa.ai/lectures/bloom-filters?t=309.0948333333334): tags\_13 is shown on the screen, written out. - [05:9.125](https://academa.ai/lectures/bloom-filters?t=309.12483333333336): tags\_14 is shown on the screen, written out. - [05:9.155](https://academa.ai/lectures/bloom-filters?t=309.1548333333334): tags\_15 is shown on the screen, written out. - [05:9.185](https://academa.ai/lectures/bloom-filters?t=309.18483333333336): tags\_16 is shown on the screen, written out. - [05:15.937](https://academa.ai/lectures/bloom-filters?t=315.93683333333337): q1 is shown on the screen, written out. - [05:16.332](https://academa.ai/lectures/bloom-filters?t=316.33183333333335): q2 is shown on the screen, written out. - [05:16.785](https://academa.ai/lectures/bloom-filters?t=316.7848333333334): q3 is shown on the screen, written out. ##### [05:18.011](https://academa.ai/lectures/bloom-filters?t=318.01133333333337) Narration: Two is a one. The first item set it. Four is a one. The second item set that. Nine is a one, and the third item set that. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); q1 — a Math \[text\] that says "$h\_1(v) = 2$"; q2 — a Math \[text\] that says "$h\_2(v) = 4$"; q3 — a Math \[text\] that says "$h\_3(v) = 9$"; head\_fp — a Heading that says "An Item Nobody Inserted"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [05:18.232](https://academa.ai/lectures/bloom-filters?t=318.2318333333334): The point (2.5, 0.5) in bits is lit up. - [05:21.378](https://academa.ai/lectures/bloom-filters?t=321.37783333333334): The point (4.5, 0.5) in bits is lit up. - [05:25.024](https://academa.ai/lectures/bloom-filters?t=325.02383333333336): The point (9.5, 0.5) in bits is lit up. ##### [05:28.619](https://academa.ai/lectures/bloom-filters?t=328.6193333333334) Narration: So all k bits are ones, and the filter says: probably present. And it is wrong. No item set that pattern. Three different items each happened to set one of its bits, and between them they covered it. Board: Unchanged from the preceding beat in this scene. Actions: - [05:32.451](https://academa.ai/lectures/bloom-filters?t=332.4508333333334): verdict is shown on the screen, written out. ##### [05:43.197](https://academa.ai/lectures/bloom-filters?t=343.19733333333335) Narration: That is a false positive. It is not a bug, and there is no clever fix for it. It is what you bought when you decided to store bits instead of items. The bits do not remember who set them. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); q1 — a Math \[text\] that says "$h\_1(v) = 2$"; q2 — a Math \[text\] that says "$h\_2(v) = 4$"; q3 — a Math \[text\] that says "$h\_3(v) = 9$"; verdict — a Math \[text\] that says "$upright("probably present")$"; head\_fp — a Heading that says "An Item Nobody Inserted"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [05:44.475](https://academa.ai/lectures/bloom-filters?t=344.4748333333334): bits: retire a lit point (unemphasize\_point). - [05:44.475](https://academa.ai/lectures/bloom-filters?t=344.4748333333334): bits: retire a lit point (unemphasize\_point). - [05:44.475](https://academa.ai/lectures/bloom-filters?t=344.4748333333334): bits: retire a lit point (unemphasize\_point). ##### [05:56.127](https://academa.ai/lectures/bloom-filters?t=356.12683333333337) Narration: What you can do is work out how often it happens, before you ship anything, and then choose how often you are willing to let it happen. So let us count it. Board: Unchanged from the preceding beat in this scene. Actions: - [05:58.101](https://academa.ai/lectures/bloom-filters?t=358.10083333333336): verdict is indicated — a transient flash. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): bits is hidden from the screen — left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_2 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_3 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_4 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_5 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_6 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_7 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_8 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_9 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_10 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_11 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_12 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_13 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_14 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_15 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): cells\_16 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_2 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_3 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_4 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_5 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_6 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_7 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): ones\_8 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_2 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_3 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_4 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_5 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_6 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_7 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_8 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_9 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_10 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_11 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_12 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_13 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_14 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_15 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): tags\_16 is hidden from the screen — bits left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): head\_fp is hidden from the screen — left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): q1 is hidden from the screen — left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): q2 is hidden from the screen — left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): q3 is hidden from the screen — left the board. - [06:6.181](https://academa.ai/lectures/bloom-filters?t=366.1813333333333): verdict is hidden from the screen — left the board. ##### [06:7.381](https://academa.ai/lectures/bloom-filters?t=367.3813333333334) Narration: Fix one bit in the row and follow it. Call P nought the chance that this bit is still a zero, and P one the chance that something has set it. A single hash function picks a position uniformly out of m, so it misses our bit with probability one minus one over m. Board: Empty. Actions: - [06:7.381](https://academa.ai/lectures/bloom-filters?t=367.3813333333334): head\_math is shown on the screen, written out. - [06:10.446](https://academa.ai/lectures/bloom-filters?t=370.4458333333333): defs is shown on the screen, written out. ##### [06:24.142](https://academa.ai/lectures/bloom-filters?t=384.14233333333334) Narration: Inserting one item runs k hashes. Inserting n items runs k times n of them, and if the hash functions are independent our bit survives every one of them, with probability one minus one over m, all raised to the power k n. Board: defs — a Text \[text\] that says "Write $P\_0$ for the chance that one chosen bit is still zero, and $P\_1$ for the chance that something has set it."; head\_math — a Heading that says "How Often Does That Happen?" Actions: - [06:32.433](https://academa.ai/lectures/bloom-filters?t=392.43283333333335): work is shown on the screen, written out. ##### [06:39.383](https://academa.ai/lectures/bloom-filters?t=399.3833333333334) Narration: That form is awkward to think with, so use the standard approximation. When m is large it is very close to e to the minus k n over m. Same number, and far easier to see what it does. Board: Unchanged from the preceding beat in this scene. Actions: - [06:42.657](https://academa.ai/lectures/bloom-filters?t=402.65683333333334): work is shown on the screen, written out. ##### [06:52.545](https://academa.ai/lectures/bloom-filters?t=412.54533333333336) Narration: Turn it around. The chance that a given bit has been set is one minus that. And this curve is exactly that number, for our sixteen bit row with three hash functions, as n climbs. Board: Unchanged from the preceding beat in this scene. Actions: - [06:52.894](https://academa.ai/lectures/bloom-filters?t=412.89383333333336): work is shown on the screen, written out. - [06:57.874](https://academa.ai/lectures/bloom-filters?t=417.8738333333333): fill is shown on the screen, written out. - [06:57.874](https://academa.ai/lectures/bloom-filters?t=417.8738333333333): share is shown on the screen, drawn. ##### [07:5.115](https://academa.ai/lectures/bloom-filters?t=425.11483333333337) Narration: With three items in, the formula says about forty three percent of the bits are ones. We counted eight out of sixteen, which is fifty. With only sixteen bits that is the sort of luck you get. Now push n up to twelve. Board: defs — a Text \[text\] that says "Write $P\_0$ for the chance that one chosen bit is still zero, and $P\_1$ for the chance that something has set it."; fill — an Axes (x\_range=(0.0, 12.0), x\_ticks\_every=3.0, y\_ticks\_every=0.25); head\_math — a Heading that says "How Often Does That Happen?"; share — a FunctionPlot \[blue\] drawn in fill (function=\) Actions: - [07:5.742](https://academa.ai/lectures/bloom-filters?t=425.7418333333334): probe is shown on the screen, written out. - [07:17.642](https://academa.ai/lectures/bloom-filters?t=437.64183333333335): probe is redrawn as the numbers it depends on change. - [07:17.642](https://academa.ai/lectures/bloom-filters?t=437.64183333333335): n\_live ticks to 12.0. ##### [07:19.774](https://academa.ai/lectures/bloom-filters?t=439.77383333333336) Narration: Nearly ninety percent of the row is ones, and at that point almost any pattern you ask about is already covered by something. The false positive rate climbs with n, and this is the reason why. Board: defs — a Text \[text\] that says "Write $P\_0$ for the chance that one chosen bit is still zero, and $P\_1$ for the chance that something has set it."; fill — an Axes (x\_range=(0.0, 12.0), x\_ticks\_every=3.0, y\_ticks\_every=0.25); head\_math — a Heading that says "How Often Does That Happen?"; share — a FunctionPlot \[blue\] drawn in fill (function=\); probe — a PlotPoint \[yellow\] labelled "3" drawn in fill (target='share', x=\) Actions: - [07:28.97](https://academa.ai/lectures/bloom-filters?t=448.9698333333333): share is indicated — a transient flash. ##### [07:32.577](https://academa.ai/lectures/bloom-filters?t=452.57683333333335) Narration: So now the query itself. An item that was never inserted names k bits. Each one is a one with probability P one, and if we treat those as independent, all k of them are ones with probability P one to the k. Board: Unchanged from the preceding beat in this scene. Actions: - [07:43.664](https://academa.ai/lectures/bloom-filters?t=463.66383333333334): work is shown on the screen, written out. ##### [07:47.735](https://academa.ai/lectures/bloom-filters?t=467.73533333333336) Narration: There it is. The false positive rate, epsilon, is one minus e to the minus k n over m, all raised to the k. Read the exponent as the total number of bits you have set, k of them for each of n items, divided by the room you gave them to spread out in. Board: Unchanged from the preceding beat in this scene. Actions: - [07:50.766](https://academa.ai/lectures/bloom-filters?t=470.7658333333334): A box is drawn around work. - [07:58.765](https://academa.ai/lectures/bloom-filters?t=478.76483333333334): work (the "k n" part) is emphasized. - [08:4.233](https://academa.ai/lectures/bloom-filters?t=484.23283333333336): work (the "k n" part) is no longer emphasized. - [08:4.233](https://academa.ai/lectures/bloom-filters?t=484.23283333333336): work (the "m" part) is emphasized. - [08:6.299](https://academa.ai/lectures/bloom-filters?t=486.2993333333334): work (the "m" part) is no longer emphasized. ##### [08:6.899](https://academa.ai/lectures/bloom-filters?t=486.89933333333335) Narration: Read the rest of it the way an engineer reads it. n is handed to you by the problem. m is what you are willing to pay for. And k is the one you actually get to choose, and it is not at all obvious which way to push it. Board: Unchanged from the preceding beat in this scene. Actions: - [08:10.649](https://academa.ai/lectures/bloom-filters?t=490.6488333333333): probe is redrawn as the numbers it depends on change. - [08:10.649](https://academa.ai/lectures/bloom-filters?t=490.6488333333333): n\_live ticks to 6.0. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): defs is hidden from the screen — left the board. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): fill is hidden from the screen — left the board. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): share is hidden from the screen — fill left the board. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): probe is hidden from the screen — fill left the board. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): head\_math is hidden from the screen — left the board. - [08:20.516](https://academa.ai/lectures/bloom-filters?t=500.5157916666667): work is hidden from the screen — left the board. ### Scene 4: [Choosing the Hash Functions](https://academa.ai/lectures/bloom-filters?t=501.55745833333333) Span: 08:21.557–11:24.416 (501.55745833333333s–684.4156458333333s). #### Objects - b\_curve: a FunctionPlot \[green\] drawn in b\_plot (function=\) - b\_live: a VariableNumber (initial\_value=8.0, format\_spec='.0f') - b\_plot: an Axes (x\_range=(2.0, 20.0), y\_range=(0.0, 0.4), x\_ticks\_every=2.0) - b\_probe: a PlotPoint \[yellow\] labelled "8" drawn in b\_plot (target='b\_curve', x=\) - budget\_read: a Math \[text\] that says "$m slash n = 8: quad epsilon approx 0.021$" - collapsed: a Math \[text\] that says "$epsilon approx 0.62^(m slash n)$" - head\_budget: a Heading that says "What Another Bit Buys You" - head\_k: a Heading that says "Ten Bits an Item: the Curve in $k$" - k\_curve: a FunctionPlot \[blue\] drawn in k\_plot (function=\) - k\_live: a VariableNumber (initial\_value=1.0, format\_spec='.0f') - k\_plot: an Axes (x\_range=(1.0, 16.0), y\_range=(0.0, 0.11), x\_ticks\_every=2.0) - k\_probe: a PlotPoint \[yellow\] labelled "1" drawn in k\_plot (target='k\_curve', x=\) - optimum: a Math \[text\] that says "$k^\* = frac(m, n) ln 2 approx 0.693 frac(m, n)$" - point: a Point \[yellow\] drawn in k\_plot (location=(7.0, 0.0082)) - point\_2: a Point \[yellow\] drawn in b\_plot (location=(3.0, 0.2366)) - point\_3: a Point \[yellow\] drawn in b\_plot (location=(8.0, 0.0214)) - rate: a Math \[text\] that says "$epsilon approx (1 - e^(-k n slash m))^k$" - reading: a Math \[text\] that says "$k = 1: quad epsilon approx 0.095$" #### Beats ##### [08:21.557](https://academa.ai/lectures/bloom-filters?t=501.55745833333333) Narration: So, choosing k. Fix the budget at ten bits an item, which is the number you will see quoted everywhere, and the rate depends on k and nothing else. Here it is, plotted against the number of hash functions. Board: Empty. Actions: - [08:21.557](https://academa.ai/lectures/bloom-filters?t=501.55745833333333): head\_k is shown on the screen, written out. - [08:28.732](https://academa.ai/lectures/bloom-filters?t=508.73245833333334): rate is shown on the screen, written out. - [08:32.598](https://academa.ai/lectures/bloom-filters?t=512.5984583333334): k\_plot is shown on the screen, written out. - [08:32.598](https://academa.ai/lectures/bloom-filters?t=512.5984583333334): k\_curve is shown on the screen, drawn. ##### [08:35.706](https://academa.ai/lectures/bloom-filters?t=515.7064583333333) Narration: With one hash function, each item sets a single bit, and the rate is about nine and a half percent. Nearly one query in ten comes back wrong. Board: rate — a Math \[text\] that says "$epsilon approx (1 - e^(-k n slash m))^k$"; k\_plot — an Axes (x\_range=(1.0, 16.0), y\_range=(0.0, 0.11), x\_ticks\_every=2.0); head\_k — a Heading that says "Ten Bits an Item: the Curve in $k$"; k\_curve — a FunctionPlot \[blue\] drawn in k\_plot (function=\) Actions: - [08:36.298](https://academa.ai/lectures/bloom-filters?t=516.2984583333333): k\_probe is shown on the screen, written out. - [08:40.617](https://academa.ai/lectures/bloom-filters?t=520.6174583333334): reading is shown on the screen, written out. ##### [08:46.07](https://academa.ai/lectures/bloom-filters?t=526.0704583333334) Narration: Two hash functions: three point three percent. Three: one point seven. Every extra hash function is another bit that has to be a one by accident, and that gets rapidly less likely. Board: rate — a Math \[text\] that says "$epsilon approx (1 - e^(-k n slash m))^k$"; reading — a Math \[text\] that says "$k = 1: quad epsilon approx 0.095$"; k\_plot — an Axes (x\_range=(1.0, 16.0), y\_range=(0.0, 0.11), x\_ticks\_every=2.0); head\_k — a Heading that says "Ten Bits an Item: the Curve in $k$"; k\_curve — a FunctionPlot \[blue\] drawn in k\_plot (function=\); k\_probe — a PlotPoint \[yellow\] labelled "1" drawn in k\_plot (target='k\_curve', x=\) Actions: - [08:46.418](https://academa.ai/lectures/bloom-filters?t=526.4184583333333): k\_probe is redrawn as the numbers it depends on change. - [08:46.418](https://academa.ai/lectures/bloom-filters?t=526.4184583333333): reading becomes "$k = 2: quad epsilon approx 0.033$". - [08:46.418](https://academa.ai/lectures/bloom-filters?t=526.4184583333333): k\_live ticks to 2.0. - [08:47.974](https://academa.ai/lectures/bloom-filters?t=527.9744583333334): k\_probe is redrawn as the numbers it depends on change. - [08:47.974](https://academa.ai/lectures/bloom-filters?t=527.9744583333334): reading becomes "$k = 3: quad epsilon approx 0.017$". - [08:47.974](https://academa.ai/lectures/bloom-filters?t=527.9744583333334): k\_live ticks to 3.0. ##### [09:0.265](https://academa.ai/lectures/bloom-filters?t=540.2654583333333) Narration: Five hash functions gets you under one percent. Seven gets you eight in a thousand, and that is the best this budget can do. Board: Unchanged from the preceding beat in this scene. Actions: - [09:0.741](https://academa.ai/lectures/bloom-filters?t=540.7414583333333): k\_probe is redrawn as the numbers it depends on change. - [09:0.741](https://academa.ai/lectures/bloom-filters?t=540.7414583333333): reading becomes "$k = 5: quad epsilon approx 0.0094$". - [09:0.741](https://academa.ai/lectures/bloom-filters?t=540.7414583333333): k\_live ticks to 5.0. - [09:4.224](https://academa.ai/lectures/bloom-filters?t=544.2244583333334): k\_probe is redrawn as the numbers it depends on change. - [09:4.224](https://academa.ai/lectures/bloom-filters?t=544.2244583333334): reading becomes "$k = 7: quad epsilon approx 0.0082$". - [09:4.224](https://academa.ai/lectures/bloom-filters?t=544.2244583333334): k\_live ticks to 7.0. ##### [09:9.422](https://academa.ai/lectures/bloom-filters?t=549.4224583333333) Narration: Now watch what happens if you keep going. Ten hash functions is worse than seven. Fourteen is worse than three. The curve turns around and climbs back up. Board: Unchanged from the preceding beat in this scene. Actions: - [09:12.835](https://academa.ai/lectures/bloom-filters?t=552.8354583333333): k\_probe is redrawn as the numbers it depends on change. - [09:12.835](https://academa.ai/lectures/bloom-filters?t=552.8354583333333): reading becomes "$k = 10: quad epsilon approx 0.0100$". - [09:12.835](https://academa.ai/lectures/bloom-filters?t=552.8354583333333): k\_live ticks to 10.0. - [09:15.877](https://academa.ai/lectures/bloom-filters?t=555.8774583333334): k\_probe is redrawn as the numbers it depends on change. - [09:15.877](https://academa.ai/lectures/bloom-filters?t=555.8774583333334): reading becomes "$k = 14: quad epsilon approx 0.0184$". - [09:15.877](https://academa.ai/lectures/bloom-filters?t=555.8774583333334): k\_live ticks to 14.0. ##### [09:21.609](https://academa.ai/lectures/bloom-filters?t=561.6089583333334) Narration: And the reason is sitting in the formula. Every extra hash function is one more bit a query has to match, which helps you. But it is also one more bit set on every insert, so the exponent grows and the row fills up faster, which hurts you. Past a point the second effect wins. Board: Unchanged from the preceding beat in this scene. Actions: - [09:33.637](https://academa.ai/lectures/bloom-filters?t=573.6374583333334): rate (the "k n slash m" part) is emphasized. - [09:39.709](https://academa.ai/lectures/bloom-filters?t=579.7094583333333): rate (the "k n slash m" part) is no longer emphasized. ##### [09:41.157](https://academa.ai/lectures/bloom-filters?t=581.1569583333334) Narration: The minimum is where those two balance, and it lands somewhere clean. The best k is m over n times the natural log of two, which for ten bits an item is six point nine. So you use seven. Board: Unchanged from the preceding beat in this scene. Actions: - [09:46.044](https://academa.ai/lectures/bloom-filters?t=586.0444583333333): optimum is shown on the screen, written out. - [09:53.394](https://academa.ai/lectures/bloom-filters?t=593.3944583333333): point is shown on the screen, grown. ##### [09:54.795](https://academa.ai/lectures/bloom-filters?t=594.7949583333333) Narration: And there is a check you can run in production. At the optimal k the row ends up with almost exactly half its bits set. Half ones, half zeros. If your filter is much fuller than half, you are running too many hash functions. Board: rate — a Math \[text\] that says "$epsilon approx (1 - e^(-k n slash m))^k$"; reading — a Math \[text\] that says "$k = 1: quad epsilon approx 0.095$"; optimum — a Math \[text\] that says "$k^\* = frac(m, n) ln 2 approx 0.693 frac(m, n)$"; k\_plot — an Axes (x\_range=(1.0, 16.0), y\_range=(0.0, 0.11), x\_ticks\_every=2.0); head\_k — a Heading that says "Ten Bits an Item: the Curve in $k$"; k\_curve — a FunctionPlot \[blue\] drawn in k\_plot (function=\); k\_probe — a PlotPoint \[yellow\] labelled "1" drawn in k\_plot (target='k\_curve', x=\); point — a Point \[yellow\] drawn in k\_plot (location=(7.0, 0.0082)) Actions: - [09:55.394](https://academa.ai/lectures/bloom-filters?t=595.3944583333333): point is hidden from the screen. - [10:1.192](https://academa.ai/lectures/bloom-filters?t=601.1924583333333): k\_probe is indicated — a transient flash. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): head\_k is hidden from the screen — left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): k\_plot is hidden from the screen — left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): k\_curve is hidden from the screen — k\_plot left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): k\_probe is hidden from the screen — k\_plot left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): optimum is hidden from the screen — left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): rate is hidden from the screen — left the board. - [10:9.818](https://academa.ai/lectures/bloom-filters?t=609.8179583333333): reading is hidden from the screen — left the board. ##### [10:11.018](https://academa.ai/lectures/bloom-filters?t=611.0179583333334) Narration: Which leaves the budget itself. Substitute that optimal k back into the rate, and the whole expression collapses into one number raised to the bits per item. About zero point six two, to the power m over n. Board: Empty. Actions: - [10:11.018](https://academa.ai/lectures/bloom-filters?t=611.0179583333334): head\_budget is shown on the screen, written out. - [10:17.427](https://academa.ai/lectures/bloom-filters?t=617.4274583333333): collapsed is shown on the screen, written out. - [10:18.541](https://academa.ai/lectures/bloom-filters?t=618.5414583333334): b\_plot is shown on the screen, written out. - [10:18.541](https://academa.ai/lectures/bloom-filters?t=618.5414583333334): b\_curve is shown on the screen, drawn. ##### [10:25.968](https://academa.ai/lectures/bloom-filters?t=625.9684583333333) Narration: So here is the curve an engineer actually wants. Bits per item across the bottom, false positive rate up the side. At eight bits an item, two percent. Board: collapsed — a Math \[text\] that says "$epsilon approx 0.62^(m slash n)$"; b\_plot — an Axes (x\_range=(2.0, 20.0), y\_range=(0.0, 0.4), x\_ticks\_every=2.0); head\_budget — a Heading that says "What Another Bit Buys You"; b\_curve — a FunctionPlot \[green\] drawn in b\_plot (function=\) Actions: - [10:34.826](https://academa.ai/lectures/bloom-filters?t=634.8264583333333): b\_probe is shown on the screen, written out. - [10:35.894](https://academa.ai/lectures/bloom-filters?t=635.8944583333333): budget\_read is shown on the screen, written out. ##### [10:37.76](https://academa.ai/lectures/bloom-filters?t=637.7604583333333) Narration: At ten bits, eight in a thousand. At fourteen, about one in a thousand. At twenty bits an item you are down to seven in a hundred thousand, and you are still using less than three bytes a URL. Board: collapsed — a Math \[text\] that says "$epsilon approx 0.62^(m slash n)$"; budget\_read — a Math \[text\] that says "$m slash n = 8: quad epsilon approx 0.021$"; b\_plot — an Axes (x\_range=(2.0, 20.0), y\_range=(0.0, 0.4), x\_ticks\_every=2.0); head\_budget — a Heading that says "What Another Bit Buys You"; b\_curve — a FunctionPlot \[green\] drawn in b\_plot (function=\); b\_probe — a PlotPoint \[yellow\] labelled "8" drawn in b\_plot (target='b\_curve', x=\) Actions: - [10:38.445](https://academa.ai/lectures/bloom-filters?t=638.4454583333334): b\_probe is redrawn as the numbers it depends on change. - [10:38.445](https://academa.ai/lectures/bloom-filters?t=638.4454583333334): budget\_read becomes "$m slash n = 10: quad epsilon approx 0.0082$". - [10:38.445](https://academa.ai/lectures/bloom-filters?t=638.4454583333334): b\_live ticks to 10.0. - [10:41.916](https://academa.ai/lectures/bloom-filters?t=641.9164583333334): b\_probe is redrawn as the numbers it depends on change. - [10:41.916](https://academa.ai/lectures/bloom-filters?t=641.9164583333334): budget\_read becomes "$m slash n = 14: quad epsilon approx 0.0012$". - [10:41.916](https://academa.ai/lectures/bloom-filters?t=641.9164583333334): b\_live ticks to 14.0. - [10:45.422](https://academa.ai/lectures/bloom-filters?t=645.4224583333333): b\_probe is redrawn as the numbers it depends on change. - [10:45.422](https://academa.ai/lectures/bloom-filters?t=645.4224583333333): budget\_read becomes "$m slash n = 20: quad epsilon approx 0.000067$". - [10:45.422](https://academa.ai/lectures/bloom-filters?t=645.4224583333333): b\_live ticks to 20.0. ##### [10:54.614](https://academa.ai/lectures/bloom-filters?t=654.6144583333333) Narration: Every extra bit per item multiplies the error by roughly zero point six two. That is what makes ten the number people quote. It is the first place the curve is properly flat, and it is under one percent. Board: Unchanged from the preceding beat in this scene. Actions: - [10:56.413](https://academa.ai/lectures/bloom-filters?t=656.4134583333333): collapsed (the "0.62" part) is emphasized. - [11:2.23](https://academa.ai/lectures/bloom-filters?t=662.2304583333333): collapsed (the "0.62" part) is no longer emphasized. ##### [11:9.053](https://academa.ai/lectures/bloom-filters?t=669.0534583333333) Narration: And look at the shape of it. Going from three bits an item to eight is cheap, and it buys you an enormous amount. After that it gets expensive, because you are paying linearly for an error that is shrinking exponentially. Board: Unchanged from the preceding beat in this scene. Actions: - [11:12.013](https://academa.ai/lectures/bloom-filters?t=672.0134583333333): point\_2 is shown on the screen, grown. - [11:13.151](https://academa.ai/lectures/bloom-filters?t=673.1514583333334): point\_3 is shown on the screen, grown. - [11:14.013](https://academa.ai/lectures/bloom-filters?t=674.0134583333333): point\_2 is hidden from the screen. - [11:15.151](https://academa.ai/lectures/bloom-filters?t=675.1514583333334): point\_3 is hidden from the screen. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): b\_plot is hidden from the screen — left the board. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): b\_curve is hidden from the screen — b\_plot left the board. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): b\_probe is hidden from the screen — b\_plot left the board. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): budget\_read is hidden from the screen — left the board. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): collapsed is hidden from the screen — left the board. - [11:23.374](https://academa.ai/lectures/bloom-filters?t=683.3739791666667): head\_budget is hidden from the screen — left the board. ### Scene 5: [No Deletions, and One Real Use](https://academa.ai/lectures/bloom-filters?t=684.4156458333333) Span: 11:24.416–14:17.241 (684.4156458333333s–857.2411875s). #### Objects - arrow\_fetch: an Arrow \[green\] labelled "upright("definitely new")" drawn in crawl (start=(7.8, 2.8), end=(8.9, 1.8)) - arrow\_in: an Arrow \[gray\] drawn in crawl (start=(3.4, 3.2), end=(4.4, 3.2)) - arrow\_skip: an Arrow \[red\] labelled "upright("probably seen")" drawn in crawl (start=(7.8, 3.6), end=(8.9, 4.6)) - bits: a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)) - box\_fetch: a Polygon \[gray\] labelled "upright("fetch")" drawn in crawl (vertices=((9.1, 1.1), (11.4, 1.1), (11.4, 2.3), (9.1, 2.3)), filled=False) - box\_filter: a Polygon \[blue\] labelled "upright("Bloom filter")" drawn in crawl (vertices=((4.6, 2.4), (7.6, 2.4), (7.6, 4.0), (4.6, 4.0)), fill\_opacity=0.25) - box\_link: a Polygon \[gray\] labelled "upright("URL found")" drawn in crawl (vertices=((0.6, 2.5), (3.2, 2.5), (3.2, 3.9), (0.6, 3.9)), filled=False) - box\_skip: a Polygon \[gray\] labelled "upright("drop")" drawn in crawl (vertices=((9.1, 4.1), (11.4, 4.1), (11.4, 5.3), (9.1, 5.3)), filled=False) - cells: a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False) - cells\_10: a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False) - cells\_11: a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False) - cells\_12: a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False) - cells\_13: a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False) - cells\_14: a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False) - cells\_15: a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False) - cells\_16: a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False) - cells\_2: a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False) - cells\_3: a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False) - cells\_4: a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False) - cells\_5: a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False) - cells\_6: a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False) - cells\_7: a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False) - cells\_8: a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False) - cells\_9: a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False) - clear\_chip: a Math \[text\] that says "$upright("clear") thin x: quad 2, thin 7, thin 11$" - counting: a Panel that says "If you truly must delete, replace each bit with a small counter and increment on insert. That is a counting Bloom filter, and four bit counters make the structure four times larger." - crawl: a Figure (x\_range=(0.0, 12.0), y\_range=(0.0, 6.4), aspect=(12.0, 6.4)) - head\_crawl: a Heading that says "A Crawler That Has Seen a Billion URLs" - head\_delete: a Heading that says "Try to Delete Something" - head\_rule: a Heading that says "The Rule, Plainly" - ones: a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75) - ones\_2: a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75) - ones\_3: a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75) - ones\_4: a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75) - ones\_5: a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75) - ones\_6: a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75) - ones\_7: a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75) - ones\_8: a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75) - query\_chip: a Math \[text\] that says "$upright("query") thin y: quad 4, thin 7, thin 13$" - rule: a Panel that says "A bit set by one item may also be needed by another. Clearing it can turn a present item into a definite absence, and definite absence is the one answer a Bloom filter is never allowed to get wrong." - scale\_1: a Math \[text\] that says "$m slash n = 10 arrow.r 1.25 thin upright("GB")$" - scale\_2: a Math \[text\] that says "$epsilon approx 0.008$" - scale\_3: a Math \[text\] that says "$8 dot.op 10^6 thin upright("pages skipped")$" - tags: a Math \[gray\] that says "$0$" drawn in bits - tags\_10: a Math \[gray\] that says "$9$" drawn in bits - tags\_11: a Math \[gray\] that says "$10$" drawn in bits - tags\_12: a Math \[gray\] that says "$11$" drawn in bits - tags\_13: a Math \[gray\] that says "$12$" drawn in bits - tags\_14: a Math \[gray\] that says "$13$" drawn in bits - tags\_15: a Math \[gray\] that says "$14$" drawn in bits - tags\_16: a Math \[gray\] that says "$15$" drawn in bits - tags\_2: a Math \[gray\] that says "$1$" drawn in bits - tags\_3: a Math \[gray\] that says "$2$" drawn in bits - tags\_4: a Math \[gray\] that says "$3$" drawn in bits - tags\_5: a Math \[gray\] that says "$4$" drawn in bits - tags\_6: a Math \[gray\] that says "$5$" drawn in bits - tags\_7: a Math \[gray\] that says "$6$" drawn in bits - tags\_8: a Math \[gray\] that says "$7$" drawn in bits - tags\_9: a Math \[gray\] that says "$8$" drawn in bits - verdict: a Math \[text\] that says "$upright("definitely absent")$" #### Beats ##### [11:24.416](https://academa.ai/lectures/bloom-filters?t=684.4156458333333) Narration: One more property, and it is the one that catches people out. You cannot remove anything from a Bloom filter. Here is why, on the row we already have, with the same three items in it. Board: Empty. Actions: - [11:24.416](https://academa.ai/lectures/bloom-filters?t=684.4156458333333): head\_delete is shown on the screen, written out. - [11:24.416](https://academa.ai/lectures/bloom-filters?t=684.4156458333333): bits is shown on the screen, written out. - [11:32.09](https://academa.ai/lectures/bloom-filters?t=692.0896458333333): cells is shown on the screen, faded in. - [11:32.13](https://academa.ai/lectures/bloom-filters?t=692.1296458333334): cells\_2 is shown on the screen, faded in. - [11:32.17](https://academa.ai/lectures/bloom-filters?t=692.1696458333333): cells\_3 is shown on the screen, faded in. - [11:32.21](https://academa.ai/lectures/bloom-filters?t=692.2096458333333): cells\_4 is shown on the screen, faded in. - [11:32.25](https://academa.ai/lectures/bloom-filters?t=692.2496458333333): cells\_5 is shown on the screen, faded in. - [11:32.29](https://academa.ai/lectures/bloom-filters?t=692.2896458333333): cells\_6 is shown on the screen, faded in. - [11:32.33](https://academa.ai/lectures/bloom-filters?t=692.3296458333333): cells\_7 is shown on the screen, faded in. - [11:32.37](https://academa.ai/lectures/bloom-filters?t=692.3696458333333): cells\_8 is shown on the screen, faded in. - [11:32.41](https://academa.ai/lectures/bloom-filters?t=692.4096458333333): cells\_9 is shown on the screen, faded in. - [11:32.45](https://academa.ai/lectures/bloom-filters?t=692.4496458333333): cells\_10 is shown on the screen, faded in. - [11:32.49](https://academa.ai/lectures/bloom-filters?t=692.4896458333333): cells\_11 is shown on the screen, faded in. - [11:32.53](https://academa.ai/lectures/bloom-filters?t=692.5296458333333): cells\_12 is shown on the screen, faded in. - [11:32.57](https://academa.ai/lectures/bloom-filters?t=692.5696458333333): cells\_13 is shown on the screen, faded in. - [11:32.61](https://academa.ai/lectures/bloom-filters?t=692.6096458333333): cells\_14 is shown on the screen, faded in. - [11:32.65](https://academa.ai/lectures/bloom-filters?t=692.6496458333334): cells\_15 is shown on the screen, faded in. - [11:32.69](https://academa.ai/lectures/bloom-filters?t=692.6896458333333): cells\_16 is shown on the screen, faded in. - [11:34.331](https://academa.ai/lectures/bloom-filters?t=694.3306458333333): ones is shown on the screen, faded in. - [11:34.381](https://academa.ai/lectures/bloom-filters?t=694.3806458333333): ones\_2 is shown on the screen, faded in. - [11:34.431](https://academa.ai/lectures/bloom-filters?t=694.4306458333333): ones\_3 is shown on the screen, faded in. - [11:34.481](https://academa.ai/lectures/bloom-filters?t=694.4806458333334): ones\_4 is shown on the screen, faded in. - [11:34.531](https://academa.ai/lectures/bloom-filters?t=694.5306458333333): ones\_5 is shown on the screen, faded in. - [11:34.571](https://academa.ai/lectures/bloom-filters?t=694.5706458333333): tags is shown on the screen, written out. - [11:34.581](https://academa.ai/lectures/bloom-filters?t=694.5806458333333): ones\_6 is shown on the screen, faded in. - [11:34.601](https://academa.ai/lectures/bloom-filters?t=694.6006458333333): tags\_2 is shown on the screen, written out. - [11:34.631](https://academa.ai/lectures/bloom-filters?t=694.6306458333333): ones\_7 is shown on the screen, faded in. - [11:34.631](https://academa.ai/lectures/bloom-filters?t=694.6306458333333): tags\_3 is shown on the screen, written out. - [11:34.661](https://academa.ai/lectures/bloom-filters?t=694.6606458333333): tags\_4 is shown on the screen, written out. - [11:34.681](https://academa.ai/lectures/bloom-filters?t=694.6806458333333): ones\_8 is shown on the screen, faded in. - [11:34.691](https://academa.ai/lectures/bloom-filters?t=694.6906458333333): tags\_5 is shown on the screen, written out. - [11:34.721](https://academa.ai/lectures/bloom-filters?t=694.7206458333333): tags\_6 is shown on the screen, written out. - [11:34.751](https://academa.ai/lectures/bloom-filters?t=694.7506458333334): tags\_7 is shown on the screen, written out. - [11:34.781](https://academa.ai/lectures/bloom-filters?t=694.7806458333333): tags\_8 is shown on the screen, written out. - [11:34.811](https://academa.ai/lectures/bloom-filters?t=694.8106458333333): tags\_9 is shown on the screen, written out. - [11:34.841](https://academa.ai/lectures/bloom-filters?t=694.8406458333333): tags\_10 is shown on the screen, written out. - [11:34.871](https://academa.ai/lectures/bloom-filters?t=694.8706458333334): tags\_11 is shown on the screen, written out. - [11:34.901](https://academa.ai/lectures/bloom-filters?t=694.9006458333333): tags\_12 is shown on the screen, written out. - [11:34.931](https://academa.ai/lectures/bloom-filters?t=694.9306458333333): tags\_13 is shown on the screen, written out. - [11:34.961](https://academa.ai/lectures/bloom-filters?t=694.9606458333333): tags\_14 is shown on the screen, written out. - [11:34.991](https://academa.ai/lectures/bloom-filters?t=694.9906458333334): tags\_15 is shown on the screen, written out. - [11:35.021](https://academa.ai/lectures/bloom-filters?t=695.0206458333333): tags\_16 is shown on the screen, written out. ##### [11:35.906](https://academa.ai/lectures/bloom-filters?t=695.9056458333333) Narration: Suppose we want to take the first item back out. Its bits were two, seven, and eleven, so the obvious move is to clear those three. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); head\_delete — a Heading that says "Try to Delete Something"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [11:39.366](https://academa.ai/lectures/bloom-filters?t=699.3656458333334): clear\_chip is shown on the screen, written out. - [11:42.385](https://academa.ai/lectures/bloom-filters?t=702.3846458333334): ones\_2 is hidden from the screen. - [11:42.385](https://academa.ai/lectures/bloom-filters?t=702.3846458333334): ones\_4 is hidden from the screen. - [11:42.385](https://academa.ai/lectures/bloom-filters?t=702.3846458333334): ones\_6 is hidden from the screen. ##### [11:44.099](https://academa.ai/lectures/bloom-filters?t=704.0986458333333) Narration: Now ask about the second item, which is still very much in the set. Its bits are four, seven, and thirteen. Four is a one. Thirteen is a one. And seven is now a zero, because we just cleared it. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); clear\_chip — a Math \[text\] that says "$upright("clear") thin x: quad 2, thin 7, thin 11$"; head\_delete — a Heading that says "Try to Delete Something"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [11:48.441](https://academa.ai/lectures/bloom-filters?t=708.4406458333333): query\_chip is shown on the screen, written out. - [11:48.813](https://academa.ai/lectures/bloom-filters?t=708.8126458333334): The point (4.5, 0.5) in bits is lit up. - [11:49.811](https://academa.ai/lectures/bloom-filters?t=709.8106458333333): The point (13.5, 0.5) in bits is lit up. - [11:54.316](https://academa.ai/lectures/bloom-filters?t=714.3156458333333): The point (7.5, 0.5) in bits is lit up. ##### [11:57.923](https://academa.ai/lectures/bloom-filters?t=717.9226458333333) Narration: So the filter says definitely absent, about an item that is definitely present. That is a false negative, and it is the single answer this structure promised you it would never get wrong. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); clear\_chip — a Math \[text\] that says "$upright("clear") thin x: quad 2, thin 7, thin 11$"; query\_chip — a Math \[text\] that says "$upright("query") thin y: quad 4, thin 7, thin 13$"; head\_delete — a Heading that says "Try to Delete Something"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [11:59.862](https://academa.ai/lectures/bloom-filters?t=719.8616458333333): verdict is shown on the screen, written out. ##### [12:10.017](https://academa.ai/lectures/bloom-filters?t=730.0166458333333) Narration: The bit at seven was never the first item's bit to give back. It was shared, and nothing in the row records how many items are leaning on it. So we put it back, and we do not do that again. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); clear\_chip — a Math \[text\] that says "$upright("clear") thin x: quad 2, thin 7, thin 11$"; query\_chip — a Math \[text\] that says "$upright("query") thin y: quad 4, thin 7, thin 13$"; verdict — a Math \[text\] that says "$upright("definitely absent")$"; head\_delete — a Heading that says "Try to Delete Something"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [12:14.045](https://academa.ai/lectures/bloom-filters?t=734.0446458333333): bits: retire a lit point (unemphasize\_point). - [12:14.045](https://academa.ai/lectures/bloom-filters?t=734.0446458333333): bits: retire a lit point (unemphasize\_point). - [12:14.045](https://academa.ai/lectures/bloom-filters?t=734.0446458333333): bits: retire a lit point (unemphasize\_point). - [12:19.003](https://academa.ai/lectures/bloom-filters?t=739.0026458333333): ones\_4 is shown on the screen, faded in. - [12:19.003](https://academa.ai/lectures/bloom-filters?t=739.0026458333333): ones\_2 is shown on the screen, faded in. - [12:19.003](https://academa.ai/lectures/bloom-filters?t=739.0026458333333): ones\_6 is shown on the screen, faded in. ##### [12:22.134](https://academa.ai/lectures/bloom-filters?t=742.1336458333333) Narration: Which gives us the rule, and it is worth stating plainly. Board: bits — a Figure (x\_range=(-0.5, 16.5), y\_range=(-1.6, 1.6), aspect=(17.0, 3.2)); clear\_chip — a Math \[text\] that says "$upright("clear") thin x: quad 2, thin 7, thin 11$"; query\_chip — a Math \[text\] that says "$upright("query") thin y: quad 4, thin 7, thin 13$"; verdict — a Math \[text\] that says "$upright("definitely absent")$"; head\_delete — a Heading that says "Try to Delete Something"; cells — a Polygon \[gray\] drawn in bits (vertices=((0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)), filled=False); cells\_2 — a Polygon \[gray\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), filled=False); cells\_3 — a Polygon \[gray\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), filled=False); cells\_4 — a Polygon \[gray\] drawn in bits (vertices=((3.0, 0.0), (4.0, 0.0), (4.0, 1.0), (3.0, 1.0)), filled=False); cells\_5 — a Polygon \[gray\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), filled=False); cells\_6 — a Polygon \[gray\] drawn in bits (vertices=((5.0, 0.0), (6.0, 0.0), (6.0, 1.0), (5.0, 1.0)), filled=False); cells\_7 — a Polygon \[gray\] drawn in bits (vertices=((6.0, 0.0), (7.0, 0.0), (7.0, 1.0), (6.0, 1.0)), filled=False); cells\_8 — a Polygon \[gray\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), filled=False); cells\_9 — a Polygon \[gray\] drawn in bits (vertices=((8.0, 0.0), (9.0, 0.0), (9.0, 1.0), (8.0, 1.0)), filled=False); cells\_10 — a Polygon \[gray\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), filled=False); cells\_11 — a Polygon \[gray\] drawn in bits (vertices=((10.0, 0.0), (11.0, 0.0), (11.0, 1.0), (10.0, 1.0)), filled=False); cells\_12 — a Polygon \[gray\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), filled=False); cells\_13 — a Polygon \[gray\] drawn in bits (vertices=((12.0, 0.0), (13.0, 0.0), (13.0, 1.0), (12.0, 1.0)), filled=False); cells\_14 — a Polygon \[gray\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), filled=False); cells\_15 — a Polygon \[gray\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), filled=False); cells\_16 — a Polygon \[gray\] drawn in bits (vertices=((15.0, 0.0), (16.0, 0.0), (16.0, 1.0), (15.0, 1.0)), filled=False); ones — a Polygon \[blue\] drawn in bits (vertices=((1.0, 0.0), (2.0, 0.0), (2.0, 1.0), (1.0, 1.0)), fill\_opacity=0.75); ones\_2 — a Polygon \[blue\] drawn in bits (vertices=((2.0, 0.0), (3.0, 0.0), (3.0, 1.0), (2.0, 1.0)), fill\_opacity=0.75); ones\_3 — a Polygon \[blue\] drawn in bits (vertices=((4.0, 0.0), (5.0, 0.0), (5.0, 1.0), (4.0, 1.0)), fill\_opacity=0.75); ones\_4 — a Polygon \[blue\] drawn in bits (vertices=((7.0, 0.0), (8.0, 0.0), (8.0, 1.0), (7.0, 1.0)), fill\_opacity=0.75); ones\_5 — a Polygon \[blue\] drawn in bits (vertices=((9.0, 0.0), (10.0, 0.0), (10.0, 1.0), (9.0, 1.0)), fill\_opacity=0.75); ones\_6 — a Polygon \[blue\] drawn in bits (vertices=((11.0, 0.0), (12.0, 0.0), (12.0, 1.0), (11.0, 1.0)), fill\_opacity=0.75); ones\_7 — a Polygon \[blue\] drawn in bits (vertices=((13.0, 0.0), (14.0, 0.0), (14.0, 1.0), (13.0, 1.0)), fill\_opacity=0.75); ones\_8 — a Polygon \[blue\] drawn in bits (vertices=((14.0, 0.0), (15.0, 0.0), (15.0, 1.0), (14.0, 1.0)), fill\_opacity=0.75); tags — a Math \[gray\] that says "$0$" drawn in bits; tags\_2 — a Math \[gray\] that says "$1$" drawn in bits; tags\_3 — a Math \[gray\] that says "$2$" drawn in bits; tags\_4 — a Math \[gray\] that says "$3$" drawn in bits; tags\_5 — a Math \[gray\] that says "$4$" drawn in bits; tags\_6 — a Math \[gray\] that says "$5$" drawn in bits; tags\_7 — a Math \[gray\] that says "$6$" drawn in bits; tags\_8 — a Math \[gray\] that says "$7$" drawn in bits; tags\_9 — a Math \[gray\] that says "$8$" drawn in bits; tags\_10 — a Math \[gray\] that says "$9$" drawn in bits; tags\_11 — a Math \[gray\] that says "$10$" drawn in bits; tags\_12 — a Math \[gray\] that says "$11$" drawn in bits; tags\_13 — a Math \[gray\] that says "$12$" drawn in bits; tags\_14 — a Math \[gray\] that says "$13$" drawn in bits; tags\_15 — a Math \[gray\] that says "$14$" drawn in bits; tags\_16 — a Math \[gray\] that says "$15$" drawn in bits Actions: - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): bits is hidden from the screen — left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_2 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_3 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_4 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_5 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_6 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_7 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_8 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_9 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_10 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_11 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_12 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_13 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_14 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_15 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): cells\_16 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_2 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_3 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_4 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_5 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_6 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_7 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): ones\_8 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_2 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_3 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_4 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_5 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_6 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_7 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_8 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_9 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_10 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_11 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_12 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_13 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_14 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_15 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): tags\_16 is hidden from the screen — bits left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): clear\_chip is hidden from the screen — left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): head\_delete is hidden from the screen — left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): query\_chip is hidden from the screen — left the board. - [12:26](https://academa.ai/lectures/bloom-filters?t=746.0001458333334): verdict is hidden from the screen — left the board. ##### [12:27.2](https://academa.ai/lectures/bloom-filters?t=747.2001458333333) Narration: A Bloom filter supports insert, and it supports query, and it does not support delete. If the things you are tracking ever go away again, this is the wrong structure for them. Board: Empty. Actions: - [12:27.2](https://academa.ai/lectures/bloom-filters?t=747.2001458333333): head\_rule is shown on the screen, written out. - [12:28.71](https://academa.ai/lectures/bloom-filters?t=748.7096458333333): rule is shown on the screen, written out. - [12:32.251](https://academa.ai/lectures/bloom-filters?t=752.2506458333334): rule (the "Clearing it" part) is emphasized. - [12:36.593](https://academa.ai/lectures/bloom-filters?t=756.5926458333333): rule (the "Clearing it" part) is no longer emphasized. ##### [12:38.783](https://academa.ai/lectures/bloom-filters?t=758.7831458333333) Narration: There is a variant that fixes it. Replace each bit with a small counter, increment on insert, decrement on delete, and now the shared position knows that two items are leaning on it. You pay for that. Four bit counters make the whole thing four times bigger, which was most of the reason you reached for a Bloom filter in the first place. Board: rule — a Panel that says "A bit set by one item may also be needed by another. Clearing it can turn a present item into a definite absence, and definite absence is the one answer a Bloom filter is never allowed to get wrong."; head\_rule — a Heading that says "The Rule, Plainly" Actions: - [12:39.654](https://academa.ai/lectures/bloom-filters?t=759.6536458333333): counting is shown on the screen, written out. - [12:57.858](https://academa.ai/lectures/bloom-filters?t=777.8581458333333): counting is hidden from the screen — left the board. - [12:57.858](https://academa.ai/lectures/bloom-filters?t=777.8581458333333): head\_rule is hidden from the screen — left the board. - [12:57.858](https://academa.ai/lectures/bloom-filters?t=777.8581458333333): rule is hidden from the screen — left the board. ##### [12:59.058](https://academa.ai/lectures/bloom-filters?t=779.0581458333334) Narration: So where does this earn its keep? A crawler is the clean case. You pull a URL off the frontier, and before you spend a network round trip on it, you ask whether you have fetched it already. Board: Empty. Actions: - [12:59.058](https://academa.ai/lectures/bloom-filters?t=779.0581458333334): head\_crawl is shown on the screen, written out. - [12:59.058](https://academa.ai/lectures/bloom-filters?t=779.0581458333334): crawl is shown on the screen, written out. - [13:4.527](https://academa.ai/lectures/bloom-filters?t=784.5266458333333): box\_link is shown on the screen, written out. - [13:8.718](https://academa.ai/lectures/bloom-filters?t=788.7176458333333): arrow\_in is shown on the screen, drawn. - [13:8.718](https://academa.ai/lectures/bloom-filters?t=788.7176458333333): box\_filter is shown on the screen, written out. ##### [13:11.222](https://academa.ai/lectures/bloom-filters?t=791.2216458333332) Narration: The filter answers in the two ways we know. Definitely new, and you fetch it. Probably seen, and you drop it on the floor. Board: crawl — a Figure (x\_range=(0.0, 12.0), y\_range=(0.0, 6.4), aspect=(12.0, 6.4)); head\_crawl — a Heading that says "A Crawler That Has Seen a Billion URLs"; box\_link — a Polygon \[gray\] labelled "upright("URL found")" drawn in crawl (vertices=((0.6, 2.5), (3.2, 2.5), (3.2, 3.9), (0.6, 3.9)), filled=False); arrow\_in — an Arrow \[gray\] drawn in crawl (start=(3.4, 3.2), end=(4.4, 3.2)); box\_filter — a Polygon \[blue\] labelled "upright("Bloom filter")" drawn in crawl (vertices=((4.6, 2.4), (7.6, 2.4), (7.6, 4.0), (4.6, 4.0)), fill\_opacity=0.25) Actions: - [13:14.345](https://academa.ai/lectures/bloom-filters?t=794.3446458333333): arrow\_fetch is shown on the screen, drawn. - [13:15.901](https://academa.ai/lectures/bloom-filters?t=795.9006458333333): box\_fetch is shown on the screen, written out. - [13:17.05](https://academa.ai/lectures/bloom-filters?t=797.0496458333333): arrow\_skip is shown on the screen, drawn. - [13:18.467](https://academa.ai/lectures/bloom-filters?t=798.4666458333332): box\_skip is shown on the screen, written out. ##### [13:20.401](https://academa.ai/lectures/bloom-filters?t=800.4011458333333) Narration: A billion URLs at ten bits each is a gigabyte and a quarter, which fits in memory on any machine you would run a crawler on. The exact set was sixty four gigabytes, and a disk seek for every link on every page. Board: crawl — a Figure (x\_range=(0.0, 12.0), y\_range=(0.0, 6.4), aspect=(12.0, 6.4)); head\_crawl — a Heading that says "A Crawler That Has Seen a Billion URLs"; box\_link — a Polygon \[gray\] labelled "upright("URL found")" drawn in crawl (vertices=((0.6, 2.5), (3.2, 2.5), (3.2, 3.9), (0.6, 3.9)), filled=False); arrow\_in — an Arrow \[gray\] drawn in crawl (start=(3.4, 3.2), end=(4.4, 3.2)); box\_filter — a Polygon \[blue\] labelled "upright("Bloom filter")" drawn in crawl (vertices=((4.6, 2.4), (7.6, 2.4), (7.6, 4.0), (4.6, 4.0)), fill\_opacity=0.25); arrow\_fetch — an Arrow \[green\] labelled "upright("definitely new")" drawn in crawl (start=(7.8, 2.8), end=(8.9, 1.8)); box\_fetch — a Polygon \[gray\] labelled "upright("fetch")" drawn in crawl (vertices=((9.1, 1.1), (11.4, 1.1), (11.4, 2.3), (9.1, 2.3)), filled=False); arrow\_skip — an Arrow \[red\] labelled "upright("probably seen")" drawn in crawl (start=(7.8, 3.6), end=(8.9, 4.6)); box\_skip — a Polygon \[gray\] labelled "upright("drop")" drawn in crawl (vertices=((9.1, 4.1), (11.4, 4.1), (11.4, 5.3), (9.1, 5.3)), filled=False) Actions: - [13:24.129](https://academa.ai/lectures/bloom-filters?t=804.1286458333333): crawl moves to a new place on the board. - [13:24.129](https://academa.ai/lectures/bloom-filters?t=804.1286458333333): scale\_1 is shown on the screen, written out. ##### [13:34.818](https://academa.ai/lectures/bloom-filters?t=814.8176458333332) Narration: At seven hash functions the rate is eight in a thousand, so about eight million URLs out of a billion get reported as seen when they never were, and never get fetched. On a web that size, that is a rounding error in your coverage. Board: scale\_1 — a Math \[text\] that says "$m slash n = 10 arrow.r 1.25 thin upright("GB")$"; crawl — a Figure (x\_range=(0.0, 12.0), y\_range=(0.0, 6.4), aspect=(12.0, 6.4)); head\_crawl — a Heading that says "A Crawler That Has Seen a Billion URLs"; box\_link — a Polygon \[gray\] labelled "upright("URL found")" drawn in crawl (vertices=((0.6, 2.5), (3.2, 2.5), (3.2, 3.9), (0.6, 3.9)), filled=False); arrow\_in — an Arrow \[gray\] drawn in crawl (start=(3.4, 3.2), end=(4.4, 3.2)); box\_filter — a Polygon \[blue\] labelled "upright("Bloom filter")" drawn in crawl (vertices=((4.6, 2.4), (7.6, 2.4), (7.6, 4.0), (4.6, 4.0)), fill\_opacity=0.25); arrow\_fetch — an Arrow \[green\] labelled "upright("definitely new")" drawn in crawl (start=(7.8, 2.8), end=(8.9, 1.8)); box\_fetch — a Polygon \[gray\] labelled "upright("fetch")" drawn in crawl (vertices=((9.1, 1.1), (11.4, 1.1), (11.4, 2.3), (9.1, 2.3)), filled=False); arrow\_skip — an Arrow \[red\] labelled "upright("probably seen")" drawn in crawl (start=(7.8, 3.6), end=(8.9, 4.6)); box\_skip — a Polygon \[gray\] labelled "upright("drop")" drawn in crawl (vertices=((9.1, 4.1), (11.4, 4.1), (11.4, 5.3), (9.1, 5.3)), filled=False) Actions: - [13:37.268](https://academa.ai/lectures/bloom-filters?t=817.2676458333333): scale\_2 is shown on the screen, written out. - [13:43.479](https://academa.ai/lectures/bloom-filters?t=823.4786458333333): scale\_3 is shown on the screen, written out. ##### [13:48.944](https://academa.ai/lectures/bloom-filters?t=828.9436458333333) Narration: And notice which way the errors fall. What cannot happen is a page you have already fetched coming back as new. That is the one that puts a crawler in a loop, and it is precisely the answer the filter is exact about. Board: scale\_1 — a Math \[text\] that says "$m slash n = 10 arrow.r 1.25 thin upright("GB")$"; scale\_2 — a Math \[text\] that says "$epsilon approx 0.008$"; scale\_3 — a Math \[text\] that says "$8 dot.op 10^6 thin upright("pages skipped")$"; crawl — a Figure (x\_range=(0.0, 12.0), y\_range=(0.0, 6.4), aspect=(12.0, 6.4)); head\_crawl — a Heading that says "A Crawler That Has Seen a Billion URLs"; box\_link — a Polygon \[gray\] labelled "upright("URL found")" drawn in crawl (vertices=((0.6, 2.5), (3.2, 2.5), (3.2, 3.9), (0.6, 3.9)), filled=False); arrow\_in — an Arrow \[gray\] drawn in crawl (start=(3.4, 3.2), end=(4.4, 3.2)); box\_filter — a Polygon \[blue\] labelled "upright("Bloom filter")" drawn in crawl (vertices=((4.6, 2.4), (7.6, 2.4), (7.6, 4.0), (4.6, 4.0)), fill\_opacity=0.25); arrow\_fetch — an Arrow \[green\] labelled "upright("definitely new")" drawn in crawl (start=(7.8, 2.8), end=(8.9, 1.8)); box\_fetch — a Polygon \[gray\] labelled "upright("fetch")" drawn in crawl (vertices=((9.1, 1.1), (11.4, 1.1), (11.4, 2.3), (9.1, 2.3)), filled=False); arrow\_skip — an Arrow \[red\] labelled "upright("probably seen")" drawn in crawl (start=(7.8, 3.6), end=(8.9, 4.6)); box\_skip — a Polygon \[gray\] labelled "upright("drop")" drawn in crawl (vertices=((9.1, 4.1), (11.4, 4.1), (11.4, 5.3), (9.1, 5.3)), filled=False) Actions: - [13:52.114](https://academa.ai/lectures/bloom-filters?t=832.1136458333333): arrow\_fetch is indicated — a transient flash. - [13:58.151](https://academa.ai/lectures/bloom-filters?t=838.1506458333333): box\_fetch is indicated — a transient flash. ##### [14:2.826](https://academa.ai/lectures/bloom-filters?t=842.8256458333333) Narration: So that is the whole structure. Bits instead of items. k hash functions instead of a comparison. A false positive rate you can compute before you ship. And no deletions, ever. Board: Unchanged from the preceding beat in this scene. Actions: - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): crawl is hidden from the screen — left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): box\_link is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): arrow\_in is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): box\_filter is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): arrow\_fetch is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): box\_fetch is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): arrow\_skip is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): box\_skip is hidden from the screen — crawl left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): head\_crawl is hidden from the screen — left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): scale\_1 is hidden from the screen — left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): scale\_2 is hidden from the screen — left the board. - [14:16.2](https://academa.ai/lectures/bloom-filters?t=856.1995208333333): scale\_3 is hidden from the screen — left the board.