This algorithm seems to resemble HyperLogLog (and all its variants), which is also cited in the research paper. Using the same insight of the estimation value of tracking whether we've hit a "run" of heads or tails, but flipping the idea on its head (heh), it leads to the simpler algorithm described, which is about discarding memorized values on the basis of runs of heads/tails.
This also works especially well (that is, efficiently) in the streaming case, allowing you to keep something resembling a "counter" for the distinct elements, albeit with a error rate.
The benefit of HyperLogLog is that it behaves similarly to a hash set in some respects -- you can add items, count distinct them, and, importantly, merge two HLLs together (union), all the while keeping memory fixed to mere kilobytes even for billion-item sets. In distributed data stores, this is the trick behind Elasticsearch/OpenSearch cardinality agg, as well as behind Redis/Redict with its PFADD/PFMERGE/PFCOUNT.
I am not exactly sure how this CVM algorithm compares to HLL, but they got Knuth to review it, and they claim an undergrad can implement it easily, so it must be pretty good!
It's a really interesting open problem to get the cost of these down so that they can be used to heuristically select the variable order for worst case optimal joins during evaluation.
It's somewhere on the back of my todo list, and I have the hunch that it would enable instance optimal join algorithms.
I've dubbed these the Atreides Family of Joins:
- Jessicas Join: The cost of each variable is based on the smallest number of rows that might be proposed for that variable by each joined relation.
- Pauls join: The cost of each variable is based on the smallest number of distinct values that will actually be proposed for that variable from each joined relation.
- Letos join: The cost of each variable is based on the actual size of the intersection.
In a sense each of the variants can look further into the future.
I'm using the first and the second in a triplestore I build in Rust [1] and it's a lot faster than Oxigraph. But I suspect that the constant factors would make the third infeasable (yet).
Having read something vaguely related recently [0] I believe "Lookahead Information Passing" is the common term for this general idea. That paper discusses the use of bloom filters (not HLL) in the context of typical binary join trees.
We now formally define our _God-Emperor Join_ henceforth denoted join_ge...
Nice work with TXDB btw, it's funny how much impact Clojure, Datomic and Datascript had outside their own ecosystem!
Let me return the favour with an interesting paper [1] that should be especially relevant to the columnar data layout of TXDB. I'm currently building a succinct on-disk format with it [2], but you might be able to simply add some auxiliary structures to your arrow columns instead.
Oh nice, I recall skimming this team's precursor paper "Worst-Case Optimal Graph Joins in Almost No Space" (2021) - seems like they've done a lot more work since though, so definitely looking forward to reading it:
> The conference version presented the ring in terms of the Burrows–Wheeler transform. We present a new formulation of the ring in terms of stable sorting on column databases, which we hope will be more accessible to a broader audience not familiar with text indexing
My apologies! It's even more emberrasing given the fact that I looked up the website, knowing that I _always_ swap them after having written too many `tx-listen` in my career.
They expanded their work to wider relations and made the whole framework a lot more penetrable. I think they over-complicate things a bit with their forward-extension, so I'm keeping every column twice (still much better than all permutations), which in turn allows for ad-hoc cardinality estimation.
Also the 1 based indexing with inclusive ranges is really not doing them any favours. Most formula become much more streamlined and simpler with 0 based indexing and exclusive ranges. (see `base_range` and `restrict_range` in [0])
Just curious, dusting off my distant school memories :)
How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning?
I once had a job at a hospital (back when 'whiz kids' were being hired by pretty much every business) where I used reservoir sampling to make small subsets of records that were stored on DAT tapes.
I guess there is a connection in the sense that with reservoir sampling, each sample observed has an equal chance of remaining when you're done. However, if you have duplicates in your samples, traditional algorithms for reservoir sampling do not do anything special with duplicates. So you can end up with duplicates in your output with some probability.
I guess maybe it's more interesting to look at the other way. How is the set of samples you're left with at the end of CVM related to the set of samples you get with reservoir sampling?
Knuth's presentation of this [1] seems very very similar to the heap-version (top-k on a uniform deviate) of reservoir sampling as mentioned in [2]. The difference is in how duplicates are handled. I wouldn't be surprised if this algorithm was in fact already in use somewhere!
Edit: Another commenter [3] brought up the BJKST algorithm which seems to be similar procedure except using a suitably "uniform" hash function (pairwise independence) as the deviate instead of a random number.
You could merge these data structures as well. If the two instances to be merged are not at the same "round", take the one that's at an earlier round and advance it (by discarding half the entries at random) by the difference in rounds. Then just insert the values from one list to the other, ignoring duplicates; if the result is too large, discard half at random and increment the round number.
I implemented exactly this algorithm at my previous employer, except that alongside each value, we stored an estimate of the number of times that value appeared. This allowed us to generate an approximate list of the most common values and estimated count for each value.
Was there, reviewed the PR, can confirm. Hi Steve!
Since then we've also tuned it up in a couple ways, in particular adding "skip" logic similar to fast reservoir sampling to trade some accuracy for the ability to not even look at the next N {M,G,T}B if you've already seen many many many matches. For non-selective searches over PB of data it's a good tradeoff, despite introducing some search-order bias.
Merging like that doesn't work -- it will tend to overestimate the number of distinct elements.
This is fairly easy to see, if you consider a stream with some N distinct elements, with the same elements in both the first and second halves of the stream. Then, supposing that p is 0.5, the first instance will result in a set with about N/2 of the elements, and the second instance will also. But they won't be the same set; on average their overlap will be about N/4. So when you combine them, you will have about 3N/4 elements in the resulting set, but with p still 0.5, so you will estimate 3N/2 instead of N for the final answer.
I have a thought about how to fix this, but the error bounds end up very large, so I don't know that it's viable.
tbh, the title (and introduction) did a lot to dissuade me from finishing the (really good) article. It was actually informative, why dress it as a SEO blogspam?
Presumably so it is optimised for search engines and people find it.
Publishers generally have good data about where their audience comes from. They wouldn't do this if it wasn't the best way they know of to maximise readership.
I've been following Quanta for some time, I'm sure they don't care about SEO and number of visitors, they care about the quality of texts. They write for the general audience, and even though they try to preserve the scientific accuracy, sometimes their explanations may seem oversimplified and even a bit confusing when you come from the same field. It's not clickbait, it's their popular science style.
Seems this is one of those things like UUIDs where we rely on it being very unlikely to be wrong, because statistics.
> the accuracy of this technique scales with the size of the memory.
I wonder if that's proportional to the number of distinct items to count, though.
> if the [memory] is so big that it fits all the words, then we can get 100% accuracy
Yes, but then the algorithm isn't being used any more, that's just normal counting.
They counted the distinct words in Hamlet with a memory size of 100 words, about 2.5% of the number to find, and got a result that was off by 2. If you do the same with the whole of Shakespeare, again using 2.5% of the memory needed to hold all the distinct words, is the accuracy better?
Anyway, this is limited to counting, and doesn't help list what the words are, though quickly counting them first is perhaps a way to speed up the task of actually finding them?
When it is actually impossible to count something and when the error between estimation and an exact answer is not significant the pedantic distinction is not helpful.
The same thing happens with measurement. No measurement is ever exact. If I said I was measuring a count, someone would probably correct to say that I am counting.
I don't know a word or phrase for this, but I really enjoy any examples of "thinking outside the box" like this because it's something I struggle with in my professional career. Learning not only the right ways to solve problems, but figuring out the questions to ask that make solving the problems you have easier or even in some cases possible. In this case, it's hey, we don't need exact numbers if we can define a probabilistic range given defined parameters. Other problems are gonna have other questions. I guess my hope is that if I see enough examples I'll be able to eventually internalize the thought process and apply it correctly.
To be fair, this was a university research team. Literally, a team of folks who can, all day everyday, iterate over a single topic using the Scientific Method.
If you were paid by a big company to sit at a whiteboard all day with a team of equally intelligent engineers, I'm sure you'd be come up with SOMETHING that would look like an "outside the box" solution to the rest of the world.
However, most of us are paid to work the JIRA factory line instead, which limits the amount of time we can spend experimenting on just one single problem.
After skimming Knuth's paper — does the algorithm work if values are hashed, that is, the "uniform deviate" is selected deterministically for each unique value of the stream?
Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW how else does one define unique/distinct values ?
It is about estimating the cardinality of a set of elements derived from a stream. The algorithm is so simple, you can code it and play with it whilst you read the paper.
The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.
If you refer to the subtitle of the paper - An Algorithm for the (Text) Book - I think that is actually a reference to something *Paul Erdos allegedly said about some proofs are so elegant in their simplicity and beauty that they are "from The Book", like representing some divine Platonic ideal.
Given that Knuth himself reviewed it, he might have remarked that this was one of those algorithms! Perhaps the authors decided to include it in the title as a not-so-humble brag (which would be well-earned if that's the case!)
edit: originally this comment said Knuth was the one who said this about some algorithms being from The Book, but that was my faulty memory.
From the abstract: "... All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory ...."
This is really twisting it, I don't find pairwise indepedence to be more advanced than applying a Chernoff bound. In this problem it'd mostly be the difference of using a Cherbyshev type bound or Chernoff bound.
Pairwise independence is to give the algorithm stronger guarantees and let it work with a simple hash function like ax+b, otherwise probably most existing algorithms can be simplified in the same way. The most similar algorithm is BJKST, which is almost identical except for specifyimg the sampling mechanism to require less randomness.
To someone who worked on this type of thing before, it's like seeing people familar with LLMs say "oh yet another X-billion parameter model on github doing more or less the same".
The Chernoff bound needed in this work can be derived from Binomial distribution (with Stirling's approximation);
I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels like magic. The notion of pairwise independence is easy to explain but the notion of pairwise independent hash functions isn't.
The other strength of our work is that it can work for general settings of sets for which pairwise independent hash functions are not known. Please see: https://dl.acm.org/doi/10.1145/3452021.3458333
I liked this part. They got Knuth to review it, and found mistakes. That's kind of cool, in its own way.
We are deeply grateful to Donald E. Knuth for his thorough review,
which not only enhanced the quality of this paper (including fixing
several errors) but has also inspired us for higher standards.
From the abstract: "All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory."
> "The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks."
If you're saying it's just for "undergraduates and textbooks", as opposed to just being simple enough for them to use but not limited to them, would you mind explaining what makes it useful for undergrads but not for professionals?
My interpretation from the paper is that this algorithm is simpler than other options but also worse. So in a professional context you'd use one of those instead
From the abstract: "All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory."
That still only speaks to it being simple enough for students, not whether its too simple for any other use vs. useful enough that students who learn it will spend the rest of their lives using it.
For example word processor software is commonly described as simple enough for children to use at school, that doesn't mean that word processor software is of no use to adults.
the reason it's too simple for most real world use is that hyper-log-log is the "good" version of this technique (but is harder to prove that it works)
Simplicity in an algorithm has limited direct impact on its usefulness in industry where libraries are prevalent.
Consider mapping structures with Θ(k) expected lookup times. The simplest implementation is a hash table with chaining. Open-addressing is a bit more complicated, but also more common. Tries, which have O(k) worst-case lookup times are often covered in Undergraduate courses and are definitely easier to analyze and implement than forms of open-addressed hash-tables that have O(k) guarantees (e.g. Cuckoo hashing).
> Now you move forward with what the team calls Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outcome of 100 coin tosses. That concludes Round 1.
It's not just removals you test with N coin flips in Round N, it's whether to insert the new item at all.
I originally used Guttenburgh to get Hamlet and coded the Quanta method in Python and it did not work. I then moved to Algorithm 1 in the paper and got Copilot to (mis) convert it to Python and then spent time getting Copilot to admit its mistakes.
The resultant code seemed to work but I found the Quanta suggested data of the words of hamlet to be uninspiring as for the calculated theta (max set size before halving), was often from ~50% of the total number of words in hamlet to often more than the words in hamlet.
I've yet to investigate theta in more depth...
I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1]
You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct).
It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.
It's been a while, and maybe my brain has smoothened since my time in CS, but man this looks more confusing than it needs to be.
First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.
Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size of the stream the probability changes. But the algorithm is described as if it had a single output, which is not the case(?).
And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
I factored out the threshold parts into a helper instead, which makes a lot more sense than accidentally allocating too much memory.
Perhaps there should be a method for estimating the confidence/error rate. Nobody knows the size of a stream upfront, so it would make more sense to update these values as you go. Brain is not strong enough to implement it, but feel free to send a PR.
Didn’t realize you were here so let me be clear that I did overall find the paper so approachable that I could implement it with only a couple of outside pointers (also a little clever impl optimization around storing p if you’re curious). The above should be read more as “even this well-written simplified paper is not necessarily trivial to understand for practicians”. So more of a general point around academic obscurity.
> But yes, our theorems can be reworked to estimate the confidence/error rate
I think that’s useful for practical implications. Also, for practical use, how does one decide the tradeoff between delta and epsilon? Perhaps it’s covered elsewhere, but I have a hard time intuiting their relationship.
I fully agree with you and this is indeed one of my criticisms of modern academic writing -- we tend to write papers that are just very hard for anyone to read.
So delta refers to the confidence, i.e., how often are you willing to be wrong, and epsilon is tolerance with respect to the actual count.
We have found that in general, setting delta=0.1 and espilon=0.8 works fine for most practical applications.
> First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.
I suspect due to the details of the proof. This condition looks likely to me for very small set cardinality making the algorithm inappropriate for all-weather. See page 3 of the paper where Algorithm 2 is introduced. They show that in the failure condition, the likelihood of the algorithm returning a value outside of the epsilon bounds is higher.
> Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not.
m sizes the threshold, if it is too small, the error bounds guaranteed by the algorithm will be larger than expected, and vice versa if m is too large.
> And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
Papers typically do not spend words on basics and those are standard concepts.
> Perhaps there should be a method for estimating the confidence/error rate.
You can't resize the stream easily because p implicitly depends on m via the thresh cardinality condition and if you were to change m then your p updates would not correspond. As a result you may not be able to rely on the error bounds. Note though that stream doesn't mean infinite or very large: take it to mean one item at a time. The point of this algorithm is to bound space complexity to something small. Have a look at thresh and note that log2(1e50) is just 166: if you did have a very large stream of indeterminate length you could also just pick a very large m.
Estimating the amount of unique elements in a set and counting the amount of unique elements in a set are very different things. Cool method, bad headline.
Actually, my understanding is that it is an estimation because in the given context we don't know or cannot compute the true answer due to some kind of constraint (here memory or the size of |X|). An approximation is when we use a simplified or rounded version of an exact number that we actually know.
"In mathematics, approximation describes the process of finding estimates in the form of upper or lower bounds for a quantity that cannot readily be evaluated precisely"
This process doesn't use upper and lower bounds.
However, it still seems more like approximation than estimation to me because of this:
“Of course,” Variyam said, “if the [memory] is so big that it fits all the words, then we can get 100% accuracy.
It seems that in estimation the answer should be unknowable without additional information, whereas in this case it's just a matter of resolution or granularity because of the memory size.
Anyhoo ...
EDIT: also the paper says "estimate" and the article says both "approximate" and "estimate" at different times so it seems everyone except me thinks it's either an estimation or that estimation and approximation are interchangeable.
For someone who's pretty well-versed in English, but not a math-oriented computer scientist, this seems like a distinction without a difference. Please remedy my ignorance.
Eatimation is a procedure the generates an estimate, which is a kind of approximation, while approximation is a result value. They are different "types", as a computer scientist would say. An approximation is any value that is justifiably considered to be nearly exact. ("prox" means "near". See also "proximate" and "proxy".)
Estimation is one way to generate an approximation. An estimate is a subtype of an approximation. There are non-estimation ways to generate an approximation. For example, take an exact value and round it to the nearest multiple of 100. That generates an approximation, but does not use estimation.
I’m not sure the linguistic differences here are as cut and dried as you would like them to be. Estimate and approximate are both verbs, so you can derive nouns from them both for the process of doing the thing, and for the thing that results from such a process.
Estimation is the process of estimating. It produces an estimate.
Approximation is the process of approximating. It produces an approximation.
You can also derive adjectives from the verbs as well.
An estimate is an estimated value.
An approximation is an approximate value.
But you’re right that the ‘approximate’ terms make claims about the result - that it is in some way near to the correct value - while the
‘estimate’ derived terms all make a claim about the process that produced the result (ie that it was based on data that is known to be incomplete, uncertain, or approximate)
They’re not very different things; the terms are used interchangeably in most contexts because in the real world all counting methods have some nonzero error rate.
We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count.
That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound.
I kind of think the mythology of the ‘countless stones’ (https://en.wikipedia.org/wiki/Countless_stones) is a sort of folk-reminder that you can never be too certain that you counted something right. Even something as big and solid and static as a standing stone.
The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.
It’s not a fundamental difference, it’s a fundamental constraint.
There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway.
We still call procedures for counting things under those circumstances ‘counting’.
The constraints on this problem (insufficient memory to remember all the unique items you encounter) are one such situation where even computerized counting isn’t going to be exact.
Frankly, most of what you consider counting in your comment needs error bars - ask anyone who operated an all-cash cash-register how frequently end-of-day reconciliation didn't match the actual cash in the drawer (to the nearest dollar.)
The following is a list from my personal experience - of presumably precisely countable things that didn't turn out to be the case: the number of computers owned by an fairly large regional business, the number of (virtual) servers operated by a moderately sized team, the number of batteries sold in a financial year by a battery company.
Counting is a subset of estimation, not a synonym.
If I estimated the number of quarters in a stack by weighing them, that would be different from estimating the number of quaters in a stack by counting them. Both methods of estimation have error bars.
The list you provide is of categories that don't have clear definitions. If you have a sufficiently clear definition for a category given your population, it has a precise count (though your counting methodologies will still be estimates.) If your definition is too fuzzy, then you don't actually have a countable set.
The algorithm accuracy scales with the ratio of memory to set size so you don't actually know if it is "close enough" without an estimate of of the set size.
I think the headline is clickbaity and the article makes no effort to justify it's misuse of the wors 'counting'. The subheadline is far more accurate and doesn't use that many more words.
I think I get your point completely, yet I'm not getting through.
Would you agree that 1+1=2? Or that pi is 3.14159...? These are mathematical truths, but quickly crumble in the real world. One apple plus one apple doesn't just equate to double the apple, no two apples are ever the same to begin with, there are no real perfect circles out there either, there is still value to those mathematical truths in that they make it evident that they are perfectly precise and that it is real world interaction which may bring error into the table.
Counting and estimation are different by definition. One is a full enumeration, the latter an extrapolation from sampled data. In both cases 'accuracy' is a factor. Even if we are counting the number of stars, it is still a difference of technique compared to estimating the number if stars.
I could try to count fibers in muscle or grains of sand in the beach, chances are accuracy would be low. One can be smart about technique for more accurate counts, eg: get 10M sand counters and give them each 1kg of sand which they then count the grains with tweezer and microscope. That is counting. At the same time, we could find an average count of grains in 1kg sand from a random 100 of our counters, and then estimate what an expected total would be. The estimate can be used to confirm the accuracy of the counts.
They are not really as far apart a you think. At small numbers, yes get are distinct. At large enough numbers, they in all practicality the same thing. E.g what’s the population of the US
> the terms are used interchangeably in most contexts
Counting and estimating are not used interchangeably in most contexts.
> because in the real world all counting methods have some nonzero error rate.
The possibility that the counting process may be defective does not make it an estimation.
> We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count.
We talk about counting votes in elections because votes are counted. The fact that the process isn't perfect is a defect; this does not make it estimation.
> That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound.
No. Exit polling is estimation. Vote counting is counting. Vote recounting is also counting, and does not necessarily impose a tighter error bound, nor necessarily derive a different number.
> The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.
So like, computers? Regardless, this is wrong. Estimating something and counting it are not the same thing. Estimation has uncertainty, counting may have error.
This is like saying addition estimates a sum because you might get it wrong. It's just not true.
IEEE 754 defines an exact binary result for the addition of any two floats.
That this bit-identical result is not the same operation as addition of real numbers is irrelevant, because floats aren't reals.
f1 + f2 is not an estimation. Even treating it as an approximation will get you into trouble. It's not that either, it's a floating-point result, and algorithms making heavy use of floating point had better understand precisely what f1 + f2 is going to give you if they want to obtain maximum precision and accuracy.
True - for (relatively) small numbers. For large (huge) numbers estimation is usually considered to be equivalent to counting, and the result is sometimes represented using the "scientific" notation (i.e. "floating-point") rather than as an integer. For example, the mole is an integer whose value is only known approximately (and no one cares about the exact value anyway).
This doesn't justify estimation to be equivalent to counting even if some mathematicians consider them to be the same. Floating points are for estimation. Integers are for counting. The two are not the same, not even for large numbers.
HyperLogLog uses additions, it keeps sums. Thus, you can subtract one HLL sums from other. This is useful if stream supports deletion. Streams with deletions can be found in log-structured merge trees, for one example, so one can estimate count of distinct elements in all of the LSM tree hierarchy.
The algorithm in the paper does not allow for deletions.
Also, if one counts statistics of the stream of large elements (say, SHA-512 hashes, 64 bytes per hash), this algorithm requires some storage for elements from this stream, so memory requirement is O(table size * element size).
Does finding the number of unique elements in a set actually require comparison of each element with everything else? Can't you use a hashtable? For every element, add it to the table (ignore if already exists), and finally, take a count of keys.
Using a hashtable is the "normal" approach mentioned in the article. It works of course, but requires memory to store each unique element (or their hashes). If you have less memory available, the described algorithm can still give a very good approximation.
That is fine when you have say 1 million values and only 1000 are unique.
But when you have 1 million values and about 900 thousand are unique you are putting more or less the whole data set into memory.
Using a hashtable is effective because you only compare elements within their hash buckets, not the entire set. However, they can become inefficient with very large datasets due to memory usage and processing time, which is where approximate counts shine.
This algorithm is still spinning a lot of random. I would guess that this is much less overhead than hashing but still seems like it could be significant.
Imagine 1PB of data and you expect 30% of it to be unique. That needs 300TB RAM to store unique elements. Keep in mind the values in a hash table are the elements themselves, so a hastable of perhaps 300TB. Doing that without that much RAM, even swapping to disk can be tough.
very interesting solution. A perfect example of how even some very complicated problems can sometimes have simple solutions. Will definitely try to write an implementation of this.
The only minor downside to this is that it's obviously not deterministic since it depends on chance. But for many applications where the dataset is so big it doesn't fit in memory, that's probably just a tiny rounding error anyway.
>What if you’re Facebook, and you want to count the number of distinct users who log in each day, even if some of them log in from multiple devices and at multiple times?
Seems like a bad example of when this algorithm could be useful in practice.
If you already know you will want this info when designing the login process, it's simple: keep track of the date of last login for each account, and increment the unique user counter when the stored value is different from the current one.
And even if not, it should still be possible to "replay" a stream of login events from the database later to do this analysis. Unless maybe you already had years worth of data?
No, what you propose needs to "keep track of the date of last login for each account", so you need memory of the size of your user population. The idea is to perform it with much smaller, fixed amount of memory.
"In a recent paper" - really? The paper first appeared in ESA 2022. The revised version (with some errors fixed) is from May 2023. To be fair, compared to the rate of progress in this area between Flajolet & Martin (1985) and the previous SOTA (Blasiok, 2018), a couple of years of sitting on this news is not a lot.
It is quite amazing that after we had so many talented researchers working for decades on this problem, the authors were able to come up with such an elegant and simple solution. Another proof that research is very necessary and useful.
> Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list.
Why would you delete the word already on the list by flipping coins? Doesn't this reduce the accuracy by counting less words than expected? And will the word be added to the list later?
After thinking about it for a while and reading the paper, I've finally developed a good mental model for how this algorithm works as below, which should convince even a high schooler why the algorithm works:
1. You are given a streaming set of elements from [n] (a finite set of n distinct elements). Now let's give each element a random uniform real number in [0,1]. This helps us choose the elements we want: if we choose all elements with the number below 0.5, we get about half of the elements.
2. Assume for a moment we have unbounded memory. Now we maintain a table of already seen elements, and for each element we keep the last real number attached with that element: so if an element A appears three times with the number 0.3, 0.7, 0.6, we keep A with the number 0.6.
3. Our memory is bounded! So we keep only the elements below a threshold 2^-r, that is, 1, 0.5, 0.25, etc. So at first we will keep all elements, but when we don't have enough memory, we will need to filter existing elements according to the threshold. It's easy to see that when we decrease threshold, only elements already in memory will meet the criteria and continue to exist in memory. No other elements in the stream will be below threshold. Also note that whether an element is in memory depends only on its last occurence. It can exist in memory for a while, get dropped because a later element does not meet the threshold, and get back in.
4. We don't actually have a real number attached to every element! But we can pretend as if there is one. For each new element X from the stream, we replace the number in memory with its attached number, and we only care if its attached number is below 2^-r or not. If it is, it should be in our memory, and if it's not, it should be out. Once the number is in memory, it's a random number in [0,2^-r] and we care no further.
When increasing r, we only care about whether the number is in [0,2^{-r-1}]. This has exactly 1/2 probability. So each number has 1/2 probability of getting out, and 1/2 probability of being kept in memory.
5. Now it's easy to see that whether an element is in the memory depends solely on the real number attached to its last occurence. That is, each distinct element has exactly 2^-r probability of being in memory. 2^r multiplied by the number of elements in memory gives a good estimate of number of distinct elements.
They criticized previous approaches as relying on hash functions. A simplified version of the approach is as follows:
1. Make a hash function that maps distinct elements to different uniform real numbers. So all As compute to 0.3, all Bs compute to 0.7, etc.
2. Use that hash function to transform all elements. The same element maps to the same real number, and different elements map to different real numbers.
3. Keep a set of N smallest distinct real numbers. This works by inserting numbers from the stream to the set. It's easy to see that adding the same element multiple times has exactly no effect; it's either too big to be in the set or the same as an existing number in the set.
4. This gives the Nth smallest real number in the set as K. The number of distinct elements is approximated as N/K.
This algorithm is remarkable, but not in that it's efficient or it's new. Both algorithm using a hash function and algorithms without hash functions has been around and is optimal. I assume this algorithm is the first optimal algorithm without hash functions that is very easy to understand even by undergraduates.
I had the same problem with the same paragraph and still don’t quite get it.
Unfortunately I struggle to follow the detailed explanation you gave… since you seem to understand it… can you confirm that they really do mean to throw away the word in the list they just found?
Eg
ACT
I
SCENE
Elsinore
A
platform
before
the
castle
FRANCISCO
at
his
post.
Enter
to
him
If buffer max is 16, I am supposed to randomly half it first?
Act
Scene
Elisnore
Platform
Before
The
His
Post
Now what? The next words are “Bernado Bernado who’s there”
The key insight is that words should appear in your scratch space with equal probability, no matter how often they appear in the source text. If you have a scratch space of size one, then the sequence of "apple" x 16 + "banana" x 1 should have equal chances of of the scratch space containing [apple] or [banana] at the end of the sequence, at least averaged over all 17 permutations.
One way to achieve this result is to make the scratch space memory-free. Rather than think of it as "remove the word with probability x", think of it as "always remove the word, then re-add it with probability (1-x)".
- You have a buffer. You initially try to fit every unique word on there.
- If the buffer gets full, you know that you can't fit all the unique words in there. So you decide to keep only a fraction, _p1_, of them. Run through the buffer, keep each value with probability _p1_.
- Keep adding new words, again only with probability _p1_.
- If the buffer gets full again, _p1_ was too large, so you choose a lower fraction, _p2_, retain existing elements only with probability _p2_/_p1_, and continue adding new words with probability _p2_.
- Every time the buffer gets full, you lower the faction of words you try to retain.
The choice of using _pn_ = (1/2)^n is just easy for a computer, it only needs entire random bits at each step.
What I _don't_ get is how this is correct for counting unique words. If I have a text of 16384 unique words, then I can accept that each will be in the final list with the same probability. But if I take that list and repeat the last word 30000 times, then it becomes overwhelmingly plausible that that word is in the final list, even though I haven't changed the number of unique words.
Maybe there is some statistical property that evens things out, but I couldn't see it from the article.
And I got it. When the algorithm sees a word that is already in the list, it discards the word in the list first. Then it adds the word again with the same probability as any other word.
This ensures that only the last occurrence of each word can occur in the final list, so the final occurrence of each word are all in the final list with the same probability, and prior occurrences are always removed, if no earlier then when the next occurrence is seen.
If the input is known to be large, there is no reason to start by adding every element. It can treat the first round like any other, and start out with a _p0_ that is smaller than 1.
On the topic of counting things, I would like to mention this efficient and easily-implemented algorithm for finding the top-k items in a stream, which I think is perhaps not as well known as it should be:
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Hmm, this is phrased in a way that sounds different (to my ears) than the abstract, which says:
> it is often desirable to identify from a very long sequence of symbols (or tuples, or packets) coming from a large alphabet those symbols whose frequency is above a given threshold
Your description suggests a finding fixed nr of k items, with the guarantee that it will be the top ones. The abstract sounds like if determines an a priori unknown number of items that meet the criteria of having a particular value greater than k.
So "find the 100 oldest users" vs "find all users older than 30".
Am I misunderstanding you or the abstract? (English is not my first language)
It's been a while since I used this in anger, but my recollection is that it maintains a fixed-size set of items. The same algorithm is in section 3.2 of https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf and might be clearer there.
298 comments
[ 3.9 ms ] story [ 333 ms ] threadThis also works especially well (that is, efficiently) in the streaming case, allowing you to keep something resembling a "counter" for the distinct elements, albeit with a error rate.
The benefit of HyperLogLog is that it behaves similarly to a hash set in some respects -- you can add items, count distinct them, and, importantly, merge two HLLs together (union), all the while keeping memory fixed to mere kilobytes even for billion-item sets. In distributed data stores, this is the trick behind Elasticsearch/OpenSearch cardinality agg, as well as behind Redis/Redict with its PFADD/PFMERGE/PFCOUNT.
I am not exactly sure how this CVM algorithm compares to HLL, but they got Knuth to review it, and they claim an undergrad can implement it easily, so it must be pretty good!
http://oertl.github.io/hyperloglog-sketch-estimation-paper/
It's somewhere on the back of my todo list, and I have the hunch that it would enable instance optimal join algorithms.
I've dubbed these the Atreides Family of Joins:
In a sense each of the variants can look further into the future.I'm using the first and the second in a triplestore I build in Rust [1] and it's a lot faster than Oxigraph. But I suspect that the constant factors would make the third infeasable (yet).
1: https://github.com/triblespace/tribles-rust/blob/master/src/...
> Letos join
God-Emperor Join has a nice ring to it.
[0] "Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis" - https://www.vldb.org/pvldb/vol16/p2962-zhang.pdf
Let me return the favour with an interesting paper [1] that should be especially relevant to the columnar data layout of TXDB. I'm currently building a succinct on-disk format with it [2], but you might be able to simply add some auxiliary structures to your arrow columns instead.
1: https://aidanhogan.com/docs/ring-graph-wco.pdf
2: https://github.com/triblespace/tribles-rust/blob/archive/src...
It's X.T. (as in 'Cross-Time' / https://xtdb.com), but thank you! :)
> 1: https://aidanhogan.com/docs/ring-graph-wco.pdf
Oh nice, I recall skimming this team's precursor paper "Worst-Case Optimal Graph Joins in Almost No Space" (2021) - seems like they've done a lot more work since though, so definitely looking forward to reading it:
> The conference version presented the ring in terms of the Burrows–Wheeler transform. We present a new formulation of the ring in terms of stable sorting on column databases, which we hope will be more accessible to a broader audience not familiar with text indexing
They expanded their work to wider relations and made the whole framework a lot more penetrable. I think they over-complicate things a bit with their forward-extension, so I'm keeping every column twice (still much better than all permutations), which in turn allows for ad-hoc cardinality estimation.
Also the 1 based indexing with inclusive ranges is really not doing them any favours. Most formula become much more streamlined and simpler with 0 based indexing and exclusive ranges. (see `base_range` and `restrict_range` in [0])
0: https://github.com/triblespace/tribles-rust/blob/e3ad6f21cdc...
How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning?
I once had a job at a hospital (back when 'whiz kids' were being hired by pretty much every business) where I used reservoir sampling to make small subsets of records that were stored on DAT tapes.
I guess maybe it's more interesting to look at the other way. How is the set of samples you're left with at the end of CVM related to the set of samples you get with reservoir sampling?
[1] https://cs.stanford.edu/~knuth/papers/cvm-note.pdf [2] https://florian.github.io/reservoir-sampling/
Edit: Another commenter [3] brought up the BJKST algorithm which seems to be similar procedure except using a suitably "uniform" hash function (pairwise independence) as the deviate instead of a random number.
[3] https://news.ycombinator.com/item?id=40389178
I implemented exactly this algorithm at my previous employer, except that alongside each value, we stored an estimate of the number of times that value appeared. This allowed us to generate an approximate list of the most common values and estimated count for each value.
Since then we've also tuned it up in a couple ways, in particular adding "skip" logic similar to fast reservoir sampling to trade some accuracy for the ability to not even look at the next N {M,G,T}B if you've already seen many many many matches. For non-selective searches over PB of data it's a good tradeoff, despite introducing some search-order bias.
This is fairly easy to see, if you consider a stream with some N distinct elements, with the same elements in both the first and second halves of the stream. Then, supposing that p is 0.5, the first instance will result in a set with about N/2 of the elements, and the second instance will also. But they won't be the same set; on average their overlap will be about N/4. So when you combine them, you will have about 3N/4 elements in the resulting set, but with p still 0.5, so you will estimate 3N/2 instead of N for the final answer.
I have a thought about how to fix this, but the error bounds end up very large, so I don't know that it's viable.
Publishers generally have good data about where their audience comes from. They wouldn't do this if it wasn't the best way they know of to maximise readership.
> the accuracy of this technique scales with the size of the memory.
I wonder if that's proportional to the number of distinct items to count, though.
> if the [memory] is so big that it fits all the words, then we can get 100% accuracy
Yes, but then the algorithm isn't being used any more, that's just normal counting.
They counted the distinct words in Hamlet with a memory size of 100 words, about 2.5% of the number to find, and got a result that was off by 2. If you do the same with the whole of Shakespeare, again using 2.5% of the memory needed to hold all the distinct words, is the accuracy better?
Anyway, this is limited to counting, and doesn't help list what the words are, though quickly counting them first is perhaps a way to speed up the task of actually finding them?
The same thing happens with measurement. No measurement is ever exact. If I said I was measuring a count, someone would probably correct to say that I am counting.
Common speech is like that.
...but actually, I think you didn't even read the headline...?
> When the space is full, press pause and flip a coin for each word. Heads, and the word stays on the list; tails, and you delete it.
I wasn't expecting to go that far: randomization. How can you verify if the answer is good? Only approximation, maybe..
If you were paid by a big company to sit at a whiteboard all day with a team of equally intelligent engineers, I'm sure you'd be come up with SOMETHING that would look like an "outside the box" solution to the rest of the world.
However, most of us are paid to work the JIRA factory line instead, which limits the amount of time we can spend experimenting on just one single problem.
note how "u"s are selected every time value is not in a list. I don't read it as being a hash.
Looks like it was posted at the time https://news.ycombinator.com/item?id=36079213 but not much discussed. I found it over here https://news.ycombinator.com/item?id=40387594
https://arxiv.org/pdf/2301.10191
It is about estimating the cardinality of a set of elements derived from a stream. The algorithm is so simple, you can code it and play with it whilst you read the paper.
The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.
Given that Knuth himself reviewed it, he might have remarked that this was one of those algorithms! Perhaps the authors decided to include it in the title as a not-so-humble brag (which would be well-earned if that's the case!)
edit: originally this comment said Knuth was the one who said this about some algorithms being from The Book, but that was my faulty memory.
https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
Pairwise independence is to give the algorithm stronger guarantees and let it work with a simple hash function like ax+b, otherwise probably most existing algorithms can be simplified in the same way. The most similar algorithm is BJKST, which is almost identical except for specifyimg the sampling mechanism to require less randomness.
To someone who worked on this type of thing before, it's like seeing people familar with LLMs say "oh yet another X-billion parameter model on github doing more or less the same".
I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels like magic. The notion of pairwise independence is easy to explain but the notion of pairwise independent hash functions isn't.
The other strength of our work is that it can work for general settings of sets for which pairwise independent hash functions are not known. Please see: https://dl.acm.org/doi/10.1145/3452021.3458333
Doesn't seem like it. Seems like an algorithm (similar to other approximate cardinality estimation algorithms) with huge applicability.
Not that this is just useful for textbooks, a mere academic toy example, which would be something else entirely.
This is both accessible AND efficient.
If you're saying it's just for "undergraduates and textbooks", as opposed to just being simple enough for them to use but not limited to them, would you mind explaining what makes it useful for undergrads but not for professionals?
For example word processor software is commonly described as simple enough for children to use at school, that doesn't mean that word processor software is of no use to adults.
Consider mapping structures with Θ(k) expected lookup times. The simplest implementation is a hash table with chaining. Open-addressing is a bit more complicated, but also more common. Tries, which have O(k) worst-case lookup times are often covered in Undergraduate courses and are definitely easier to analyze and implement than forms of open-addressed hash-tables that have O(k) guarantees (e.g. Cuckoo hashing).
> Now you move forward with what the team calls Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outcome of 100 coin tosses. That concludes Round 1.
It's not just removals you test with N coin flips in Round N, it's whether to insert the new item at all.
I think the pseudocode in the paper is very hard to beat.
[1] https://news.ycombinator.com/item?id=40388878
One example source, but it is pretty common in general: http://www.mathwords.com/s/set_subtraction.htm
Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.
It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.
First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.
Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size of the stream the probability changes. But the algorithm is described as if it had a single output, which is not the case(?).
And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
Anyway, here's my take in Golang: https://github.com/betamos/distinct
I factored out the threshold parts into a helper instead, which makes a lot more sense than accidentally allocating too much memory.
Perhaps there should be a method for estimating the confidence/error rate. Nobody knows the size of a stream upfront, so it would make more sense to update these values as you go. Brain is not strong enough to implement it, but feel free to send a PR.
We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf
But yes, our theorems can be reworked to estimate the confidence/error rate; that's what Knuth did: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
> But yes, our theorems can be reworked to estimate the confidence/error rate
I think that’s useful for practical implications. Also, for practical use, how does one decide the tradeoff between delta and epsilon? Perhaps it’s covered elsewhere, but I have a hard time intuiting their relationship.
So delta refers to the confidence, i.e., how often are you willing to be wrong, and epsilon is tolerance with respect to the actual count.
We have found that in general, setting delta=0.1 and espilon=0.8 works fine for most practical applications.
I suspect due to the details of the proof. This condition looks likely to me for very small set cardinality making the algorithm inappropriate for all-weather. See page 3 of the paper where Algorithm 2 is introduced. They show that in the failure condition, the likelihood of the algorithm returning a value outside of the epsilon bounds is higher.
> Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not.
m sizes the threshold, if it is too small, the error bounds guaranteed by the algorithm will be larger than expected, and vice versa if m is too large.
> And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.
Papers typically do not spend words on basics and those are standard concepts.
> Perhaps there should be a method for estimating the confidence/error rate.
You can't resize the stream easily because p implicitly depends on m via the thresh cardinality condition and if you were to change m then your p updates would not correspond. As a result you may not be able to rely on the error bounds. Note though that stream doesn't mean infinite or very large: take it to mean one item at a time. The point of this algorithm is to bound space complexity to something small. Have a look at thresh and note that log2(1e50) is just 166: if you did have a very large stream of indeterminate length you could also just pick a very large m.
"In mathematics, approximation describes the process of finding estimates in the form of upper or lower bounds for a quantity that cannot readily be evaluated precisely"
This process doesn't use upper and lower bounds.
However, it still seems more like approximation than estimation to me because of this:
“Of course,” Variyam said, “if the [memory] is so big that it fits all the words, then we can get 100% accuracy.
It seems that in estimation the answer should be unknowable without additional information, whereas in this case it's just a matter of resolution or granularity because of the memory size.
Anyhoo ...
EDIT: also the paper says "estimate" and the article says both "approximate" and "estimate" at different times so it seems everyone except me thinks it's either an estimation or that estimation and approximation are interchangeable.
Eatimation is a procedure the generates an estimate, which is a kind of approximation, while approximation is a result value. They are different "types", as a computer scientist would say. An approximation is any value that is justifiably considered to be nearly exact. ("prox" means "near". See also "proximate" and "proxy".)
Estimation is one way to generate an approximation. An estimate is a subtype of an approximation. There are non-estimation ways to generate an approximation. For example, take an exact value and round it to the nearest multiple of 100. That generates an approximation, but does not use estimation.
Estimation is the process of estimating. It produces an estimate.
Approximation is the process of approximating. It produces an approximation.
You can also derive adjectives from the verbs as well.
An estimate is an estimated value.
An approximation is an approximate value.
But you’re right that the ‘approximate’ terms make claims about the result - that it is in some way near to the correct value - while the ‘estimate’ derived terms all make a claim about the process that produced the result (ie that it was based on data that is known to be incomplete, uncertain, or approximate)
We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count.
That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound.
I kind of think the mythology of the ‘countless stones’ (https://en.wikipedia.org/wiki/Countless_stones) is a sort of folk-reminder that you can never be too certain that you counted something right. Even something as big and solid and static as a standing stone.
The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.
There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway.
We still call procedures for counting things under those circumstances ‘counting’.
The constraints on this problem (insufficient memory to remember all the unique items you encounter) are one such situation where even computerized counting isn’t going to be exact.
You can make an algorithm that counts, you can make an algorithm that estimates, this is the second.
Frankly, most of what you consider counting in your comment needs error bars - ask anyone who operated an all-cash cash-register how frequently end-of-day reconciliation didn't match the actual cash in the drawer (to the nearest dollar.)
The following is a list from my personal experience - of presumably precisely countable things that didn't turn out to be the case: the number of computers owned by an fairly large regional business, the number of (virtual) servers operated by a moderately sized team, the number of batteries sold in a financial year by a battery company.
If I estimated the number of quarters in a stack by weighing them, that would be different from estimating the number of quaters in a stack by counting them. Both methods of estimation have error bars.
The list you provide is of categories that don't have clear definitions. If you have a sufficiently clear definition for a category given your population, it has a precise count (though your counting methodologies will still be estimates.) If your definition is too fuzzy, then you don't actually have a countable set.
I think the headline is clickbaity and the article makes no effort to justify it's misuse of the wors 'counting'. The subheadline is far more accurate and doesn't use that many more words.
Would you agree that 1+1=2? Or that pi is 3.14159...? These are mathematical truths, but quickly crumble in the real world. One apple plus one apple doesn't just equate to double the apple, no two apples are ever the same to begin with, there are no real perfect circles out there either, there is still value to those mathematical truths in that they make it evident that they are perfectly precise and that it is real world interaction which may bring error into the table.
I could try to count fibers in muscle or grains of sand in the beach, chances are accuracy would be low. One can be smart about technique for more accurate counts, eg: get 10M sand counters and give them each 1kg of sand which they then count the grains with tweezer and microscope. That is counting. At the same time, we could find an average count of grains in 1kg sand from a random 100 of our counters, and then estimate what an expected total would be. The estimate can be used to confirm the accuracy of the counts.
Counting and estimating are not used interchangeably in most contexts.
> because in the real world all counting methods have some nonzero error rate.
The possibility that the counting process may be defective does not make it an estimation.
> We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count.
We talk about counting votes in elections because votes are counted. The fact that the process isn't perfect is a defect; this does not make it estimation.
> That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound.
No. Exit polling is estimation. Vote counting is counting. Vote recounting is also counting, and does not necessarily impose a tighter error bound, nor necessarily derive a different number.
> The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.
So like, computers? Regardless, this is wrong. Estimating something and counting it are not the same thing. Estimation has uncertainty, counting may have error.
This is like saying addition estimates a sum because you might get it wrong. It's just not true.
That this bit-identical result is not the same operation as addition of real numbers is irrelevant, because floats aren't reals.
f1 + f2 is not an estimation. Even treating it as an approximation will get you into trouble. It's not that either, it's a floating-point result, and algorithms making heavy use of floating point had better understand precisely what f1 + f2 is going to give you if they want to obtain maximum precision and accuracy.
It's not a new problem, and it isn't specific to floats. Computers do discrete math. Always have, always will.
It depends on what the meaning of the word 'is' is.
https://libquotes.com/bill-clinton/quote/lby0h7o
The algorithm in the paper does not allow for deletions.
Also, if one counts statistics of the stream of large elements (say, SHA-512 hashes, 64 bytes per hash), this algorithm requires some storage for elements from this stream, so memory requirement is O(table size * element size).
Otherwise Nassim Taleb would like a word with them.
But to be honest I implemented it, ran it on Hamlet, and it's very wrong, it's barely useful but maybe if you just need a vague idea...
That's easy, that's all of them. Sorry, could not resist.
Yes, hashing is the usual method. In a sorted list you can compare to the following element.
The only minor downside to this is that it's obviously not deterministic since it depends on chance. But for many applications where the dataset is so big it doesn't fit in memory, that's probably just a tiny rounding error anyway.
Seems like a bad example of when this algorithm could be useful in practice.
If you already know you will want this info when designing the login process, it's simple: keep track of the date of last login for each account, and increment the unique user counter when the stored value is different from the current one.
And even if not, it should still be possible to "replay" a stream of login events from the database later to do this analysis. Unless maybe you already had years worth of data?
Intuitively I think the key to many computational limitations is making use of randomness.
> Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list.
Why would you delete the word already on the list by flipping coins? Doesn't this reduce the accuracy by counting less words than expected? And will the word be added to the list later?
After thinking about it for a while and reading the paper, I've finally developed a good mental model for how this algorithm works as below, which should convince even a high schooler why the algorithm works:
1. You are given a streaming set of elements from [n] (a finite set of n distinct elements). Now let's give each element a random uniform real number in [0,1]. This helps us choose the elements we want: if we choose all elements with the number below 0.5, we get about half of the elements.
2. Assume for a moment we have unbounded memory. Now we maintain a table of already seen elements, and for each element we keep the last real number attached with that element: so if an element A appears three times with the number 0.3, 0.7, 0.6, we keep A with the number 0.6.
3. Our memory is bounded! So we keep only the elements below a threshold 2^-r, that is, 1, 0.5, 0.25, etc. So at first we will keep all elements, but when we don't have enough memory, we will need to filter existing elements according to the threshold. It's easy to see that when we decrease threshold, only elements already in memory will meet the criteria and continue to exist in memory. No other elements in the stream will be below threshold. Also note that whether an element is in memory depends only on its last occurence. It can exist in memory for a while, get dropped because a later element does not meet the threshold, and get back in.
4. We don't actually have a real number attached to every element! But we can pretend as if there is one. For each new element X from the stream, we replace the number in memory with its attached number, and we only care if its attached number is below 2^-r or not. If it is, it should be in our memory, and if it's not, it should be out. Once the number is in memory, it's a random number in [0,2^-r] and we care no further.
When increasing r, we only care about whether the number is in [0,2^{-r-1}]. This has exactly 1/2 probability. So each number has 1/2 probability of getting out, and 1/2 probability of being kept in memory.
5. Now it's easy to see that whether an element is in the memory depends solely on the real number attached to its last occurence. That is, each distinct element has exactly 2^-r probability of being in memory. 2^r multiplied by the number of elements in memory gives a good estimate of number of distinct elements.
They criticized previous approaches as relying on hash functions. A simplified version of the approach is as follows:
1. Make a hash function that maps distinct elements to different uniform real numbers. So all As compute to 0.3, all Bs compute to 0.7, etc.
2. Use that hash function to transform all elements. The same element maps to the same real number, and different elements map to different real numbers.
3. Keep a set of N smallest distinct real numbers. This works by inserting numbers from the stream to the set. It's easy to see that adding the same element multiple times has exactly no effect; it's either too big to be in the set or the same as an existing number in the set.
4. This gives the Nth smallest real number in the set as K. The number of distinct elements is approximated as N/K.
This algorithm is remarkable, but not in that it's efficient or it's new. Both algorithm using a hash function and algorithms without hash functions has been around and is optimal. I assume this algorithm is the first optimal algorithm without hash functions that is very easy to understand even by undergraduates.
Unfortunately I struggle to follow the detailed explanation you gave… since you seem to understand it… can you confirm that they really do mean to throw away the word in the list they just found?
Eg
ACT I SCENE Elsinore A platform before the castle FRANCISCO at his post. Enter to him
If buffer max is 16, I am supposed to randomly half it first?
Act Scene Elisnore Platform Before The His Post
Now what? The next words are “Bernado Bernado who’s there”
The key insight is that words should appear in your scratch space with equal probability, no matter how often they appear in the source text. If you have a scratch space of size one, then the sequence of "apple" x 16 + "banana" x 1 should have equal chances of of the scratch space containing [apple] or [banana] at the end of the sequence, at least averaged over all 17 permutations.
One way to achieve this result is to make the scratch space memory-free. Rather than think of it as "remove the word with probability x", think of it as "always remove the word, then re-add it with probability (1-x)".
So if it is not in the list you just add it, right? Actually is that right? Won’t the list fill up to the max again at some point like this?
So if so, I add Bernardo. Now the very next word is Bernardo so I remove the last Bernardo and maybe re-add it based on a 50% chance.
- You have a buffer. You initially try to fit every unique word on there. - If the buffer gets full, you know that you can't fit all the unique words in there. So you decide to keep only a fraction, _p1_, of them. Run through the buffer, keep each value with probability _p1_. - Keep adding new words, again only with probability _p1_. - If the buffer gets full again, _p1_ was too large, so you choose a lower fraction, _p2_, retain existing elements only with probability _p2_/_p1_, and continue adding new words with probability _p2_. - Every time the buffer gets full, you lower the faction of words you try to retain.
The choice of using _pn_ = (1/2)^n is just easy for a computer, it only needs entire random bits at each step.
What I _don't_ get is how this is correct for counting unique words. If I have a text of 16384 unique words, then I can accept that each will be in the final list with the same probability. But if I take that list and repeat the last word 30000 times, then it becomes overwhelmingly plausible that that word is in the final list, even though I haven't changed the number of unique words. Maybe there is some statistical property that evens things out, but I couldn't see it from the article.
If the input is known to be large, there is no reason to start by adding every element. It can treat the first round like any other, and start out with a _p0_ that is smaller than 1.
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf
Hmm, this is phrased in a way that sounds different (to my ears) than the abstract, which says:
> it is often desirable to identify from a very long sequence of symbols (or tuples, or packets) coming from a large alphabet those symbols whose frequency is above a given threshold
Your description suggests a finding fixed nr of k items, with the guarantee that it will be the top ones. The abstract sounds like if determines an a priori unknown number of items that meet the criteria of having a particular value greater than k.
So "find the 100 oldest users" vs "find all users older than 30".
Am I misunderstanding you or the abstract? (English is not my first language)