explain xkcd - User contributions [en]

2934: Bloom Filter

2024-08-20T15:09:47Z

Wertercatt: This should be cited

{{comic
| number = 2934
| date = May 17, 2024
| title = Bloom Filter
| image = bloom_filter_2x.png
| imagesize = 212x206px
| noexpand = true
| titletext = Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they're the right one you can never be sure.
}}

==Explanation==
The comic is about a data structure called a {{w|Bloom filter}}. Software engineers use Bloom filters to check if something is probably in a set or to estimate how many things are in that set, using limited memory.

* One example: the Chrome web browser used to store a Bloom filter of URLs that were known to be malicious<ref>Chromium Issue 10896048: Transition safe browsing from bloom filter to prefix set. (Closed) – https://chromiumcodereview.appspot.com/10896048/</ref>, based on a database that was too large to store locally. Chrome used that Bloom filter to confirm that it didn’t need to warn the user that they were visiting a malicious page. Only in the rare cases that the Bloom filter said the URL might be malicious, Chrome would send the URL to an external service to confirm whether it was known to be malicious. The developers didn’t want the browser to send ''every'' URL to the external service because that would leak the user’s entire browsing history to the service and would add an unnecessary network delay whenever a web page was loaded.

Here's how a Bloom filter works:

# ''' Adding items:''' When you add an item, it gets hashed (a way of transforming it into numbers) by several hash functions. These hash functions mark certain spots in a big array of bits (think of it as a row of lights that can be on or off).
# ''' Checking items:''' To check whether an item might be in the set, you hash it with the same functions and see if all the corresponding spots are lit up. If they are, the item might be in the set, but there's a chance of a false positive (the Bloom filter could mistakenly say the item is there when it’s not). If any spot is not lit up, the item is not in the set.
# '''False positives:''' The larger the array compared to the number of items, the lower the chance of false positives. For example, 10 bits per item gives each tested item a 0.1% chance of matching each item actually in the set.
# ''' Counting items:''' By analyzing the activated bits, with appropriate calculations, you can derive an estimate of ''how many'' individual items are 'stored' for confirmation within the array. This estimate's accuracy will depend upon several factors, but more array bits (making themselves potentially available to 'remember' each item) will be one of the most important ones when it comes to narrowing down the likelihood.

In the comic, [[Cueball]] is holding a piece of paper or tablet computer with a large "1" digit on it. This is labeled as a 1-bit Bloom filter, which is almost useless. When empty, it correctly returns a negative for any item tested, but as soon as one item is added the bit is set to 1, and now it unhelpfully says that any item tested might be in the set. Its size estimate also becomes "between 1 and infinity," which isn’t helpful.

Having multiple hash functions is pointless for a 1-bit filter since they all end up pointing to the same single bit, which would return the exact same answer as a result.

The title text carries the characteristics of the Bloom filter into the decision-making process for choosing a Bloom filter over other candidate data structures. Analogously (according to the text), you can be sure when they are ''not'' the best approach but only conclude that they ''are'' with a limited degree of probability.

==Transcript==
:[Ponytail holds out her hand to Cueball, who is holding a flat object with a 1 on it.]
:Ponytail: Does your set contai–
:Cueball: Yeah, probably.

:[Caption below the panel:]
:One-Bit Bloom Filter

==Trivia==
* The Bloom Filter was invented by Burton "Buzz" Bloom, who laughed when shown this comic and said "It's been a long time since I've done filtering... about twenty years."{{Actual citation needed}}

* Bloom Filters were also referenced in [[2739]] as a very lossy form of data compression.

==References==
<references/>

{{comic discussion}}

[[Category:Comics featuring Ponytail]]
[[Category:Comics featuring Cueball]]
[[Category:Statistics]]
[[Category:Programming]]

Talk:2750: Flatten the Planets

2024-02-22T18:23:36Z

Wertercatt: /* NASA's Response */

