text:
Talk:Bloom filter

A Graph
Maybe the following graph could be added to the "Probability of false positives" section. --Jerz4835 (talk) 12:29, 12 March 2008 (UTC)

this graph is weird. why is there no linear probability axis? i mean, this graph suggests that this is a shitty algorithm? the probability for false positives is really steep... --78.53.219.53 (talk) 13:00, 21 April 2010 (UTC)

 * The graph isn't really showing how "good" the bloom filter is, rather how various filter sizes and set sizes relate to the false positive rate. The probability axis emphasizes the area between 0 and 0.01 because differences there are a lot more meaningful than between, say, 0.99 and 1. Unfortunately I agree that it's not very clear at a glance, but I am no good at these types of visualizations and probably couldn't improve on it. Maybe someone else has ideas. Maghnus (talk) 04:11, 13 August 2010 (UTC)

The example
False positives are silly in a spelling checker. I think an example more like should be used, with the secrecy thing mentioned elsewhere. But my english very bad, so I leave in capable hands of brother and sister. —Preceding unsigned comment added by 220.233.116.128 (talk) 16:19, 9 January 2008 (UTC)

Completely agree, if you read the article your mind becomes "stuck" on the example; it is so silly you wonder if you misunderstood the concept. 80.79.35.68 (talk) 17:16, 11 January 2008 (UTC)Lambert

The example image both has k=3 and also includes 3 elements. This makes it less than ideal for explaining how the 'k' thing works. Rsclient (talk) 03:34, 1 May 2018 (UTC)

Operation Names
I propose changing insert to add and test membership to query. I think add better matches what actually happens and query is just more concise. --Pfunk42 22:42, 1 Jun 2005 (UTC)

Discoverer?
I propose changing discoverer in "...named after its discoverer Burton H. Bloom," to inventor. Algorithms like this aren't 'discovered' so much as invented.
 * I tried "conceived by" whoever in year whatever, a pattern I've seen elsewhere. Deco 01:21, 5 Jun 2005 (UTC)

Removing from a Bloom filter
It feels like you can't. This should probably be emphasized in the article, as this is a distinction from similar data structures. It's mentioned in the intro, but then never discussed...I don't have the technical expertise to say definitively how to handle this, so I can't write it up myself. -- Metahacker 15:32, 21 Jun 2005 (UTC)
 * Good idea. I added a short explanation. You think it'll do? Deco 19:46, 21 Jun 2005 (UTC)

While strictly speaking practical removal may not be possible in a simple Bloom filter, two facts presented in the article might use some clarification as to why removal is logically impossible. First, the universe can be represented by an "full" array, and second, Bloom arrays can be ANDed. In cases with a finite data universe the two of these seems to idicate that I could build the Bloom array of everything but the element I want to delete then AND that with the Bloom array I have. I can't say that I see this never introducing false negatives, but it does seem worthy of mention one way or the other by someone more apt in these things than myself. JonShops 03:06, 15 April 2007 (UTC)

 * The problem with that idea is that the Bloom filter corresponding to "universe minus my element" will almost certainly be identical to the Bloom filter corresponding to "entire universe". You'll never introduce a false negative, but you will usually introduce false positives — that is, if you take the Bloom filter for (A,B,C) and try to subtract out (B) using your method, you'll probably end up with the Bloom filter for (A,B,C). The "removal" didn't actually do anything! Hope this helps; also, check out the other variations mentioned on this Talk page. Some of them support removals, with various restrictions. --Quuxplusone 03:26, 15 April 2007 (UTC)

I know this discussion is a few years old, but you could technically remove items from a bloom filter if you use a counter array rather than a bit array. It kills the efficiency of the table, but at least you can remove items as long as you don't manage to overflow a given counter (but you'd hit false positives first.)  --Sigma 7 (talk) 17:36, 17 April 2010 (UTC)
 * Yes, that's already in the article under Bloom filter. —David Eppstein (talk) 18:13, 17 April 2010 (UTC)
 * What if you have a second Bloom filter, which stores a set of deleted items? So, check the first Bloom filter to see if the item was (at some point) a member of the set, then check the second Bloom filter to see if it was deleted.  Of course, there is a downside: once an item is deleted, you can never add that item again, simply because there's still no way to delete something from the second Bloom filter.  Well, unless you have *another* Bloom filter for 'undeleted' items, but it's not a practical solution.  For applications where deletion is irrevocable (such as with SSL certificates), this may be an extremely desirable feature. 208.81.212.224 (talk) 19:04, 24 October 2013 (UTC)
 * False positives in the second filter could be a problem... They would eliminate one of the more useful properties of Bloom filters, that its errors are only one-sided. —David Eppstein (talk) 19:12, 24 October 2013 (UTC)

Adding and removing in a single-bit Bloom filter
You could implement a voting algorithm in a single bit Bloom filter to allow both adds and deletes, at the cost of admitting false negatives, with an add setting k hash-bits, and a delete clearing k hash bits. The difference from an ordinary Bloom filter would be that the decision threshold would be less than requiring all k bits to be set for a rejection: for example, say, k/2, for say k=20. In this way, although both false-positive and false-negative results would be possible, the threshold factor could be tuned to give low error rates for both types of error.

Has anyone done this? Or are multi-bit Bloom filters simply superior? Inquiring minds weant to know. -- The Anome 13:54, September 9, 2005 (UTC)
 * Good question. I can't imagine why nobody's thought about this already, it's pretty obvious considering the implementation of your average BPP algorithm. I shall have to ask some people about it. Dcoetzee 08:03, 28 May 2007 (UTC)

Adding and removing in a counting Bloom filter
Riffing on The Anome's suggestion above: You could also implement a "counting" Bloom filter, by using b bits per hash instead of only one. For example, using b=2, you'd replace Bloom's array of m bits with an array of m 2-bit counters. Adding an element would increment all k relevant counters; if any counter was already at 3, it would "stick" there instead of wrapping around. Therefore, a count of 0 represents "absence," and a count of 1 or 2 indicates 1 or 2 entries sharing that counter. A count of 3 indicates at least three entries sharing that counter.

To remove an element, you'd decrement all k relevant counters, except for those counters that contained 3 — such a counter you'd leave at 3, since to decrement it would falsely imply that it was shared by exactly two entries.

This kind of "counting" Bloom filter would have all the problems with false positives of a normal Bloom filter, but it would allow a certain number of removals to proceed correctly. Add enough elements, though, and removals would stop working — you'd be unable to remove any element all of whose counters had maxed out.

I suspect that the added complexity of implementation wouldn't make a "counting" Bloom filter worth the trouble, but it's worth a mention on this Talk page, at least. :) --Quuxplusone, 19:06, 18 March 2006 (UTC)

 * ✅. Quuxplusone, that's a great idea, now in the article at Bloom filter. --DavidCary (talk) 16:52, 27 December 2020 (UTC)

Bloomier filter insertion
The bloomier filter insertion description is wrong:

"Now that we have the structure and a search algorithm, we also need to know how to insert new key/value pairs. The program must not attempt to insert the same key with both values. If the value is 0, insert the key into A0 and then test if the key is in B0. If so, this is a false positive for B0, and the key must also be inserted into A1 recursively in the same manner. If we reach the last level, we simply insert it. When the value is 1, the operation is similar but with A and B reversed.".

So any key in A0 that is a false positive in B0 must be present in A1 (and so on). But a key inserted in A0 might BECOME a false positive key in B0 after other insertions in B0. Imagine we insert a key in A0 which is "almost present" in B0 - only one of the k bits is not set; the key is not (yet) a false positive in B0. But after this, maybe we insert a key in B0 that also sets that kth bit to 1; now the initial key is in A0, it is a false positive in B0, and it is not in A1 - violating the data structure invariants. --Raduberinde 08:09, 28 July 2006 (UTC)
 * You're right. My mistake. I will reconsider the original paper. Dcoetzee 04:38, 25 May 2007 (UTC)

I think the paragraph on insertion in bloomier filter should be removed. The described bloomier filter is static, it doesnt permit insertion or deletion. The bloomier filter is constructed globally. I have added a section on dynamic bloomier filters that support insertions and deletions.
 * Okay, dynamic is certainly better - and surprisingly simple. We ought to still cite the original paper, but we can discuss the more recent result in detail. Dcoetzee 17:40, 24 July 2007 (UTC)

 * What is this "more recent result" about "dynamic bloomier filters that support insertions and deletions" you all are discussing?
 * The original reference "Chazelle et al. (2004)" (which is currently the *only* reference in the "Bloom filter" section) specifically says

"A data structure that supports only create and lookup is referred to as an immutable data structure. Note that although re-assignments to elements in S are made by set value, no changes to S are allowed. Our lower bounds show that, if we allow S to be modified, then linear size (measured in bits) is impossible to achieve regardless of the query time. In other words, Bloomier filters provably rule out fully dynamic operations."
 * Does this "more recent result" imply that the 2004 statement is now known to be incorrect? --DavidCary (talk) 21:29, 24 December 2020 (UTC)

You should break this into multiple pages
A bloom filter is a bloom filter - a counting bloom filter is a different beast with enough different permutations to discuss for the rest of eternity.

Break it into two - at least

 * ✅. That's been broken off into the counting Bloom filter article. --DavidCary (talk) 16:52, 27 December 2020 (UTC)

Generalized
Don't mean to be a wank, but has the "Generalized Bloom Filter" thingy been accepted into a peer-reviewed publication?

Regardless, the author should stick in info on how much bigger than a regular BF a GBF that uses ones and zeros needs to be to have the same false positive rate. Oh, I see. You forgot to mention that because it's A LOT (many times) bigger. ;) --pfunk42 04:35, 28 May 2007 (UTC)

Proof of false positive probability is wrong
The events of each particular bit being 1 are not independent. Intuitively, if you know the first bit mapped to 1, it suggests the array is more dense. That is, the probability the second bit maps to 1 given that the first did is greater than the probability the second bit maps to 1 given the first mapped to 0 (or say, given no other information). 128.2.16.192 22:49, 27 September 2007 (UTC)
 * First of all, i would call it an "analysis", not a "proof". And, in fact, this is an average case analysis, because it doesn't take into account the fact that the number of bits set in the Bloom filter from n additions follows a probability distribution, and with random hash functions, the number of set bits determines the false positive probability.  Thus, adding n things to a Bloom filter doesn't always result in a certain false positive probability--you might get lucky or unlucky.  But the variance is small.  There are possibly some other suble, mostly insignificant inaccuracies in that  formula.  See this paper for what seems to be a more detailed analysis, but it has not, to my knowledge been accepted under peer review.  --pfunk42 05:32, 30 September 2007 (UTC)

What are they used for?
What are bloom filters used for? Any applications people can think of should be put in the intro. Fresheneesz 02:09, 16 October 2007 (UTC)

 * No. Any applications people can source should be put into later parts of the article, and (per WP:LEDE) mentioned briefly in the intro. —David Eppstein 02:47, 16 October 2007 (UTC)

 * I agree with both of you -- this article should mention some applications, but in an "applications" section rather than the intro. It appears that has been done already with the Bloom filter section. Would it be better to split that section up into an "applications" section and a "extensions"/"generalizations" section? --DavidCary (talk) 21:29, 24 December 2020 (UTC)

meaning of bloom filter
if it gives "false positives" and "correct negatives" then it must be used to find whether element is *not* in a set (and so one would be 100% sure). maybe this article could be change according to it. 84.16.123.194 (talk) 15:47, 28 January 2008 (UTC)

 * I know this is old but this conclusion is either slightly incorrect or just poorly phrased. Bloom Filters are used to filter things out but not to conclusively determine whether an element is not in a set since it can return a "maybe" result. You can sometimes use it to avoid doing more expensive lookups/calculations if the Bloom Filter first determines your element is NOT in the set. 209.131.62.115 (talk) 05:49, 16 November 2013 (UTC)

Purpose of k hash functions?
Why are there k hash functions? Why would you need more than one? —Preceding unsigned comment added by 66.11.82.73 (talk) 15:07, 15 April 2008 (UTC)

 * You try doing it with one hash function and let me know what error bound you obtain.

 * This was confusing for me as well. Couldn't a single function duplicate the functionality of k hash functions? It's always been the case that a single function can call 10 different functions, for instance. Isn't the whole point that the single value ends up in k different places with a more or less even distribution? I can see the need for k different algorithms, maybe - although even then a little bit of modulus arithmetic would enable one to use a single algorithm in a loop k times and, again, would duplicate the functionality of using k different algorithms perfectly. So yeah, why the heck do you need k different hash functions? To answer your question, the error bound would be exactly the same. — Preceding unsigned comment added by 209.180.36.114 (talk) 20:31, 27 March 2013 (UTC)

I think it's unnecessarily ambiguous that the diagram in the Algorithm description has k=3 and also a set of 3 elements. To the novice like me it's initially confusing. Anyone agree? --Flexdream (talk) 15:35, 16 May 2012 (UTC)

Decay?
Can anybody provide a description of various techniques for decaying bloom filters? Google has hits for several different terms, "Scope Decay", "Deterministic Decay", "Time Decaying", etc. I conjecture this is a way to stochastically remove no longer relevant members from the set, but the articles I've found all require various subscriptions. nuffin (talk) 20:25, 26 July 2008 (UTC)

Filter size (m)
It would be helpful to note that the number of bits in the filter (m) should be a multiple of the expected number of elements (usually called n in the papers). Not as obvious as you might think. Could save someone's afternoon, a note like that... —Preceding unsigned comment added by 208.85.112.97 (talk) 15:15, 24 September 2008 (UTC)

k for a particular p
An interesting consequence of the formulas presented that if one wants a particular false positive rate, p, and intend to use the required number of bits (m) to get that rate for the number of entries (n) then the optimal number of hashes is
 * $$k=-\log_2 p\,.$$

regardless of the specifics. Although in some sense obvious (adding one more hash halves the false positive rate) it is a clean clear, simple and useful result. If you want, say, no more than one false positive out of 1024 tests, and you want to use the minimum number of bits in the filter, you will need at least 10 hashes. This might be worth including in the article. Topher Cooper--65.196.61.126 (talk) 22:12, 22 September 2009 (UTC)

 * I'm new to editing wikipedia, so please bare with me on this. I just made a change which I believe corrects the claim in the article which says that k is proportional to 1/p instead of, as you observe, log(1/p). Of course, it depends on how k is chosen, e.g., if is chosen to be optimal for the given m (size of bit vector) and n (number of elements inserted into the set), then k ~ log(1/p).

 * I didn't see your comment here until after I posted the change. I would welcome any feedback on this change since I want to make sure my edit is sound and you seem familiar with the math.

 * Queelius (talk) 09:05, 11 July 2014 (UTC)

Probability of false positives - demand for sources is a rejection of science and the scientific method.
Everything in the section "Probability of false positives" is verifiable from basic principles of mathematics and science by following the author's reasoning, thus the demand for proper authoritative sources is a rejection of science and the scientific method.

This section not original research, rather it is replicated research that each one and every one should replicate.

Roger Bacon was the first scientist since because insisted on observing things for himself and urged others to do the same. If Wikipedia prohibits people from doing the same, it becomes the holy book of a scientistic religion.

The motto of the Royal society was "Nullius in verba" meaning "Take no one's word for it".

Wikipedia is scientifically and morally wrong to demand that people take someone else's word for things. Replicability, not proper authority is the gold standard of truth. James A. Donald (talk) 02:48, 13 January 2010 (UTC)

 * Technically, a citation is required for the jump from (1-(1-m)^kn)^k to (1-e^(-kn/m))^k, since that requires some level of calculus. A better reason for removing the tag is that it echoed information found in an external link (and also has a hard reference), rather than complaining that Wikipedia doesn't follow the scietific method of more formal peer review.  --Sigma 7 (talk) 18:51, 17 April 2010 (UTC)

Hash Tables are no longer Hash Tables when they are Bloom Filters
Saying that a Bloom Filter at k=1 is a special kind of Hash Table (in the Space & Time Advantages section) seems counter intuitive. Hash Tables are deterministic and a Bloom Filter with k=1 is exactly what is described, not a surprising anomaly having to do with what happens when a Hash Table no longer checks for collisions and uses single bits rather than full entries. Specifically, "Note also that hash tables gain a space and time advantage if they begin ignoring collisions and store only whether each bucket contains an entry; in this case, they have effectively become Bloom filters with k = 1." should be removed for conciseness. Rbkillea (talk) 22:08, 6 December 2011 (UTC)

No other data structure?
The page says "Bloom filters also have the unusual property that the time needed either to add items or to check whether an item is in the set is a fixed constant, O(k), completely independent of the number of items already in the set. No other constant-space set data structure has this property."

It is misleading to think that no other data structure has the property of the complexity being independent of the number of elements in the set. However, vEB Trees, constant size Fenwick Trees and Segment Trees have this property. The running time is a function of the universe size and not the set size.

Maybe it needs to be made more clear that a constant running time, which is independent of the number of elements in the set is what is being talked about.

Dhruvbird (talk) 18:27, 2 February 2012 (UTC)

 * I agree with @Dhruvbird - [edit] There are, indeed, other data structures that are even actual Sets (containing data items or indicating a data item exists in the set) that do have constant "running time"..