I have to wonder, would you slide down to the sun, or be flung outwards? [[User:SDSpivey|SDSpivey]] ([[User talk:SDSpivey|talk]]) 19:39, 15 March 2023 (UTC)
: The discs are centered on the orbit of the parent planet, and presumably rotating at the same frequency as the parent planet's orbit. That means the inner edge of each disc is going slower than you'd need to orbit the Sun at that distance, and the outer edge faster. If you moved inward from the original planet's orbit, the Sun's gravity would pull you in, but when you crossed the boundary to the next disc, you'd get flung back outward.[[Special:Contributions/162.158.62.61|162.158.62.61]] 19:58, 15 March 2023 (UTC)
::No Each planet fills out the space within their orbit into the next planet. Easy to see as the outer edge of Neptune's orbit is the same as with the planet flattened. There is a distance from Mercury to the Sun indicated. Maybe because it would melt if it got any closer? --[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 20:03, 15 March 2023 (UTC)
:::Take another look at the top and bottom images, you'll notice that the Neptune disc is significantly larger than Neptune's orbit (especially on the left hand side of the image). I suspect that, as the other response suggested Mercury and Neptune takes the inner edge of the disc as the average between Neptune and Uranus's orbital radii, and then the outer radius the same distance on the other side of Neptune's orbit. Similar for Mercury.
:::First, they're rings not discs, but I'm skeptical of the math. And it looks to me like the ring's edges are halfway between the orbits, with Neptune extended outwards the same distance as halfway to Uranus's orbit. [[Special:Contributions/172.69.22.4|172.69.22.4]] 20:08, 15 March 2023 (UTC)