[rest of this discussion was moved to "This page needs revision.."

 * TL;DR but it is indeed a constant-time set data structure (with one-sided errors). If you don't think so then you don't understand it. It is entirely possible that our article mis-states the time bounds for other alternative structures, however. —David Eppstein (talk) 03:56, 31 October 2013 (UTC)

Note: this discussion was edited and moved below for clarity and lack of offensiveness and furthering frustration at the wikipedia community..75.133.175.2 (talk) 15:40, 6 November 2013 (UTC)

This page needs revision - conflicts, clarity, the rest can stay as-is
I am going to be borrowing from another page, called a 'quotient filter', which is a derivative data structure which came from the idea of a bloom filter. It's usage, design, and purpose are exactly the same as a bloom filter, however, its implementation was performed in a way that 'enhances' what a bloom filter fails to do - where we can see in the bloom filter article that it needs restructured, which is a total restructure, as n changes.

Here are the changes I am proposing:

1. --> Clarify Introductory paragraphs to more accurately represent what the data structure is, what it is intended to be used for, and what it does and does not do.

[note] then add this (an important piece of information borrowed from quotient filters. I borrowed this from quotient filters, which has the exact same properties of a bloom filter only its internal representation is different.  Both a bloom filter and a quotient filter are equivalent data structures - probabilistic data structure filters...  This is a better description of what a bloom filter is, what it is used for, and why secondary storage is needed.  A bloom filter cannot resize without storing keys - if you think it can, I would love to see you try and build a bloom filter that can rehash and resize for optimal m and k as per p and n.  In fact, I would take great pleasure at seeing you attempt this impossible programming feat:

"Each Bloom Filter is associated with a more space-consuming set, such as a B-tree and its variants, or other disk-based algorithms, and its contents are reflective of the associated set. As elements – key/value pairs – are added to the set, their keys are also added to the Bloom Filter. However the Bloom Filter stores only a few bits per key, whereas the set stores the entire key, which can be of arbitrary size; therefore, a Bloom Filter can often be memory-resident while the associated set is stored in slower secondary storage. Thus this association can dramatically improve the performance of membership tests, because a test that results in "negative" (definitely not in the set) can be resolved by the Bloom Filter without necessitating any I/Os to access the set itself. The reason for having secondary storage, even though it is never accessed by the lookup operation for the stand-alone case of "negative" only lookups, is due to the fact that a bloom filter needs to resize according to the number of elements in the data set to account for optimally small false positive rates and therefore more definite "negative" results. If the bloom filter is static, the probability suffers where its size and hash usage are constants. A bloom filter cannot re-hash by itself, because it never stores any keys, only bits or numbers. Therefore, in order to resize the bloom filter we must at least store the actual keys somewhere. This gives the bloom filter the ability to re-hash, and therefore resize, without difficulty."

[note] Borrowing from 'Quotient Filter' page,

2. --> Algorithm Description section - careful on wording..

"To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem."

[note] The above paragraph just needs re-wording. This is also a fact. A bloom fiter cannot and never does say 'A contains x', it only says 'A may contain x with standard probability error p', basically meaning the only definitive test is 'x is not in A' - but that isn't even definitive, since as the bloom filter fills up, 'x is not in A' becomes 'A may contain x with standard probability error p' These are facts about the data structure. The more advanced techniques refer to other sections of this article...

"To query for an element (test whether it might be in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is definitely not in the set - if it were, then all the bits would have been set to 1 when it was inserted.  If all are 1, then either the element is in the set, or it actually is not (a collision resulting in a false positive).  More advanced techniques work out the problems of a normal bloom filter - such as dynamic resizing, allowing removal, and maintaing a preferable false positive rate."

[note] and the following paragraph

"One-time removal of an element from a Bloom filter can be simulated by having a second Bloom filter that contains items that have been removed. However, false positives in the second filter become false negatives in the composite filter, which may be undesirable. In this approach re-adding a previously removed item is not possible, as one would have to remove it from the "removed" filter."

[note] should read - this is factual. A bloom filter cannot be resized without rehashing, and most bloom filters are not constant-sized arrays. Therefore, if you want to resize a bloom filter secondary storage of keys is required. A scalable bloom filter does address the problem of resizing. Cite Scalable Bloom filter for more info, these are borrowed from the respective links to articles.:

"More advanced algorithms resolve the problem of not being able to remove from a bloom filter. Additionally, a bloom filter cannot be resized - in most proposed bloom filter algorithms there is no way to re-hash, since no keys are stored.  A Scalable Bloom Filter addresses this problem.  Additionally, if the actual keys are stored in secondary storage, this gives the bloom filter the ability to resize and re-hash, therefore implying that we can choose an optimal m and k for any p and n."

[note] The following should be added to algorithm description/merged into it somewhere. This is also fact. A bloom filter only says 'x maybe is in the set' or 'x is not in the set'. The probability of false positives is a probability application. Following probabilistic math, this means that if you have a 1% chance of error, then 1/100 queries, based on that probability, will return a false positive, on average. However, this is not exact - as you can see the probability of flipping a coin is 1/2, but usually by the sixth time you flip it will land on a different side eventually. This is a fact of probability. It is also fact that as the bloom filter fills up, if it doesn't resize itself, p will rise. This means more false positives and also less definitive negatives. That is a fact. The ''only way to have a constant bloom filter with acceptable p is to set its initial size arbitrarily large - which defeats the purpose of memory efficiency and also increase k, which worsens performance - usually to six hashes, according to your formulas...

"A bloom filter resolves two situations. The first is when a program only wishes to know whether an item is definitely not in the set.  In this situation, a bloom filter can be used as a stand-alone data structure.  However, if the program wants to know whether an item definitely is in the set, an accompanying data structure must be utilized.  The reason for an accompanying data structure in the latter case is because even though a bloom filter employs a 1% false positive rate storing fewer than 10 bits, and can be reduced easily to 0.1% - this still means that 1 out of every 100 or 1 out of every 1000 queries, respectively, will return a false positive in the general case; yielding an item that is not actually in the set when the bloom filter says it is.  As the data structure fills up and the bloom filter size in bits m and hash function numbers k are not set to ideal proportions of item numbers n, it becomes the case that the probability p will suffer, meaning higher chances of false positive lookups. This is especially a problem when n is dynamic and the bloom filter cannot resize itself without total reconstruction, if that is possible according to the implementation of the bloom filter. Therefore, care must be taken, unless using Scalable Bloom Filters, in choosing an optimal m and p."

[note] - this is also a factual statement. What would you call hashing to the same bucket? A collision. However, bloom filters do not provide collision resolution - that is how it arrives as a probabilistic data structure. Increasing false positive rates means that you have decreased the amount of definite negatives. What is a false positive? It is an item that is not in the set, but the bloom filter says it is. What would the inverse of that situation be? The bloom filter says it is not in the set. Because false positives exist - a false positive is actually a negative. Let x be 'maybe in Set' and y be 'not in set'. As n increases, and the bloom filter does not resize, p increases. As p increases, x gets bigger and y gets smaller. In fact, false positives only exist because y gets smaller. In other words, the negative members of x in a real data set would be members of y, or to put it more bluntly, false positives are members of y. understood? this is why you have an algorithm page that contradicts itself...

"Because the margin of error is usually 1% to test if an item is in the set, the bloom filter cannot guarantee with 100% certainty that an item actually is in the set. In fact, just like a hashtable; a bloom filter can have collisions.  A collision in a bloom filter is when an item lookup results in all 1s but is actually not in the set, meaning a false positive.  As the number of items it represents increases, the data structure, if left alone, continues to turn 'not in this set' to 'maybe in this set' - increasing false positive rates; also meaning negative results will dwindle to false positives.  An exhausted bloom filter, if it cannot be re-hashed, may get full at which point it considers almost everything 'a part of the set', and almost nothing 'not in this set'.  Hence the term probablistic bloom filter: it is a probablistic data structure, intended to be used as a filter."

[note] now the article does not conflict

3. --> Space and Time Advantages

[note] change the entire section to the following. The following paragraph re-iterates the points made above.. It does you all no good to discuss calculations if you are using a constant size m. Given a constant size m, why would you need to calculate m?  It would be a constant. So would k. Why do any calculation? The only time this is fine is if n is also constant - which in practice, n is hardly ever constant size. Therefore, if you do not resize, and therefore re-hash, and therefore need to store keys somewhere, then these calculations are meaningless. That's why I propose you state the following:

Bloom filters with 1% error and an optimal value of k requires only about 9.6 bits per element - regardless of the size of the individual elements. This advantage comes partly from its compactness, inherited from arrays, and partly from its probablistic nature. The 1% false positive rate can be reduced by a factor of ten by adding only about 4.8 bits per element. However, simple bloom filters and counting filters are static data sets - that also cannot be resized unless actual keys are stored somewhere. This is because items that are inserted do not store their keys - there is no way to re-hash. For this reason, we must either choose ahead of time an optimal, static m and then an appropriate k (meaning an unecessarily large data structure to account for any n items), or store the actual keys in secondary storage so we can re-hash the bloom filter and therefore acheive optimal, calculated m and k in accordance with any p and n.

[note] - see usage examples and actually read them

Its general use is to accompany and filter unecessary disk I/O, or avoid similar more costly operations - but will come at the cost of memory consumption, as well as insertions, removals, and lookups being in addition to the underlying secondary data structure. Filtering is employed to weed out what isn't in the set, but no matter how small the probability of false positives p, a bloom filter never says with absolute certainty whether or not an item is in the set - it just says it might be; and in addition it cannot find a nearest neighbor that definitely is in the set. In this situation, the bloom filter serves to eliminate, sometimes dramatically, unecessary operations simply by ruling out what items aren't members of a set - which results in performance enhancements on the secondary data structure lookup. See use cases below for examples of how this is used.

[note] - I do not see what's wrong with this statement, either.

For the case of lookups where the only concern is what definitely isn't in the set, it can be used as a stand-alone data structure; and in those cases it may be beneficial over other algorithms in terms of lookup speed 0(k) and memory consumption (m bits). Note that a Scalable Bloom Filter may reduce the need for setting m higher than is necessary relative to a dynamic n, but so too can re-hashing and therefore calculating appropriate sizes of m and k. If n is static, then m and k can easily be pre-calculated for optimization. See use cases below for examples of how this is used.

[note] cited from article

An example of the problem in practice with bloom filters using up more memory than desired or is ideal was proven by : "Counting Bloom Filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error, and support element deletions unlike Bloom Filters. However, they consume significant amounts of memory..."

[note] this is basically what you had, just re-worded slightly..

Bloom filters have the unusual property that the time needed either to add items or to check whether an item is potentially in the underlying data set is a fixed contant, 0(k) - where k is a multiple of hash functions, completely independent of the number of items already in the set. These lookups can also be parallelized, even in a multithreaded environment. This gives a bloom filter its main advantage over or in accordance with other data structures - like hashtables, tries, lists, or trees.

[auth]Thank you - sorry it got heated. All I wanted was for this page to get corrected and clarified. One person actually posted on a site saying it was a form of a trie. That is very incorrect, and I am assuming they got it off of this page..75.133.175.2 (talk) 18:54, 6 November 2013 (UTC)
 * Re your point #1, please see WP:TECHNICAL. The lead is supposed to be for an easy-to-read introduction to the subject. It is not supposed to be the place to go into this level of detail. And your writing could use copyediting, e.g. the last sentence no verb. And your last sentence in your last point, "A Bloom filter must be accompanied by..." is simply blatantly, false. There are plenty of use cases for Bloom filters that do not accompany it with another data structure. —David Eppstein (talk) 19:09, 6 November 2013 (UTC)

David: I'm assuming you meant the discription of the algorithm, and not the discription of a bloom filter's use as discussed on the very closely related quotient filter page (I would assume since a quotient filter is an equivalent algorithm, that page is at least not wrong - as noted by wikipedia by not saying that the quotient filter page does not contradict itself and has no errors in statement)...  So I moved it to 'Algorithm Description' above. I also moved more from 'Space and Time Advantages' above to 'Algorithm Description', since it made more sense for some of it to be moved in order to only discuss actual space and time advantages. If you feel that my last sentence is gramatically incorrect, feel free to modify it to fit your needs, or any other sentences that are gramatically incorrect (I'm not a writer by profession). Also, when you do agree on the wording, please then revise the bloom filter page itself - since you seem to be the most interested in its revision at this time... Also, 'A bloom filter must be accompanied by...' is not blatently false. Sure, there are situations, where the programmer just wants to know what isn't in the set. Then it can be used as a stand-alone structure. However, the only way to know whether an item is in the set is to have the 'bloom filter accompanied by...' (another data set). We are disagreeing here on a matter of a special case, when both of us are correct when you look at a bloom filter from a certain angle. But I would argue that in order to have optimal sizes of m and k, which is relative to n and desired p, we must at least store the keys in secondary storage so we can re-hash the bloom filter. Otherwise, there is no way to re-hash the bloom filter and we end up with a static set in which p suffers as n increases - meaning more false positives and less definitive negatives. The exact same feature is true of a quotient filter.

I'll make the corrections above, let me know when you have the time to actually read it. When we reach agreement, please update the bloom filter page with the changes.

75.133.175.2 (talk) 06:37, 7 November 2013 (UTC)
 * I think we are still far apart. You seem to have a very dogmatic point of view about what operations must be supported to call something a set data structure. Dogmatism and opinions are not a good mix for editing here, where you need to back up things with reliable sources. What are your sources? —David Eppstein (talk) 06:58, 7 November 2013 (UTC)

A set is a gathering together into a whole of definite, distinct objects of our perception [Anschauung] or of our thought – which are called elements of the set.

A set is a well defined collection of distinct objects. The objects that make up a set (also known as the elements or members of a set) can be anything: numbers, people, letters of the alphabet, other sets, and so on.

elements: wikipedia- The relation "is an element of", also called set membership, is denoted by the symbol "∈". Writing

x \in A

means that "x is an element of A". Equivalent expressions are "x is a member of A", "x belongs to A", "x is in A" and "x lies in A". The expressions "A includes x" and "A contains x" are also used to mean set membership, however some authors use them to mean instead "x is a subset of A".[1] Logician George Boolos strongly urged that "contains" be used for membership only and "includes" for the subset relation only.[2]

Another possible notation for the same relation is

A \ni x,

meaning "A contains x", though it is used less often.

The negation of set membership is denoted by the symbol "∉". Writing

x \notin A

means that "x is not an element of A".

The definition of a set sounds very vague at first. A set can be defined as a collection of things that are brought together because they obey a certain rule.

These 'things' may be anything you like: numbers, people, shapes, cities, bits of text ..., literally anything.

The key fact about the 'rule' they all obey is that it must be well-defined. In other words, it enables us to say for sure whether or not a given 'thing' belongs to the collection. If the 'things' we're talking about are English words, for example, a well-defined rule might be:

'... has 5 or more letters'

A rule which is not well-defined (and therefore couldn't be used to define a set) might be:

'... is hard to spell'

The mathematical requirements for a set means "distinct elements", and a requirement for elements in the set is both "A contains x AND x is not an element of A", and further a requirement for a set is that the set is "well defined, which means it enables us to say for sure whether or not a given 'thing' belongs to the collection".

Since ''a bloom filter does not have distinct elements, does not contain elements, and never says that for sure 'A contains x'; as such it is not a well-defined set - so according to mathematics, a bloom filter does not meet the requirements of a set - whereas a trie, hashtable, tree, list, etc. all do - because they meet not only the requirement that 'x is not an element of A' but also 'A contains X', contains distinct and definite elements, etc.

You seem to be very dogmatic in your understanding of set theory... I'll look for sources to back up statements and make adjustments since you cannot trust the advise of an expert on the subject of algorithms speaking plainly. That said, it is possible if I were to change this page you would either change it right back or put citations needed notices everywhere. I'll fix the above to only reference cited articles.. That way you can also trust the words of some other expert who is also just speaking their minds... Until then, david..

75.133.175.2 (talk) 06:31, 8 November 2013 (UTC)
 * I know what a set is. That wasn't the point, and cluttering up this talk page with copied and pasted definitions doesn't seem to be very constructive to me (nor does copying and reversing lines from my comments). The question was, what is your source for the assertions that Bloom filters are not data structures, do not (even approximately) represent sets, and can only used with an exact backing data structure? —David Eppstein (talk) 07:09, 8 November 2013 (UTC)

David: You asked for references - so I gave them. Sorry it cluttered the disussion up. If asking for references, citations, and external sources doesn't seem to be constructive to you, then I will simply stop here.

Your question 'the assertion that bloom bilters are not data structures' - is something I never said. I said they are not data sets - by mathematical definition.

Your next question, 'do not (even approximately) represent sets' is your implication - a twist of my words. I simply said a Bloom filter cannot be a set - because it does not meet the mathematical requirements of a set. I'm sorry it's taking this long to explain it to you. An approximate set is not a set. A bloom filter is more like a null set or not a set at all. There are no 'approximate sets' in mathematics. In fact, a set that is not well-defined or automic cannot be a set and therefore has paradoxes. In this case, the paradox is the false positives, where 'x is in A' becomes 'x may be in A' and 'y is not in A' becomes 'y may be in A', as the set fills up. In other words, it cannot say for certainty, in all truthfulness, the set requirement that 'x is in A' or 'y is not in A'. The reason for this is your false positive paradox. As such, you are defying mathematics by suggesting it is representative of a set. It is not a set, and approximate sets are paradoxes - and therefore an error, as shown.

Your third question, 'can only be used with an exact backing data structure' - is also a twist of my words. I said if n is dynamic, which it usually is - that means if you want an appropriate, calculatable value of m and k to guarantee a certain probability p you want according to the number of items n, then in that case you have to store the keys somewhere. That is because (fact) you cannot ever resize the bit array in a bloom filter because if you do not store the keys somewhere it is impossible to rehash - therefore impossible to resize. If you can't resize the data structure, then you pick a constant m and k, which means as the array fills p becomes larger - as per your page's own calculations. Picking a constant size m and k is a really poor choice...

Therefore, as n is usually not a constant size, where you say yourself a bloom fiter must allow for insertions and deletions - then how, pray tell me - do you suppose you resize the bloom filter? If you need to resize it, you must rehash it - therefore you have to store the keys somewhere in secondary storage. That's what I said, and it is completely correct and factual.

While we are talking about facts, let me go back to my original statement which you flat out refuse, along with any citations, facts, observations, or anything about this data structure - you just flat out refuse to read and accept things, and instead are insistant on just throwing up strawmen, argumentative abuses, and being rather ignorant and close-minded. You do not understand this data structure. Because you do not - and this wikipedia page clearly displays this, the web is full of false statements regarding bloom filters. In fact, it is my understanding that many of you are willing to accept a margin of error in lookups...:

Let me ask you this: Let's say your bloom filter set is your bank account. Would you want it to be 99% accurate? What if that 1% inaccurate thing that happens to you every month is a 1,000-1,000,000 dollar charge on your account - a charge that never really happened? Would you like that scenario? That is the same case as a bloom filter.

What if you went to the doctor, and he was 99% certain that you had cancer? What if the screening test was 99.9% accurate, and you test positive? let's further say you go on to surgery, where they find no tumor. You now owe millions of dollars in hospital and surgeon fees, you did the surgery and radiation for no reason, and you have to declare medical bankruptcy - destroying your credit and ability to purchase anything.

Do these scenarios sound acceptable to you? If they do, feel free to use a bloom filter as a set and accept the margin of error. If you think a data set must be well-defined and more exact, I suggest using a secondary data structure and using a bloom filter as the name implies - to filter out unecessary queries from the underlying data structure. I am done with you here, you are so ignorant...

2. I explain my points in the article and are observations and facts about the data structure - not my own opinion or 'dogmatic view', as you so put it..  Ignorance must be bliss, even on an encyclopedia. People use wikipedia as a source of correct information. Sad you all cannot correct this... I see now that this argument is just going to go on and on, with me pointing to ever more evidence only to be told 'nah - I don't agree with anything'. You must be republican or a member of the tea party :*75.133.175.2 (talk) 01:43, 9 November 2013 (UTC)

Separate derivation from results in the "Probability of false positives" section
The presentation might be clearer if we were to separate the formulas from their derivations in this section. Anyone agree/disagree? --Doradus (talk) 16:31, 8 November 2013 (UTC)

Imagine A World With An Infinitely Sparse Hash Table
"With unlimited core memory an error-free hash eliminates all unnecessary disk accesses..." Nice thought experiment, but back here in the 3rd dimension we could probably just say that an in-memory hash table based on some reasonable multiple of the size of your keys would suffice, and then from there go into how those requirements could be made lower with a compact Trie or a Bloom Filter. -- The Arcadian — Preceding unsigned comment added by 98.169.58.20 (talk) 21:34, 6 March 2014 (UTC)

 * Some anonymous user rewrote all the hypotheticals leading to such sentences. Anyway, I've changed "unlimited" to "sufficient", etc. Shreevatsa (talk) 10:36, 7 March 2014 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified 3 one external links on Bloom filter. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20070202202510/http://www.arl.wustl.edu:80/~sarang/ancs6819-dharmapurikar.pdf to http://www.arl.wustl.edu/~sarang/ancs6819-dharmapurikar.pdf
 * Added archive https://web.archive.org/web/20090517023058/http://adetti.iscte.pt:80/events/CONEXT06/Conext06_Proceedings/papers/13.html to http://www.adetti.iscte.pt/events/CONEXT06/Conext06_Proceedings/papers/13.html
 * Added archive https://web.archive.org/web/20070114035556/http://www.cs.utexas.edu:80/users/simha/publications/lsq.pdf to http://www.cs.utexas.edu/users/simha/publications/lsq.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at ).

Cheers.— InternetArchiveBot  (Report bug) 09:55, 4 November 2016 (UTC)

Chrome browser problem
A browser incompatibility is affecting the first sentence of "Algorithm description". The editor content is as follows.  An empty Bloom filter is a bit array of $m$ bits, all set to 0. There must also be $k$ different hash functions defined, In MS IE9 the text is correctly shown as:
 * An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined,...

but in Google Chrome the text is incorrectly shown as:
 * An empty Bloom filter is a bit array of  bits, all set to 0. There must also be   different hash functions defined,...

Perhaps the problem can be avoided by  replace $m$ by m, replace $k$ by k. Blooteuth (talk) 03:10, 26 December 2016 (UTC)
 * That would produce a slanted sans-serif letter m, where the result should be an italic serif m to indicate that it is a mathematical variable, not a fragment of emphasized text. —David Eppstein (talk) 04:31, 26 December 2016 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified 5 external links on Bloom filter. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added tag to https://git.postgresql.org/gitweb/?p=postgresql.git%3Ba%3Dcommitdiff%3Bh%3D9ee014fc899a28a198492b074e32b60ed8915ea9
 * Added archive https://web.archive.org/web/20140828071451/http://plan9.bell-labs.com/magic/man2html/8/venti to http://plan9.bell-labs.com/magic/man2html/8/venti
 * Corrected formatting/usage for http://www.arl.wustl.edu/~sarang/ancs6819-dharmapurikar.pdf
 * Corrected formatting/usage for http://www.adetti.iscte.pt/events/CONEXT06/Conext06_Proceedings/papers/13.html
 * Added archive https://web.archive.org/web/20090131053735/http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf to http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
 * Corrected formatting/usage for http://www.cs.utexas.edu/users/simha/publications/lsq.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 02:14, 22 July 2017 (UTC)

Word "bits" in intro
The use of the word "bits" in this sentence: "More generally, fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set." is incorrect. (I have seen this issue in academic papers otherwise, it might be wide-spread). Bits are a substance, and no substance I know has log(n) behavior in physical space with regards to its magnitude. 2^n *states* can be represented with n *bits*, and the correct word is *states*.MasterofAllWorlds (talk) 05:42, 20 September 2018 (UTC)
 * Uh, what? In what sense do you think this article is about physical space? —David Eppstein (talk) 06:32, 20 September 2018 (UTC)

 * I agree that "2^n *states* can be represented with n *bits*". However, the Bonomi 2006 article used to support that "10 bits" statement specifically says
 * "a Bloom filter offers very compact storage: less than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set."
 * Do you have any references or other way of showing that the correct word is "states" ? --DavidCary (talk) 21:29, 24 December 2020 (UTC)

Added External References and Contextual Text
Changes made to Bloom filter

 * Added an external reference for Kiss, et al
 * Added an introductory paragraph setting the technical context as of 2018, including the review by Luo, et al which is in arXiv.org, and the application by Dasgupta, et al, which appeared in the prestigious journal, Proceedings of the National Academy of Sciences

bayesianlogic.1@gmail.com 18:46, 4 December 2018 (UTC) Empirical bayesian (bayesianlogic.1@gmail.com)

Last Sentence of Intro
I'm not an expert on this particular topic but this sentence:

 * More generally, fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set.

...seems confusing and contradictory. I interpret this to mean that a bloom filter may incorporate less than 10 bits per element from the set that it is "filtering." In other words, if a bloom filter should have a 1% probability of returning a false positive when given an element from a target set, it may include less than 10 * n bits where n is the number of elements in the target set. But this implies that there's at least an approximate relationship between the number of bits in the filter and the number of elements in the set. So to say that the bits in the filter are independent of the number of elements in the set seems problematic. If I'm confused and that sentence actually intends to illustrate a different concept, then maybe it should be reworded for clarity?

--Davesque (talk) 01:37, 8 August 2019 (UTC)

Dependence of k on false positive rate p
Re your undo, I'm afraid I don't understand your objection at all; I believe I corrected an error and you reinstated it. As explains,"the required number of hash functions only depends on the target false positive probability p." When choosing parameters (for space efficiency, the common case), you want $$k = -\log_2 p.$$ That's what my edit tried to explain.

Perhaps my replacement text can be improved, but the original/reverted text says that $k$ is "proportional to the number of elements to be added" ($n$). This is flat wrong. It is proprtional to the ratio $m/n$, meaning that if you keep $m$ fixed, $k$ is inversely proportional to $n$. (Of course, normally you increase $m$ proportionally, making it independent of $n$.)

But $k$ in no way increases as $n$ increases, as the original/reverted text states.

In my replacement text, I assumed the common optimal-size case, which makes $k$ depend only on $p$, with full details described in.

So I believe I corrected an error in the article. Could we discuss this?

Tangent: Since you're interested in this area, it has occurred to me that I should create an article on the approximate member query abstract data type which describes the applications, and links to articles such as Bloom filter, quotient filter, cuckoo filterm etc. for possible implementations. This would migrate a lot of the current contents of the Bloom filter article. (There's also the interesting domain-specific example of probable prime tests.) Opinions or advice? 196.247.24.12 (talk) 02:08, 4 March 2020 (UTC)
 * The text in question is talking about the number of bits ($$m$$) in the Bloom filter, not the number of hash functions ($$k$$). Perhaps you misread it. The specific point in the changed text which makes clear that it is talking about $$m$$ is "$$m$$, which is proportional..." The number of bits needed for a Bloom filter (or anything else) to maintain false positive rate $$\varepsilon$$ for a set of $$n$$ elements is $$\Theta(n\log(1/\varepsilon))$$. Here, $$\varepsilon$$ is often taken as a constant (i.e. you are willing to take a fixed error rate rather than varying the error rate for different inputs), in which case one can simplify the formula for number of bits as $$\Theta(n)$$ as in the article. Instead, your version (if it is not just a misreading) treats the number of elements in the set as a constant and simplified the formula for the number of bits to $$\Theta(\log(1/\varepsilon))$$. It's not exactly wrong – there may be some applications of Bloom filters where you know you are only going to ever have 20 items (say) in your dictionary, so that you can treat $$n$$ as a constant, and where moreover you need variable false-positive rates and where the representation length of each item is so long that Bloom filters are a better choice than just keeping a static list of the items – but I think they're so rare compared to the other cases that your simplified version of the analysis is seriously misleading. —David Eppstein (talk) 02:22, 4 March 2020 (UTC)
 * Ah! I think I'm seeing it!  The original text is "Typically, $k$ is a constant, much smaller than $m$, which is proportional to the number of elements to be added;".
 * I read the part between the commas as a parenthetical phrase, i.e. "Typically, $k$ is a constant (much smaller than $m$) which is proportional to the number of elements to be added," a glaringly false statement which I leaped to correct.
 * If it's trying to say "Typically, $k$ is a constant, much smaller than ($m$, which is proportional to the number of elements to be added)," then we need a different grammatical construction, because that's not how operator precedence works in English grammar. I'll make another try; I'm currently thinking "Typically, $k$ is a small constant which depends on the desired false error rate, while $m$, is proportional to the number of elements to be added." 196.247.24.12 (talk) 02:38, 4 March 2020 (UTC)
 * P.S. I've noticed that the article uses both $p$ and $$\varepsilon$$ for the false positive rate, something that needs fixing. Any preference as to which?  (Personally, I like $ε$, since that implies "small".)  196.247.24.12 (talk) 03:14, 4 March 2020 (UTC)
 * They both make sense, but I think (without checking) I've seen $$\varepsilon$$ more often in the literature, and $$p$$ feels more generic to me. So I also prefer $$\varepsilon.$$ I did check two of my papers (on invertible Bloom filters and cuckoo filters) and they both used $$\epsilon$$ (not $$\varepsilon$$) but semantically $$\epsilon$$ and $$\varepsilon$$ are the same and $$\varepsilon$$ is less ambiguous (doesn't look like set inclusion) so probably better. —David Eppstein (talk) 05:41, 4 March 2020 (UTC)
 * In the few hours before your reply, I want ahead and made the above-mentioned edits to the article; I hope they're okay. Just for my peace of mind, could I confirm that we now both understand the original disagreement, and what needs to be fixed in the article to resolve it?  That is, I read the original as saying that $$k\propto n$$ which is Obviously Wrong, so I corrected it, while you read it as $$m\propto n$$ which is Obviously Right, so my "correction" was nothing of the sort.  The first two talk page sections above are us restating these positions to (past) each other, after which the light dawned that the root cause is an ambiguous piece of prose which needs to be made unambiguous.  We may yet go back and forth on wording, but there's no remaining disagreement about the facts.
 * (BTW, if you have a moment, I'd still appreciate even a brief word of encouragement/discouragement about my approximate member query article idea.) 196.247.24.12 (talk) 06:40, 4 March 2020 (UTC)
 * Yes, that looks like an accurate summary of recent edits. As for a broader overview of approximate member query data structures, sure, that sounds like a reasonable idea. I believe they're usually called filters, though, so Filter (data structure) might be a better name. Some of the less Bloomy material from this article could be migrated there, as well. —David Eppstein (talk) 08:35, 4 March 2020 (UTC)
 * Thank you! I just like to formally close the trouble ticket.
 * Yes, the idea is to reduce duplication among articles on various implementations by moving the material to a common page. But I think Filter (data structure) is a poor choice for two reasons:
 * I'm trying to describe an abstract data type, not a specific data structure. Like we don't have a page for Dictionary (data structure); it redirects to Associative array, a page which doesn't call it a data structure.
 * The name is already taken (both in WP and common usage) by Filter (higher-order function) which is the more general (and usually deterministic) operation of choosing a subset of the input by applying a predicate to each element.
 * The ADT I'm trying to describe is a particular type of probabilistic filter, one with a chance of error, but only in one direction. It's like a primality test in that way: the result is either "probably prime" or "definitely not prime".
 * I agree a good name is hard to find; indeed people often use "Bloom filter" generically. I'm happy to find an alternative, but "approximate member query" is the only generic term I've seen with any frequency in the literature. 196.247.24.12 (talk) 11:30, 4 March 2020 (UTC)

New proven false positive rate
There is new work on the false positive rate: Summary, publication, Presentation. I sadly haven't the time to integrate it at the moment. -- MichaelSchoenitzer (talk) 00:29, 27 July 2020 (UTC)

Typo in section "Probability of false positives": k vs m?
In the section "Probability of false positives", it starts with "m is the number of bits in the array" and "k is the number of hash functions" (after the first equation). Later, to derive \varepsilon, it is suddenly "Each of the k array positions". Shouldn't this be m instead of k, both in the text as well as the following formula? 79.208.245.153 (talk) 16:32, 10 September 2021 (UTC) anonymous (16:30), 10 September 2021 (UTC)

Futhermore, if this is indeed a mistake (as I suspect), it propagates to the next subsection "Optimal number of hash functions", which uses the same formula \varepsilon = ... . There, the erroneous k is replaced by another expression, potentially leading to a wrong result. anonymous.

Bits per element
"fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set"

I must be missing something: How do I determine how many bits per element I have, if the number of elements is variable? Perhaps this could be made clearer in some way.

title: Talk:Bloom filter


text:
User:Yue.san

「ユェ」 ("Yue" written in Kanji)

While known in various circles for having atrotious spelling, his grammer is fairly sound. Albeit not a long time contributor to wikipedia, he has been "around" for some time. Of course, like many other contributors, most edits were done without logging in, such as from the NSV stub (*July 12th, 2004, simply as 68.151.5.4). Some of these edits deserved mention, others.. didn't.

 * livejournal: daovanveries

Yue-chan was a good friend of alot of people.

We Hated him, Loved him, found him incredibly annoying. We laughed, we cried, we joked we argued. A relationship, friendship or other wise, has always had its ups and downs, as it does in most relationships. And Yue will never be forgotten, he was there for us when we needed him.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: User:Yue.san


text:
Category:Operas by George Frideric Handel

Georg Frideric Handel was a prolific composer of Italian Opera. Listed here are all of the Wikipedia articles about his operas.


text:
List of The Young and the Restless characters

This is a list of characters that appear (or have appeared) on the soap opera, The Young and the Restless.


text:
Howardian Hills

The Howardian Hills are an Area of Outstanding Natural Beauty (AONB) in England located between the Yorkshire Wolds, the North York Moors National Park, and the Vale of York. They are named after the Howard family who still own local lands.

Topography
The Howardian Hills form 79 square miles of well-wooded undulating countryside between the flat agricultural Vales of Pickering and York. The irregular 558 ft high ridges of the Howardian Hills are a southern extension of the rocks of the Hambleton Hills in the North York Moors. Jurassic limestone, pastures, and extensive woodland overlook the agricultural plains below. On the eastern edge, the River Derwent cuts through the Hills in the Kirkham Gorge, a deep winding valley formed as an overflow channel from glacial Lake Pickering.

Settlement
Although there are no towns within the AONB, the market towns of Helmsley and Malton lie just beyond the boundary. From Malton to Hovingham is a line of spring line villages. The majority of older buildings are made of locally quarried limestone with red pantile roofs and those which developed as part of the grand country house estates have largely retained a coherent identity. The village of Ampleforth and its Abbey and College lie within the area.

Land use
High grade arable land, pasture, and managed woodland makes this rich farming country whose diversity contributes to its attractive rural character.

Flora and fauna
The Howardian Hills AONB is a key area for several nationally important Biodiversity Action Plan (BAP) Priority habitats including lowland broadleaved woodland, wood pasture, veteran trees, limestone, and neutral grasslands and fen meadows. Characteristic species include brown hare, lapwing, tree sparrow, and barn owl as well as several local rarities such as knapweed broomrape and baneberry.

Howardian Hills Area of Outstanding Natural Beauty
Designated Area of Outstanding Natural Beauty (AONB); one of 46 areas in England, Wales, and Northern Ireland designated for conservation due to significant landscape value, along with National Parks and Heritage Coasts.

The Howardian Hills are designated an AONB because of the following Special Qualities:

 * Unusual landform: The Howardian Hills are the only area of Jurassic limestone in Northern England with AONB designation. Kirkham Gorge on the River Derwent, Yorkshire is a unique glacial overflow channel of great scientific importance.
 * A richly varied landscape: The landscape comprises a complex system of hills and valleys of woodland, arable fields, pasture, fens, hedgerows, stone walls, designed parklands, and scattered settlements.
 * Landscape of high visual quality: Diverse landform and land use with contrasting scale, colour, texture and form alongside historic houses, extensive woodland, sweeping views, farming landscapes, and traditional building styles provide great aesthetic appeal.
 * Remarkable heritage: A concentration of archaeological and historic features including Iron Age earthworks, medieval castles and monasteries, grand houses, and designed landscapes including Castle Howard, Newburgh Priory, Hovingham Hall, Gilling Castle, and Nunnington Hall contribute to the dramatic landscape.
 * An important wildlife resource: The area boasts outstanding wild plants and animals within the unique River Derwent and has nationally important fens as well as relatively extensive remnants of Ancient Semi-Natural Woodland.

Each of these attributes is important in its own right, but it is their combination in a relatively small area that has produced a landscape of national significance.

title: Howardian Hills


text:
Babahoyo River

The Babahoyo River is a river in western Ecuador, fed by tributaries rising in the Andes Mountains. It takes its name from the town of Babahoyo in Los Ríos. At Durán, it joins the Daule River to form the Guayas River, which continues to the Pacific Ocean.

The river is the backbone of trade in the city of the same name. Much of west-central Ecuadorian agricultural produce, especially rice, sugarcane, fruits, balsa wood, and tagua nuts are grown here.

title: Babahoyo River


text:
Courtenay Hughes Fenn

Courtenay Hughes Fenn, or C. H. Fenn, (April 11, 1866 – 1953) was an American Presbyterian missionary to China, and compiler of The Five Thousand Dictionary, a widely used basic Chinese-English dictionary that has gone through numerous reprints. Fenn's Chinese name was 芳泰瑞 (Fang Tairui).

Fenn was born in 1866 at Clyde, New York, U.S.A., the son of Samuel P. Fenn and Martha Wilson, and was ordained in 1890. He married Alice Holstein May Castle (d. 1938) on 8 June 1892 in Washington DC. They had a daughter, Martha Wilson Fenn, and two sons, Henry Courtenay Fenn, well-known American China scholar and architect of Yale University's Chinese language program, more commonly known as H. C. Fenn, (February 26, 1894 - July 1978), and William Purviance Fenn (born 1902) general secretary of the United Board for Christian Higher Education in Asia.

In China, Fenn was active in the Presbyterian Overseas Mission Board. He provided a photographic album as firsthand evidence of the Boxer Rebellion and Siege of Peking, 1900, now archived in the Yale Divinity Library, along with his typescript diary. Fenn had perhaps a rather dark view of his Chinese contemporaries, as can be adduced from several remarks attributed to him in New Forces in Old China (1904) by Arthur Judson Brown:

"Any man who has had the least occasion to deal with Chinese courts knows that `every man has his price,' that not only every underling can be bought, but that 999 out of every 1,000 officials, high or low, will favour the man who offers the most money."

"...every village and town and city—it would not be a very serious exaggeration to say every home,--fairly reeks with impurity."

"I would be almost willing to assert that it is impossible for a man, brought up in China, then spending many years abroad, to return to China and write such a book in honesty and sincerity of heart. He could not possibly help knowing that nine-tenths of what he was writing about China was absolutely untrue, that her political, legal, social, domestic and personal life are rotten to the core..."

Isaac Taylor Headland of Peking University, in his book The Chinese Boy and Girl, recounts that his own interest in Chinese children's rhymes began with a summer-time conversation with Mrs. Fenn on the veranda of the Fenns' house in the hills, fifteen miles west of Peking, in which he heard a nurse teach the following rhyme to her child Henry Fenn:

He climbed up the candlestick, The little mousey brown, To steal and eat tallow, And he couldn't get down. He called for his grandma, But his grandma was in town, So he doubled up into a wheel, And rolled himself down.

Selected works

 * The Providence of God in the Siege of Peking, date unknown
 * "The American Marines in the Siege of Peking." Independent 52, no. 2713 (29 November 1900): 2845-2849
 * Over against the treasury; or, Companions of the present Christ, a vision, 1910
 * With you always; a sequel to "Over against the treasury,", 1911
 * The Five Thousand Dictionary (1926 and revisions), with Mr. Chin Hsien Tseng
 * The Chinese English Pocket Dictionary (1944)

title: Courtenay Hughes Fenn


text:
Nancy Temple

Nancy Anne Temple is an attorney specializing in accounting liability. She was the in-house attorney for Arthur Andersen, who advised Michael Odom and David B. Duncan about Arthur Andersen policies regarding retention of documents from client engagements. Duncan oversaw the shredding of Arthur Andersen documents concerning their work for client Enron, between October 22 and November 9, 2001 (See the Timeline of the Enron scandal). A memo from Nancy Temple played a key role in the conviction of Arthur Andersen on charges of obstruction of justice. That conviction was later overturned.

Pre-Andersen
Nancy Temple graduated from the University of Illinois College of Business in 1986 with a Bachelor of Science in Accountancy. After graduation, Ms. Temple attended Harvard Law School where she graduated with a Juris Doctor in 1989. She began her career at Sidley Austin Brown & Wood, now known as Sidley Austin. She worked at the law firm for 11 years and was inducted as a partner. Ms. Temple specialized in accounting liability.

Arthur Andersen conviction overturned
On May 31, 2005, the United States Supreme Court overturned the conviction of Arthur Andersen in a unanimous decision.

Chief Justice William H. Rehnquist, writing for the court, said the former Big Five accounting firm's obstruction-of-justice conviction was improper because the instructions at trial were too vague for jurors to determine correctly whether Andersen obstructed justice. "'[T]he jury instructions at issue simply failed to convey the requisite consciousness of wrongdoing," he wrote. "[I]t is striking how little culpability the instructions required."

In post-conviction interviews, several of the Arthur Andersen jurors indicated that the "guilty" verdict was proximately based upon an internal October 16, 2001 email from in-house Arthur Andersen attorney Nancy Temple. The text of the email from Nancy Temple is as follows:

The Supreme Court's unanimous reversal of the conviction reinforces the opinion that the jury should not have inferred any liability on Arthur Andersen based solely upon the October 16 memo. Rather, Ms. Temple's bar license required that she not do anything that would waive the "attorney-client" privilege of Enron or Arthur Andersen. By having her name and a legal reference removed, in effect she was making the subject memo suitable for public disclosure – it was no longer a "privileged" document.

In addition, public accounting firms had a duty to notify the SEC within a defined time window if the accountants disagreed with a public accounting filing by a client. Ms. Temple's memo notes that the subject matter at issue was determined not to be of a nature that would require that Arthur Andersen to notify the SEC - i.e., a "Section 10A" filing, and her memo indicates that she will consult with the lawyers – again – to verify that conclusion.

Post-Andersen
Nancy Temple is now married and has three sons. After the Arthur Andersen case, Ms. Temple began working for Freeman, Freeman & Salzman P.C., a currently defunct law firm. On April 1, 2008, Ms. Temple returned to practice law at Katten & Temple LLP, a firm she co-founded. The firm specializes in litigation.

title: Nancy Temple


text:
King-Emperor

A king-emperor or queen-empress is a sovereign ruler who is simultaneously a king or queen of one territory and emperor or empress of another. This title usually results from a merger of a royal and imperial crown, but recognises the two territories as different politically and culturally as well as in status (emperor being a higher rank than king). It also denotes a king's imperial status through the acquisition of an empire or vice versa.

The dual title signifies a sovereign's dual role, but may also be created to improve a ruler's prestige. Both cases, however, show that the merging of rule was not simply a case of annexation where one state is swallowed by another, but rather of unification and almost equal status, though in the case of the British monarchy the suggestion that an emperor is higher in rank than a king was avoided by creating the title "king--emperor" or "queen-empress" instead of "emperor-king" or "empress-queen".

In Austria-Hungary
Another use of this dual title was in 1867, when the multi-national Austrian Empire, which was German-ruled and facing growing nationalism, undertook a reform that gave nominal and factual rights to Hungarian nobility. This reform revived the Austrian-annexed Kingdom of Hungary, and therefore created the dual-monarchic union state of Austria-Hungary and the dual title of "emperor-king" (in German Kaiser und König, in Hungarian Császár és Király).

The Habsburg dynasty therefore ruled as Emperors of Austria over the western and northern half of the Empire (Cisleithania), and as Kings of Hungary over the Kingdom of Hungary and much of Transleithania. Hungary enjoyed some degree of self-government and representation in joint affairs (principally foreign relations and defence). The federation bore the full name of "The Kingdoms and Lands Represented in the Imperial Council and the Lands of the Crown of St. Stephen".

In the Italian colonial empire
Following the Italian occupation of Ethiopia in 1936, King Victor Emmanuel III was proclaimed Emperor of Ethiopia. Thus, he became the King-Emperor (in Italian Re Imperatore), ruling over both the Kingdom of Italy and the Ethiopian Empire.

The King-Emperor was represented by the Viceroy, who was also appointed as Governor-General of Italian East Africa (AOI – Africa Orientale Italiana). The capital city of the Viceroy and Governor-General was Addis Ababa.

In the German Empire
In 1871, the North German Confederation united with the Southern German states to form the German Empire. The Constitution stated that the King of Prussia, then William I, would be crowned German Emperor (Deutscher Kaiser). William wanted to be proclaimed Emperor of Germany (Kaiser von Deutschland), but this would have caused sovereignty problems with the southern German princes and also with Austria.

After the devastating loss in the First World War and the German Revolution, Emperor William II attempted to abdicate the throne of Germany while retaining his throne as King of Prussia, believing the Kingdom of Prussia and the German Empire to be in a personal union. But after being informed that he could not abdicate one throne without the other, William was forced to abdicate both thrones and lived the rest of his live in exile in the Netherlands.

In the British Empire
The British Crown had officially taken over the governing of British India from the East India Company in 1858, in the aftermath of what the British called 'the Indian Mutiny'. Henceforth, India (including British India and the Princely States) was ruled directly from Whitehall via the India Office. In 1876, Queen Victoria was recognized as Empress of India by the British Government, via the Royal Titles Act 1876; this title was proclaimed in India at the Delhi Durbar of 1877. She was thus the Queen-Empress, and her successors, until George VI, were known as King-Emperors. This title was the shortened form of the full title, and in widespread popular use.

The reigning King-Emperors or Queen-Empress used the initials R I (Rex Imperator or Regina Imperatrix) or the abbreviation ''Ind. Imp. (Indiae Imperator/Imperatrix) after their name (while the one reigning Queen-Empress, Victoria, used the initials R I, the three consorts of the married King-Emperors simply used R'').

British coins, and those of the British Empire and Commonwealth dominions, routinely included some variation of the titles ''Rex Ind. Imp.'', although in India itself the coins said "Empress", and later "King Emperor." When, in August 1947, India became independent, all dies had to be changed to remove the latter two abbreviations, in some cases taking up to a year. In the United Kingdom, coins of George VI carried the title to 1948.

Titles

 * The Serbian emperor Stefan Dušan (r. 1346–55), who started off as king (1331–46), is attested with the title "Emperor of Greece and King of All Serb Lands and the Maritime" in a document dating to between 1347 and 1356 (see also Emperor of the Serbs).
 * The Holy Roman Emperors were also Kings of Italy, Bohemia, Germany, Burgundy, and/or Hungary for most of the time that title existed.
 * Napoleon was simultaneously Emperor of the French and King of Italy. His title was shortened to "Emperor-King" (Empereur-Roi or l'Empereur et Roi) rather than "King-Emperor".
 * John VI of Portugal was made titular Emperor of Brazil alongside being King of Portugal and was titled King-Emperor until his death. After John VI's death, his son Pedro briefly succeeded him as King of Portugal while reigning as Emperor of Brazil.

title: King-Emperor


text:
Talk:Bittell Reservoirs

External links modified
Hello fellow Wikipedians,

I have just modified 2 one external links on Bittell Reservoirs. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20050728085100/http://homepages.rya-online.net:80/barntgreensc/ to http://homepages.rya-online.net/barntgreensc/
 * Corrected formatting/usage for http://www.westmidlandbirdclub.com/archive/bittell-38.htm

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at ).

Cheers.— InternetArchiveBot  (Report bug) 09:41, 3 November 2016 (UTC)

title: Talk:Bittell Reservoirs


text:
Wikipedia:Articles for deletion/Fat american

 This page is an archive of the discussion about the proposed deletion of the article below. This page is no longer live. Further comments should be made on the article's talk page rather than here so that this page is preserved as an historic record. The result of the debate was - deleted - SimonP 15:21, Jun 15, 2005 (UTC)

Fat american
God bless the USA - and delete this rant --Doc (?) 22:49, 1 Jun 2005 (UTC)
 * We already have Ugly American. Delete. Fire Star 22:51, 1 Jun 2005 (UTC)
 * Keep, for now. Americans are, by and large, fat, and this sounds like a real slur.  Also, people who write lame pseudo-Christian shit like "God bless the USA" are... personal attack removed. (anonymous comment by User:Stiegl).
 * I was being semi-ironic - but you are just being plain ignorant --Doc (?) 23:25, 1 Jun 2005 (UTC)
 * Doc, I think he just insulted you. PERSONAL ATTACK ALERT! Nestea 01:23, 2 Jun 2005 (UTC)
 * comment: could be real. Americans are quite fat.  Perhaps someone could verify. Budovice 23:34, 1 Jun 2005 (UTC)
 * delete unsalvageable POV rant Fornadan (t) 23:46, 1 Jun 2005 (UTC)
 * As a fat American, I demand equal time for fat Canadians, fat Mexicans, and fat people from whatever other countries there are in the world. Either that, or Delete this POV rant. (Oh, and indeed, $DEITY bless the USA.) A и D я 01D  TALK  EMAIL  00:26, Jun 2, 2005 (UTC)
 * Delete content, then maybe redirect to Ugly American. -- BD2412 talk 00:44, 2005 Jun 2 (UTC)
 * Delete rant nonsense. You don't see me writing an article on how annoying the French are... ;P  --Etacar11 01:09, 2 Jun 2005 (UTC)
 * America could sure use some blessings, but delete. --Tydaj 01:30, 2 Jun 2005 (UTC)
 * Delete. I'm an American, and I've never heard this.  The article doesn't seem to follow NPOV very well. --Idont Havaname 02:35, 2 Jun 2005 (UTC)
 * Perhaps because you are an American, that you've never heard of it. 132.205.44.134 16:40, 2 Jun 2005 (UTC)
 * Delete POV rant --Chill Pill Bill 02:52, 2 Jun 2005 (UTC)
 * Delete agree with the Doc. K1Bond007 05:17, Jun 2, 2005 (UTC)
 * Delete rant. Sjakkalle 07:01, 2 Jun 2005 (UTC)
 * CLEANUP rant; I've heard of this term, but AFAIR, it means the gluttonous American who uses disproportionate amount of resources, and has obvious displays of avarice and gluttony, without a care for the needy of the world, or environment, etc. who claims that it is their fair share that they are using, and that the fair share for say India, is much smaller per capita (this is either because of a per nation POV or a per acre POV, instead of a per capita POV, if said American were blameless) (most obvious example: Anti-Kyoto accord ads in the US saying it's not fair that the US has to reduce greenhouse emissions while China does not, and that China will have more emissions that the US... fair if looked at from a per acre or per nation POV, unfair if looked at a per capita POV. Since the US is a "great bastion of democracy", the per capita POV should be the most appropriate one) 132.205.44.134 16:40, 2 Jun 2005 (UTC)
 * Delete. — Phil Welch 01:06, 3 Jun 2005 (UTC)
 * Merge with Cuisine of the United States     16:52, 4 Jun 2005 (UTC)

 * This page is now preserved as an archive of the debate and, like some other VfD subpages, is no longer 'live'. Subsequent comments on the issue, the deletion, or the decision-making process should be placed on the relevant 'live' pages. Please do not edit this page.


text:
User talk:Cfs-news

Welcome!

Hello,, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Here are a few good links for newcomers: I hope you enjoy editing here and being a Wikipedian! Please sign your name on talk pages using four tildes (~~); this will automatically produce your name and the date. If you need help, check out Where to ask a question, ask me on my talk page, or place  on your talk page and someone will show up shortly to answer your questions. Again, welcome! SaltyPig 22:50, 2005 Jun 1 (UTC)
 * The five pillars of Wikipedia
 * How to edit a page
 * Help pages
 * Tutorial
 * How to write a great article
 * Manual of Style

Watergate scandal
i was getting ready to revert your recent paragraph addition to this article, but saw that you appear to be new here, and wanted to spare you that shock i got when one of my first contributions was reverted. my problem with the addition is that it's, in my opinion, unnecessarily wordy, and contained unencyclopedic phrases such as, "A few might speculate". in particular, this sentence is, in my opinion, ungrammatical and almost unreadable:

"But because such an action would be so highly unethical, and because President Nixon had such a relative advantage in the polls and so such an illicit action would be so foolhardy with much to lose if discovered, therefore any link between the president's re-election campaign and this "third -rate burglary" was unimaginable for the vast majority of Americans at this early point in the scandal."

the standard wikipedia recommendation is that i should just make the changes i see fit, rather than considering you the "author" of the section. however, since wikipedia can be a strange situation to get used to, i wanted to run it by you first. i'll be happy to discuss further with you, or i will make the changes if you don't. SaltyPig 22:50, 2005 Jun 1 (UTC)

Merge discussion for Walt Whitman Birthplace
An article that you have been involved in editing, Walt Whitman Birthplace, has been proposed to be merged into another article. If you are interested in the merge discussion, please participate by going, and adding your comments on the discussion page. Thank you. • Gene93k (talk) 17:03, 12 May 2008 (UTC)

Speedy deletion of Canova (medicine)
A tag has been placed on Canova (medicine), requesting that it be speedily deleted from Wikipedia. This has been done under section G11 of the criteria for speedy deletion, because the article seems to be blatant advertising which only promotes a company, product, group, service or person and would need to be fundamentally rewritten in order to become an encyclopedia article. Please read the guidelines on spam as well as FAQ/Business for more information.

If you think that this notice was placed here in error, you may contest the deletion by adding  to the top of the page that has been nominated for deletion (just below the existing speedy deletion or "db" tag), coupled with adding a note on the talk page explaining your position, but be aware that once tagged for speedy deletion, if the article meets the criterion it may be deleted without delay. Please do not remove the speedy deletion tag yourself, but don't hesitate to add information to the article that would would render it more in conformance with Wikipedia's policies and guidelines. Lastly, please note that if the article does get deleted, you can contact one of these admins to request that they userfy the article or have a copy emailed to you. Chasingsol(talk) 16:43, 15 January 2009 (UTC)

title: User talk:Cfs-news


text:
Slabtown (Atlanta)

Slabtown or Slab Town was a red-light district that developed in Atlanta in the 1840s. The neighborhood, which was the site of a railway terminus, was located off present-day Decatur Street. In the 20th, century Grady Memorial Hospital was developed at this site.

The area's structures were built by poor workers and settlers largely with slabs and leftover lumber from pioneer Jonathan Norcross's sawmill. As the railroad terminus grew, this area was associated with brothels, saloons, and gambling.

History
Dubbed the "Father of Atlanta" and "hard fighter of everything," Jonathan Norcross was a pioneer in the railroad town. Born in 1808 and raised in Maine, along with his six siblings.

Following Indian Removal in the 1830s, in 1844 Norcross moved to northern Georgia, where he became a successful dry goods merchant and sawmill operator. His sawmill produced mainly railroad ties and string timbers for the assembly of the Georgia Railroad, which had a terminus at Atlanta. Reclaiming timber and debris discarded by the sawmill, poor settlers quickly began building crude shanties for their families.

Rise and fall
In 1845 pioneer life could be characterized as desolate and distinct with simple pleasures. The numerous male railroad workers in Atlanta sought rough trade. About 15 years before the American Civil War was a time of ill repute for Atlanta; the railroad town was known for vice and political corruption. A collection of huts, whorehouses, shacks, and saloons began developing in the settlement.

Norcross commented, "the reason why the streets are so crooked, is that every man built on his land just to suit himself." He was elected as the fourth mayor of Atlanta.

Slabtown was considered a "wicked development" that offended "the good citizens of Atlanta, as crimes were often committed there, and many of the young men fell into bad habits from frequenting Slab Town. In these places, occurred scenes of debauchery and indecency that shocked the moral sense of the community."

Atlanta's leaders demonstrated the need for law and order by their hasty municipal decisions. In 1902 an informal militia in disguise, known as White Caps, attacked Slab Town by night. They whipped the men found in huts devoted to prostitution and other vices, and warned them to leave town. They burned down the shanties and the area was abandoned. The residents were displaced by force. As Atlanta developed in the 20th century, this area was redeveloped for what is now Grady Memorial Hospital.

21st-century art and Slabtown
In early February 2010, Atlanta BeltLine, Inc. (ABI) and Atlanta's Office of Cultural Affairs developed a project Art on the BeltLine: Atlanta's New Public Place as part of redevelopment of the former industrial areas around the city. They sequenced visual and performance art installations, as well as historic site interpretations, at different points along the Atlanta BeltLine to draw the public. A sculptural homage of the City's historic Slabtown was assembled by the contemporary art collective THE STATUS FACTION. Located on Irwin Street at the BeltLine, the Slab Town installation resembles the "slab-style residences" which were destroyed and abandoned in 1902.

title: Slabtown (Atlanta)


text: Category:Operas by William Bolcom

title: Category:Operas by William Bolcom


text:
User talk:Sean Garrett

Wow! What an amazingly true article.

title: User talk:Sean Garrett


text:
What's in the Box

"What's in the Box" is episode 144 of the American television anthology series The Twilight Zone. It originally aired on March 13, 1964 on CBS. In this episode, a man's television set displays his past, present, and future, revealing to him that he will kill his wife.

Opening narration
Portrait of a TV fan. Name: Joe Britt. Occupation: cab driver. Tonight, Mr. Britt is going to watch "a really big show," something special for the cabbie who's seen everything. Joe Britt doesn't know it, but his flag is down and his meter's running and he's in high gear—on his way to the Twilight Zone.

Plot
Joe and Phyllis Britt are an old married couple in New York City who do not get along. Joe gets home from his job as a cab driver late one night, and Phyllis accuses him of seeing another woman. In the meantime, a television repairman is in the next room fixing their broken set. Irritated, Joe harasses the repairman about the inconvenience and cost. The repairman abruptly closes the open TV panel and announces the TV is fixed. After stating the job is free, he leaves, and the TV starts getting channel 10—a station showing the past, present, and future of Joe and Phyllis' lives. Joe refuses to let Phyllis watch the TV and faints when he sees himself and a mistress talking.

When he tunes in again later, it shows him killing Phyllis in a fight. Joe breaks down at the sight and tells Phyllis what is happening. Phyllis seeks help from the family doctor, who gives Joe a sedative and says that seeing oneself on television is one of several common delusions manifested by the struggle to adjust to the new technology of television.

Profoundly disturbed by the sight of Phyllis' death, Joe tries to heal their relationship, telling her that he accepts the blame for their feuding and has realized that his extramarital affairs were only an escape from the stress of his job, that Phyllis is still the one he really loves. Embittered by years of Joe's coldness and philandering, Phyllis scorns his attempt at reconciliation. When he begins reacting to another channel 10 vision – his trial for Phyllis's murder and execution via electric chair – even as Phyllis sees only static, Phyllis is convinced that Joe has lost his mind and taunts him. Joe, angered, attacks and kills her in the same manner as he had seen on the television screen.

As Joe is arrested by the police, the TV repairman suddenly appears and mockingly asks, "Fix your set okay, Mister? You will recommend my service, won't you?" The repairman smirks as Joe is taken away.

Closing narration
The next time your TV set is on the blink, when you're in the need of a first-rate repairman, may we suggest our own specialist? Factory-trained, prompt, honest, twenty-four hour service. You won't find him in the phone book, but his office is conveniently located—in the Twilight Zone.

Cast

 * Joan Blondell as Phyllis Britt
 * William Demarest as Joe Britt
 * Sterling Holloway as TV Repairman
 * Herbert Lytton as Dr. Saltman
 * Sandra Gould as Woman On T.V.
 * Howard Wright as Judge
 * Douglas Bank as Prosecutor
 * Ted Christy as The Wild Panther
 * Robert McCord as Electric Chair Guard
 * Tony Miller as Announcer
 * Mitchell Rhein as Neighbour
 * Rod Serling as Host / Narrator – Himself
 * Ron Stokes as Car Salesman
 * John L. Sullivan as The Russian Duke

title: What's in the Box


text:
Template:Lace types

{{documentation|content= {{collapsible option}}

title: Template:Lace types