{{cot|My mistake, Randall's math is correct, sorry.}}

{| class="wikitable" style="text-align: right;"
|-
! Planet !! Volume (109 km3) !! Orbital radius (106 km) || halfway to prior || halfway to next || Annulus area (10<s>9</s> ''12'' OOPS! km2) || Thickness (<s>cm</s> ''10s of microns'')
|-
| Mercury || 61 || 58 || 29 (to 0) || 83 || 19,000 || 321
|-
| Venus || 928 || 108 || 83 || 129 || 30,637 || 3,029
|-
| Earth || 1,083 || 150 || 129 || 189 || 59,942 || 1,802
|-
| Mars || 163 || 228 || 189 || 504 || 685,794 || 24
|-
| Jupiter || 1,4310,00 || 779 || 504 || 1,107 || 3,051,847 || 46,890
|-
| Saturn || 827,130 || 1,434 || 1,107 || 2,154 || 10,726,236 || 7,711
|-
| Uranus || 68,340 || 2,873 || 2,154 || 3,684 || 28,061,145 || 244
|-
| Neptune || 62,540 || 4,495 || 3,684 || 5,304 (symmetry) || 45,743,348 || 137
|}

:::: The volumes in this table are at 2 different scales. Only the Mercury to Mars volumes are at 1010 km3. Jupiter to Neptune are at 1012 km3 [[User:Sandor|Sandor]] ([[User talk:Sandor|talk]]) 21:01, 15 March 2023 (UTC)
::::: Thanks, fixed; I had the scale wrong for the radii too. [[Special:Contributions/172.71.158.231|172.71.158.231]] 21:16, 15 March 2023 (UTC)
:::Someone please double-check this, I think Randall is off by a factor of 1000. [[Special:Contributions/172.71.154.229|172.71.154.229]] 21:37, 15 March 2023 (UTC)
:::: I did my own spreadsheet, and my figures agree with Randall's (roughly). I think your thinkness figures are mostly out by 1000, and a few of your volume figures also have the wrong scale (Mercury is smaller than Mars, and the giants are too big by a factor of 10). [[User:Sandor|Sandor]] ([[User talk:Sandor|talk]]) 22:07, 15 March 2023 (UTC)
::::: 61 * 10^9 km^3 is [https://www.google.com/search?q=61+*+10%5E9+km%5E3+in+cm%5E3 6.1 × 10^25 cm^3], 19000 * 10^9 km^2 is [https://www.google.com/search?q=19000+*+10%5E9+km%5E2+in+cm%5E2 1.9 × 10^23 cm^2], and (6.1 × 10^25 cm^3) / (1.9 × 10^23 cm^2) is [https://www.google.com/search?q=%286.1+%C3%97+10%5E25+cm%5E3%29+%2F+%281.9+%C3%97+10%5E23+cm%5E2%29 3.2 meters]. I'm afraid I'm correct. [[Special:Contributions/172.69.22.145|172.69.22.145]] 22:31, 15 March 2023 (UTC)
::::: According to {{w|List_of_Solar_System_objects_by_size#Objects_with_radius_over_400_km}} yes I had Mars wrong (corrected) but the others are roughly correct. I stand by my claim that Randall is in error. [[Special:Contributions/172.71.154.86|172.71.154.86]] 22:39, 15 March 2023 (UTC)
:::::: Mercury's orbital radius is about 58 * 106 km, not 58 * 109 km, which makes the annulus' area 19000 1012 km2. [[User:Sandor|Sandor]] ([[User talk:Sandor|talk]]) 23:20, 15 March 2023 (UTC)
::::::: I fixed that label, hold on... [[Special:Contributions/172.71.154.86|172.71.154.86]] 23:30, 15 March 2023 (UTC)
::::::: You're right. Thanks. Sorry. Reverted on main. [[Special:Contributions/172.71.154.215|172.71.154.215]] 23:39, 15 March 2023 (UTC)

|} 

This makes about as much sense as other Flat Earth theories. [[Special:Contributions/172.70.200.137|172.70.200.137]] 20:00, 15 March 2023 (UTC)
:But this would actually be a flat Earth. Albeit with a rather larger surface area ;-) --[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 20:03, 15 March 2023 (UTC)
:And..the Earth-ring is not a disc and it's also in the same plane as the sun. Meaning If you were to stand on the surface of this ring earth , there would be a perpetual sunrise / sunset... And similar for everything else in the plane of the ecliptic. [[User:Iggynelix|Iggynelix]] ([[User talk:Iggynelix|talk]]) 12:36, 16 March 2023 (UTC)

But what does the plot of surface gravity vs distance from the Sun look like? Gravity of an infinite plane and all that?--[[User:Brossa|Brossa]] ([[User talk:Brossa|talk]]) 00:01, 16 March 2023 (UTC)

The explanation currently says that it would require "several solar system's worth" of matter, but isn't there enough matter in the actual solar system? --[[User:Purah126|Purah126]] ([[User talk:Purah126|talk]]) 00:49, 16 March 2023 (UTC)
:That was said in reference to the Alderson Disk, which requires 1000km or so of thickness. Clearly more than the proposal here that gives a minute thickness (relatively) from the ''actual'' planetary mass in the solar system. Even if you reduced its extent (smaller outer, bigger hole for the Sun) it wouldn't thicken up enough. The prior (non-xkcd) version would require a mass of material rivaling, if not exceeding, that of the Sun itself. [[Special:Contributions/172.70.162.222|172.70.162.222]] 02:07, 16 March 2023 (UTC)

One of the reasons NASA rejected this could've been the use of inches. [[Special:Contributions/172.71.102.13|172.71.102.13]] 02:26, 16 March 2023 (UTC)
: Except for Mars. I can only imagine that use of the metric system for the Mars ring is a reference to the [https://en.wikipedia.org/wiki/Mars_Climate_Orbiter#Cause_of_failure Mars Climate Orbiter] fiasco, which certainly would not endear Randall, or his proposal, to a NASA granting agency program officer. [[Special:Contributions/172.70.214.150|172.70.214.150]] 02:45, 16 March 2023 (UTC)
:: I assume the use of microns there is simply because 5/512 is a really awkward fraction. [[Special:Contributions/172.71.223.25|172.71.223.25]] 05:48, 16 March 2023 (UTC)
::: Awkward? Its vulgar! [[Special:Contributions/172.70.162.56|172.70.162.56]] 08:05, 16 March 2023 (UTC)
:: Oh right, the Mars Climate Orbiter reference makes sense! I was wondering why Randall would mix imperial and metric units like that. No sane physicist would do that, especially not Randall. [[Special:Contributions/172.71.250.88|172.71.250.88]] 12:52, 16 March 2023 (UTC)
::: And Randall rubs more salt into the wound by using "micron", when the formal/correct SI unit name is "micrometer".[[Special:Contributions/172.70.206.187|172.70.206.187]] 17:13, 16 March 2023 (UTC)

If the planets of the solar system were to become disks centered on the respective planet's current orbit, how do we deal with the different orbital eccentricities? For example, per That Other Wiki, Venus has an orbital eccentricity of 0.006772, Earth has 0.0167086, and Mars has 0.0934. Not to mention Neptune's 0.008678 and Pluto's 0.2488; Pluto's orbit actually crosses Neptune's. Surely that would cause issues with the disks? [[Special:Contributions/172.71.98.5|172.71.98.5]] 08:33, 16 March 2023 (UTC)
:Pluto isn't involved, so at least that difficulty doesn't have to be dealt with. Maybe Pluto and other dwarf planets could be used to supplement the asteroid ball bearings.[[Special:Contributions/172.71.242.63|172.71.242.63]] 10:55, 16 March 2023 (UTC)

It appears that there is enough material in the asteroid belt to do this, since a ring of asteroid ball bearings with a 1 trillion kilometer diameter where each ball bearing was a cube 1 meter by 1 meter (clearly more than enough!) would be less than 10 trillion cubic meters. Since the total mass of the asteroid belt is 10^21 kg, and the average density is around 2 g/cm^3, = 2000 kg/m^3, then the amount of matter required is 2,000*10 trillion = 2 quadrillion which is much less than 10^21. (Not sure if this is actually correct) --[[User:Purah126|Purah126]] ([[User talk:Purah126|talk]]) 12:17, 16 March 2023 (UTC)
:Ahh yes, the classic cubic-bearing. Just what we need in this planetary ring system we've created. Since Randall elects to eschew spheres for the planets, let's go all in and refuse them for the bearings as well. Bravo. ;-) [[User:Iggynelix|Iggynelix]] ([[User talk:Iggynelix|talk]]) 12:40-12:47, 16 March 2023 (UTC) 
::''I just want to say that this line of logic ''really'' tickled my funnybone. Well done! ...I've got no other valid contribution at this time, just that.'' [[Special:Contributions/172.70.90.101|172.70.90.101]] 13:11, 16 March 2023 (UTC)
::That was to further overestimate the material needed, since a cube is more mass than a sphere. {{cn}} --[[User:Purah126|Purah126]] ([[User talk:Purah126|talk]]) 15:09, 16 March 2023 (UTC)
Did anyone notice that this came out just after pi-day? [[User:Iggynelix|Iggynelix]] ([[User talk:Iggynelix|talk]]) 12:40, 16 March 2023 (UTC)
: That's really crusty of Randall. It does explain the rolling pin. He probably also knows, and chooses (for cause) not to disclose, that pronunciation of the Greek letter as "pie" [https://www.dude-n-dude.com/2023/03/14/amoebas-lorica-14-march-icymi/ doesn't conform to modern language usage]. [[Special:Contributions/162.158.90.232|162.158.90.232]] 17:01, 16 March 2023 (UTC)
:: for the same reasons outlined in the link, beta and phi are also pronounced differently, and I'm pretty sure zeta, eta, theta, xi and chi are too [[Special:Contributions/172.71.26.105|172.71.26.105]] 22:03, 16 March 2023 (UTC)Bumpf
:::Although all these terms were deliberately taken from ancient Greek, because that's when they were first proposed! I believe Pi was devised around 250 BC by the Greek mathematician Archimedes, and is sometimes called Archimedes' Constant. There is no reason to use more modern pronunciation, except to make jokes about "Pee Day", I suppose. Why are we talking of hypotheticals of Randall's knowledge and secret humor, anyways? Do we need such an elaborate justification to quote and link to this dude, "Amoebe"? Please wait til next time, next year![[User:Cuvtixo|Cuvtixo]] ([[User talk:Cuvtixo|talk]]) 22:40, 16 March 2023 (UTC)
::::Mathematicians have recognized that the ratio of a circle's circumference to its diameter is a constant since around 2000 BCE, but it was only given the symbol π in 1647 CE (and even then as the *p*erimeter of the circle; π wasn't used for the ratio until 1706). So if you want the pronunciation as it was when the usage was first proposed, you're looking for how English people would have said it in the 17th and 18th centuries, not how the ancient Greeks would have said it.[[Special:Contributions/172.70.114.88|172.70.114.88]] 17:55, 20 March 2023 (UTC)

I don't know if there's a non spoilery-way to mention that there are similar ideas explored in the novel ''Death's End'' by Liu Cixin. [[User:Nedlum|Nedlum]] ([[User talk:Nedlum|talk]]) 13:22, 16 March 2023 (UTC)

What would even happen here? Would the rings collapse into planets again? Where will the atmospheres go? Are the rings a uniform material like rock or many small pebbles? What happens at the borders? Would i be squished or will all life still be intact? If i a squished, do i have to put up with my worst enemy next to me? Will it be like the flat skins from //All Tomorrows//? Will i die? I expect to see this in «What If 2» coming out 13th october. [[Special:Contributions/172.68.134.38|172.68.134.38]] 14:31, 16 March 2023 (UTC)
:Presumably for the gas giants to hold a disc shape, the gas would have to be encased in hollow discs made out of the solid cores. How thick would the walls be? What if we used thinner cavities to store the inner planets' atmospheres as well? And how much would the core material decompress as a result of not being a core? [[User:Promethean|Promethean]] ([[User talk:Promethean|talk]]) 18:18, 16 March 2023 (UTC)
::isn't it hypothesized that they're "solid cores" are only solid because of the immense pressures? Like isn't much of Jupiter's inner core (or outer-inner core) metallic helium or something? My reading about this is outdated, but it's mentioned in the explanation that it requires "tensile strength beyond what is likely physically possible for any known form of matter." Actually I'm a little annoyed that this statement doesn't get "citation needed", rather than "planets of our solar system would not be suitable for this endeavor", because obviously if the first statement is true, the second needs no citation if the first is true, because no planet is made of unknown forms of matter. Correct?" [[User:Cuvtixo|Cuvtixo]] ([[User talk:Cuvtixo|talk]]) 22:19, 16 March 2023 (UTC)

Is there an element of Pluto discourse here? IIRC, one of the complaints about the "clearing your orbit" was that different metrics would 'punish' (for those who view the reclassification as a punishment) objects orbiting at a greater distance. I find the distribution of thicknesses really intriguing, and I wonder how the various dwarf planets at different parts of the system would stack up, thickness-wise. [newbyBoredAtWork]

I've replaced 'roller pin' with 'rolling pin' because a quick online search indicates that a roller pin facilitates relative motion, linear or rotary, between objects whereas a rolling pin is used to make a mass of material thinner, especially in culinary contexts.

I did an estmate of max 210m for the bearing sizes which is clearly enough even if I was off by a factor of a thousand, the proceedings are [https://0paste.com/448864 here] if someone wants to put it into the main article or check for errors. [[User:Xkcdjerry|Xkcdjerry]] ([[User talk:Xkcdjerry|talk]]) 12:48, 18 March 2023 (UTC)

== NASA's Response ==

Randall posted on Bluesky that he received a reply from NASA regarding this comic. They made some good jokes back at him, should this be added to the explanation? https://bsky.app/profile/xkcd.com/post/3klz7zr6s7i2x --[[User:Wertercatt|Wertercatt]] ([[User talk:Wertercatt|talk]]) 18:23, 22 February 2024 (UTC)

Talk:2750: Flatten the Planets

2024-02-22T18:23:08Z

Wertercatt: /* NASA's Response */ new section