17 ms·
Computer scientists invent an efficient new way to count
- unbalancedevh 2y agoI wonder how the error changes if you start a new round just before finishing the stream, compared to if the last word in the stream just fills the buffer and ends a round.
- lux 2y agoWhipped up a quick PHP version for fun: https://github.com/jbroadway/distinctelements https://github.com/jbroadway/distinctelements
- pixelmonkey 2y agoThis 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!
- hmottestad 2y agoIt’s also possible to use HLL to estimate the cardinality of joins since it’s possible to estimate both the union and the intersection of two HLLs. http://oertl.github.io/hyperloglog-sketch-estimation-paper/ http://oertl.github.io/hyperloglog-sketch-estimation-paper/
- j-pb 2y agoIt'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). 1: https://github.com/triblespace/tribles-rust/blob/master/src/query.rs https://github.com/triblespace/tribles-rust/blob/master/src/...
- refset 2y agoHaving 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. > 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 https://www.vldb.org/pvldb/vol16/p2962-zhang.pdf
- j-pb 2y agoThanks for the interesting paper! 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. 1: https://aidanhogan.com/docs/ring-graph-wco.pdf https://aidanhogan.com/docs/ring-graph-wco.pdf 2: https://github.com/triblespace/tribles-rust/blob/archive/src/triblearchive/succinctarchive/succinctarchiveconstraint.rs https://github.com/triblespace/tribles-rust/blob/archive/src...
- willvarfar 2y agoJust 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.
- michaelmior 2y agoI 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?
- _a_a_a_ 2y agoWas wondering the same, thanks for an answer.
- krackers 2y agoKnuth'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! [1] https://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf [2] https://florian.github.io/reservoir-sampling/ 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 https://news.ycombinator.com/item?id=40389178
- snewman 2y agoYou 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.
- finnh 2y agoWas 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.
- gwillen 2y agoMerging 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.
- imoverclocked 2y agoWhen do we stop calling this counting and start calling it estimation?
- pmontra 2y agoYes, even the subtile states "a simple algorithm for estimating large numbers of distinct objects".
- cubefox 2y agoThis doesn't excuse the title though.
- vlovich123 2y agoAs soon as people start reading past the headline.
- 112233 2y agotbh, 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?
- seanhunter 2y agoPresumably 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.
- a57721 2y agoI'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.
- matt3210 2y agoCS guys always wanting to throw away a good system and start from scratch.
- Miraltar 2y agoWhich good system are we talking about ?
- 112233 2y agoWhich good system are you referring to?
- baq 2y agoTell me you didn't read the article without telling me you didn't read the article. ...but actually, I think you didn't even read the headline...?
- coldtea 2y agoYeah, if only we have stuck with those stone wheels from 20,000 B.C.
- datavirtue 2y agoWell, they are easier to work on.
- biscuit1v9 2y ago> The trick, he said, is to rely on randomization. > 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..
- 8372049 2y agoDid you read the (entire) article?
- seanhunter 2y agoThe proof is pretty straightforward and is included in the paper https://arxiv.org/abs/2301.10191 https://arxiv.org/abs/2301.10191
- HDThoreaun 2y agoYes, the result is an estimation.
- biscuit1v9 2y agoThanks. Just wanted to be sure I didn't misunderstood.
- akamoonknight 2y agoI 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.
- wmwragg 2y agoI think it's generally thought of as "lateral thinking", Edward de Bono has written a few books about it you might find interesting.
- dentemple 2y agoTo 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.
- 112233 2y agoAfter 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?
- devnonymous 2y agoNot 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 ?
- 112233 2y agohttps://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf note how "u"s are selected every time value is not in a list. I don't read it as being a hash.
- hcs 2y agoI think the analysis relies on independent random "u"s, even for the same key.
- hcs 2y agohttps://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf Looks like it was posted at the time https://news.ycombinator.com/item?id=36079213 https://news.ycombinator.com/item?id=36079213 but not much discussed. I found it over here https://news.ycombinator.com/item?id=40387594 https://news.ycombinator.com/item?id=40387594
- saulrh 2y agoHuh, that's a clever twist on reservoir sampling. Neat.
- usgroup 2y agoI found the paper took about as long to read as the blog post and is more informative: https://arxiv.org/pdf/2301.10191 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.
- vanderZwan 2y agoIf 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.
- kibibu 2y agoI thought The Book was an Erdos thing. I wonder who used it first.
- stevesimmons 2y ago"During a lecture in 1985, Erdős said, `You don't have to believe in God, but you should believe in The Book.`" https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
- vanderZwan 2y agoI think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.
- usgroup 2y ago
- hum3hum3 2y agoThe counting/estimstion technique is rather like a floating point number. An integer exponent k and a mantissa of a population.
- melq 2y agoEstimating 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.
- dools 2y agoIt's an approximation, not an estimation.
- ranguna 2y agoStill very different things, no?
- blackkettle 2y agoActually, 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.
- dools 2y agoWikipedia is on your side: "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.
- aaron695 2y agoKnuth talks about this paper here - "The CVM Algorithm for Estimating Distinct Elements in Streams" - https://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
- thesz 2y agoHyperLogLog 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).
- kromem 2y agoAh, so Thanos was just conducting a census.
- rcarmo 2y agoI see what you did there.
- dist-epoch 2y agoDo they assume any particular distribution of the items? Otherwise Nassim Taleb would like a word with them.
- coldtea 2y agoNo, and Taleb is not relevant for this.
- dist-epoch 2y agoIt is if the distribution is extreme.
- coldtea 2y agoIf Hamlet was 100000000 times the word Hamlet and 1 time the word pancake, it would still give an good estimate measurement - even if pancake gets 0.
- drycabinet 2y agoDoes 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.
- jangxx 2y agoUsing 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.
- xwolfi 2y agoImagine a million elements. How big must your hashtable be ? The article explains it very well, did you miss it ? It's a way to save memory. 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...
- cb321 2y agoHow big was your thresh? I found it pretty accurate: https://news.ycombinator.com/item?id=40388878 https://news.ycombinator.com/item?id=40388878
- theginger 2y agoThat 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.
- Anduia 2y agoUsing 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.
- gh0stcloud 2y agovery 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.
- deleted 2y ago[deleted]
- rep_lodsb 2y ago>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?
- zvr 2y agoNo, 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.
- novaRom 2y agoI wish we had a theory connecting randomness with time/space complexity. Intuitively I think the key to many computational limitations is making use of randomness.
- ilya_m 2y agoYour intuition is correct. See https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity)
- ilya_m 2y ago"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.
- davidmurdoch 2y agoSounds like this qualifies as "recent" to me.
- ngrilly 2y agoIt 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.
- unnouinceput 2y ago"Computer scientists invent an efficient new way to approximate counting large unique entries" - fixed the title
- renonce 2y agoAt first find this paragraph confusing: > 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.
- gnfargbl 2y agoOn 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 Karp, Shenker & Papadimitriou https://www.cs.umd.edu/~samir/498/karp.pdf https://www.cs.umd.edu/~samir/498/karp.pdf
- vanderZwan 2y ago> the top-k items in a stream 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)
- gnfargbl 2y agoIt'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 https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf and might be clearer there.
- vanderZwan 2y agoThank you, that is much easier to follow indeed! Very elegant, I agree :)
- ceving 2y agoCan some native speaker tell me: is "count" the new "guess"?
- dekhn 2y agoIt's estimation, not counting.
- deleted 2y ago[deleted]
- Culonavirus 2y agoIn the post-GPT world? Yes. Wait, maybe actually no? Depends on context. https://www.reddit.com/r/ChatGPT/comments/16jvl4x/wait_actually_yes/ https://www.reddit.com/r/ChatGPT/comments/16jvl4x/wait_actua...
- Koshkin 2y agohttps://news.ycombinator.com/item?id=40394015 https://news.ycombinator.com/item?id=40394015
- arn3n 2y agoDoes anyone else notice that quanta consistently has good illustrations and diagrams for their articles? Good visualizations and graphics can do extraordinary things for the understandability of a topic -- people like 3Blue1Brown understand this, and I'm glad quanta puts effort into it.
- Gbotex 2y agonice read!
- cb321 2y agoThis Nim program might clarify some things for someone. import std/[random, math, sets, times]; type F = float template uniqCEcvm*(it; xfm; k=100, alpha=0.05): untyped = ## Return (unbiased estim. cardinality of `it`, 1-alpha CI ebound*(1 +- e)). var x1 = initHashSet[type(xfm)](k); var x = x1.addr var x2 = initHashSet[type(xfm)](k); var y = x2.addr var p = 1.0 # p always 2^-i means could ditch FP var n = 0 #..RNG & arith for bit shifts/masks. let t0 = epochTime() for e in it: inc n #; let e = xfm # to compute randState.next here x[].excl e # 'd be nice to reduce to 1 hash by if rand(1.0) < p: #..excl w/prob 1 - p but then cannot x[].incl e #..add new keys. p -> 0 anyway. while x[].len == k: # KnuthLoop not CVMIf guards against for e in x[]: #..unlikely case of freeing nothing. if rand(1.0) < 0.5: y[].incl e p *= 0.5 swap x, y; y[].clear # ↓ e.bound conservative by ~15X (int(x[].len.F/p), sqrt(12.0*ln(8.0*n.F/alpha)/k.F), (epochTime() - t0)*1e9/n.F) when isMainModule: # Takes nItem/trial dupMask space nTrial when defined danger: randomize() import std/[strutils, os, strformat] let n = if paramCount()>0: parseInt(paramStr(1)) else: 100000 let msk = (if paramCount()>1: parseInt(paramStr(2)) else: 0xFFFF).uint64 let k = if paramCount()>2: parseInt(paramStr(3)) else: 512 # 32KiB let m = if paramCount()>3: parseInt(paramStr(4)) else: 35 var ex = initHashSet[uint64]() var xs = newSeq[uint64](n) for j in 1..m: xs.setLen 0; ex.clear for i in 1..n: xs.add randState.next and msk for e in xs: ex.incl e let (apx, err, t) = uniqCEcvm(xs, uint64, k) let ap = apx.F; let an = ex.len.F echo ex.len," ",apx,&" eb: {err:.4f} |x-a|/x: {abs(ap-an)/an:.4f} {t:.1f}ns" First few lines of laptop output: 51160 49152 eb: 0.6235 |x-a|/x: 0.0392 10.5ns 51300 51840 eb: 0.6235 |x-a|/x: 0.0105 10.7ns 51250 55168 eb: 0.6235 |x-a|/x: 0.0764 10.9ns 51388 52352 eb: 0.6235 |x-a|/x: 0.0188 10.5ns Ditching the floating point RNG & arithmetic might be able to lower that time per element cost to more like 5 ns or maybe 2GiB/s for 8B ints. The toggle back & forth between old & new HashSet is just to re-use the same L1 CPU cache memory. Note also that the error bound in the CVM paper seems very conservative. My guess is that it could maybe be tightened by 15+X (at the scale of those example numbers), but that might also require some kind of special function evaluation. Anyone have any ideas on that? Also note that since this is just estimating unique identities, you can always just count unique 64-bit hashes of keys (or maybe even 32-bit hashes depending on your accuracy needs and cardinalities) if you care about the key space/key compares are slow.
- eterevsky 2y agoComputer scientists invent a memory-efficient way to estimate the size of a subset
- m3kw9 2y agoIt seems fast too as you can use less rounds of flips and get an estimate meaning you may not need to go thru the entire “book” to get an estimate of distinct words
- deleted 2y ago[deleted]
- seadan83 2y agoThe subset is very important, it is the subset of unique elements.
- Koshkin 2y agoIt's not a "subset," it's "the set of equivalence classes."
- seadan83 2y agoI think it's by definition that the unique elements of a set is a subset. Nonetheless, the clarification is a good point. To take a stab at a yet more correct statement, maybe something like the follows captures it: In the algorithm noted, we are extrapolating the size of the unique elements by looking at additional subsets, which themselves are an equivalence class.
- eterevsky 2y agoThis is implied by the word "set" in "subset". Otherwise it would've been a multiset.
- deleted 2y ago[deleted]
- vitus 2y agoFrom the paper [0]: > We state the following well-known concentration bound, Chernoff bound, for completeness. Which variant of the Chernoff bound is this? This is almost the (looser variant of the) multiplicative form, but it's not quite right (per the use of 1+delta instead of a single parameter beta). In particular, that bound is only guaranteed to hold for delta >= 0 (not beta = 1 + delta > 0 as asserted in the paper) [0] https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191 [1] https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error) https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_... edit: to be clear: I'm not sure at all whether this breaks the proof of correctness, although I'm having a bit of difficulty following the actual details (I think I'd need to work through the intermediate steps on paper).
- mudiadamz 2y agoPython implementation: def streaming_algorithm(A, epsilon, delta): # Initialize parameters p = 1 X = set() thresh = math.ceil((12 / epsilon ** 2) * math.log(8 * len(A) / delta)) # Process the stream for ai in A: if ai in X: X.remove(ai) if random.random() < p: X.add(ai) if len(X) == thresh: X = {x for x in X if random.random() >= 0.5} p /= 2 if len(X) == thresh: return '⊥' return len(X) / p # Example usage A = [1, 2, 3, 1, 2, 3] epsilon = 0.1 delta = 0.01 output = streaming_algorithm(A, epsilon, delta) print(output)
- planede 2y agoreturn '⊥' what's this?
- jbaber 2y agoIn some symbolic logic classes, that character "bottom" represents "false" ad flipped "top" means true. Don't know what they're getting at in the code, though.
- dentemple 2y agoOnce again proving the need for comments in code. Especially for comments that are more useful than "initialize parameters"
- hollerith 2y ago>In some symbolic logic classes, that character "bottom" represents "false" That's unfortunate, because in the study of computer programming languages, it means "undefined" (raise an error).
- tsss 2y agoNot always. It is also the uninhabited bottom type.
- klaussilveira 2y agoThis actually comes at a good time. I'm currently refactoring a system that counts visits using inserts into a table, with a tuple of date and IP. I was planning to replace it with a HLL approach, but this is really interesting.
- pytness 2y agoIs it me or is the description of the algo wrong? > 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; If i follow this description of "check if exists in list -> delete": if hash_set.contains(word) { if !keep_a_word(round) { hash_set.remove(word); continue; } } else { hash_set.insert(word.to_string()); } The algorithm runs for ~20 iterations: Total word count: 31955 | limit: 1000 End Round: 20, word count: 737 Unique word count: 7233 Estimated unique word count: 772800512 But if I save the word first and then delete the same word: hash_set.insert(word.to_string()); if !keep_a_word(round) { hash_set.remove(word); continue; } It gets the correct answer: Total word count: 31955 | 1000 End Round: 3, word count: 905 Unique word count: 7233 Estimated unique word count: 7240
- Alexanfa 2y agoWas just now solving it and came to see if others had the same issue. Yep, you are right. function generateRandomNumbers(c, n) { let randomNumbers = new Array(c); for (let i = 0; i < randomNumbers.length; i++) { let randomNumber = Math.floor(Math.random() * (n + 1)); randomNumbers[i] = randomNumber; } return randomNumbers; } function run(w, wS, m, r) { function round(r) { while(wS.size < m) { const next = w.next() if (next.done) return true; wS.add(next.value) prune(next.value, r) } return false } function prune(v,r) { for (let i = 0; i < r; i++) { const flip = new Boolean(Math.round(Math.random())) if (flip == false) { wS.delete(v) } } } function purge(wS) { const copy = new Set(wS) copy.forEach(ith=>{ const flip = new Boolean(Math.round(Math.random())) if (flip == false) { wS.delete(ith) } }) } const done = round(r); if (!done) { purge(wS) return run(w, wS, r+1,m) } console.log(`Round ${r} done. ${wS.size} Estimate: ${wS.size / (1/Math.pow(2,r))}`) } const memory = 1000 const words = generateRandomNumbers(3000000,15000) const w = words[Symbol.iterator]() // create an iterator const wS = new Set(); run(w,wS, memory,0);
- jtanderson 2y agoGiven the topic of the paper[0], the footnote is especially charming: > the authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by r⃝. The publicly verifiable record of the randomization is available at https://www.aeaweb.org/journals/policies/random-author-order/search https://www.aeaweb.org/journals/policies/random-author-order... [0]: https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191 edit: formatting
- theelous3 2y ago> Imagine that you’re sent to a pristine rainforest to carry out a wildlife census. alt-f4
- mring33621 2y agoFeels like reservoir sampling to me
- prerok 2y agoWhile the algorithm is interesting and I commend the authors for the algorithm, it should be noted that this is a guesstimate only. So, it's not really an efficient way to count distinct values but an efficient way to get an approximate count of distinct values.
- deadeye 2y agoAm I correct in thinking the accuracy of this method has more to do with the distribution in the sample than the algo itself. Meaning, given a 100% unique list of items, how far off would this estimate be?
- MarkusQ 2y agoIt doesn't appear to be heavily dependent on the distribution. It mostly depends on how large your buffer is compared to the number of unique items in the list. If the buffer is the same size or larger, it would be exact. If it's half the size needed to hold all the unique items, you drop O(1 bit) of precision; at one quarter, O(2 bits), etc.
- edflsafoiewq 2y agoI don't think so. I think the point of the removal in X <- X \ {a_i} With probability p, X <- X U {a_i} is that afterwards a_i is in X with probability p regardless of how many times it occurs in the stream.
- SoftTalker 2y agoNew interview question: Tell me how you would estimate the number of unique words in Hamlet using only 100 elements.
- preordained 2y agoI wish this was a joke...
- brianhorakh 2y agoWondering if this approach could I found myself be applied to CFD (computational flow dynamics) methods to reduce the total volume of data points while still getting approximately close to the correct final answer?
- xpe 2y agoI have questions for Quanta Magazine -- this is probably a shot in the dark, but if anyone can ask them a few questions, here would be three of mine: 1. Have independent researchers evaluated the effectiveness of Quanta Magazine at their mission? [1] 2. In the case of this article, did the editors consider including visualization? If not, why not? 3. Does Quanta have interactive designers and/or data scientists on staff? How many? Why not more? ## Background & Biases I'm trying to overcome my disappointment in Quanta by being curious about their mission, organization, and constraints. I am glad they exist, but sometimes your "closest allies" can be one's harshest critics. I'm greatly troubled by the level of scientific, mathematical, and rational understanding among the denizens of the world. But for some reason, the state of science writing bothers me more. It would seem that I hold out hope that science writers could do better. This may be unfair, I admit. Anyhow, rather than just bash Quanta for being, say, not as good at the best math blogs or YouTube channels (such as 3Blue1Brown), I really want to figure out (a) if I'm missing something; or (2) if they are actively trying to improve; and (3) what we can all learn from their experience. [1] From https://www.quantamagazine.org/about/ https://www.quantamagazine.org/about/ : "Quanta Magazine is an editorially independent online publication launched by the Simons Foundation in 2012 to enhance public understanding of science. Why Quanta? Albert Einstein called photons “quanta of light.” Our goal is to “illuminate science.”"
- xpe 2y agoThis is not a complaint. For people that downvoted, may I ask why? To be clear, I'm not asking people to _explain_ the downvotes; I am only asking the people that actually downvoted. Here are some guesses: - Are my questions too harsh or unfair? Off-topic? - Do you not like that I openly admit my priors? - You hold it against me that I don't think science journalism is very good? - Do you think Quanta is of high quality? - ... unique? Not worth challenging? - ... doing all it can? - As a point of comparison, have you looked at how many IX people and data scientists other news organizations have? - Am I expecting too much? I'm genuinely curious. Persuade me that I'm missing something. I'm open to it. For what it is worth, I've attended many events associated with the Simons Institute; I've never found an organization like it. But I don't hold any organization up as above criticism. I have a feeling that Simons could be doing much more with Quanta. To me, the downvotes without comments (above) are likely informative, but not for the reasons you might think. They suggests people want to express disapproval, but think a response is not warranted or would take too much time. But why? My hunch is that I've struck a nerve. When people are uncomfortable, they often downvote. Sacred cows. Confirmation bias. Both are strong, even when you know that these things are cognitive errors. All in all, the downvotes may well suggest that people have huge irrational responses and/or blind spots around this.
- fnord77 2y agoWith other count-distinct algorithms, you can do unions and intersections on the "sets". (theta sketches, even bloom filiters) Can you do this with CVM?
- kuldeepmeel 2y agoUnfortunately, not, and that's an interesting open problem as other count-distinct algorithms don't work for "structured sets", while this one does. https://dl.acm.org/doi/10.1145/3452021.3458333 https://dl.acm.org/doi/10.1145/3452021.3458333
- burjui 2y agoThe algorithm uses less memory, but more CPU time because of rather frequent deletions, so it's a tradeoff, not just generally better algorithm, as article may suggest.
- empath-nirvana 2y agothe list is small so the cost of deletions should be small.
- minkzilla 2y agoThere is a big practicality problem I see with this algorithm. The thresh defined in the paper relies on the length of the stream. It seems to me that in a scenario where you have a big enough data set to desire a solution that doesn't just store every unique value you don't know the length. I did not make it through all the proofs but I believe they use the fact that the defined threshold has the length in it to prove error bounds. If I were to use this in a scenario where I need to know error bounds i would probably ballpark the length of my stream to estimate error bounds and then use the algorithm with a ballpark threshold depending on my systems memory. Another practical thing is the "exception" if nothing is removed on line 6 in the original algorithm. This also seems needed for the proof but you would not want in production, though the chance of hitting it should be vanishingly small so maybe worth the gamble? Here is my faithful interpretation of the algorithm. And then a re-interpretation with some "practical" improvements that almost certainly make the provability of the correctness impossible. func CountUnique(scanner *bufio.Scanner, epsilon float64, delta float64, m int) int { X := make(map[string]bool) p := 1.0 thresh := int(math.Ceil((12 / (epsilon * epsilon)) \* math.Log(8*float64(m)/delta))) for scanner.Scan() { a := scanner.Text() delete(X, a) if rand.Float64() < p { X[a] = true } if len(X) == thresh { for key := range X { if rand.Float64() < 0.5 { delete(X, key) } } p /= 2 if len(X) == thresh { panic("Error") } } } return int(float64(len(X)) / p) } func CountUnique2(scanner *bufio.Scanner, thresh int) int { //threshold passed in, based on system memory / estimates X := make(map[string]bool) p := 1.0 for scanner.Scan() { a := scanner.Text() delete(X, a) if rand.Float64() < p { X[a] = true } if len(X) >= thresh { // >= instead of == and remove the panic below for key := range X { if rand.Float64() < 0.5 { delete(X, key) } } p /= 2 } } return int(float64(len(X)) / p) } I tested it with Shakespeare's work. The actual unique word count is 71,595. With the second algorithm it is interesting to play with the threshold. Here are some examples. threshold 1000 Mean Absolute Error: 2150.44 Root Mean Squared Error: 2758.33 Standard Deviation: 2732.61 threshold 2000 Mean Absolute Error: 1723.72 Root Mean Squared Error: 2212.74 Standard Deviation: 2199.39 threshold 10000 Mean Absolute Error: 442.76 Root Mean Squared Error: 556.74 Standard Deviation: 555.53 threshold 50000 Mean Absolute Error: 217.28 Root Mean Squared Error: 267.39 Standard Deviation: 262.84
- zero_k 2y agoI was involved with implementing the DNF volume counting version of this with the authors. You can see my blog post of it here: https://www.msoos.org/2023/09/pepin-our-probabilistic-approximate-volume-counter https://www.msoos.org/2023/09/pepin-our-probabilistic-approx... And the code here: https://github.com/meelgroup/pepin https://github.com/meelgroup/pepin Often, 30% of the time is spent in IO of reading the file, that's how incredibly fast this algorithm is. Crazy stuff. BTW, Knuth contributed to the algo, Knuths' notes: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf He actually took time off (a whole month) from TAOCP to do this. Also, he is exactly as crazy good as you'd imagine. Just mind-blowing.
- Hnrobert42 2y agoThat’s really interesting and thanks for sharing. I am very curious about the extraordinarily gifted. What made you think Knuth is crazy good? Was there a particularly moment? Was it how fast he groked ideas? Was it his ability to ELI5?
- zero_k 2y agoWhat made me realize is that I saw some snippets of emails he wrote to a colleague. It was... insane. You could see his mind race. He recognized patterns in minutes that would take me days, if not weeks, to recognize. Also, he actually writes and runs code, overnight if need be. It was as bit of a shock to me. He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.
- PartiallyTyped 2y agoI feel extremely jealous of you.
- khazhoux 2y agoYou are envious of him. Jealous is when you possess something you don’t want taken away by someone else
- deleted 2y ago[deleted]
- pierrebai 2y agoIDK, if my explanation is correct, but I do believe it is. I t goes as follow. Imagine that you have a container of potential limitless capacity. The container starts with smalls capacity, equal to the real limited capacity that the real algorithm uses. As you add elements, when the container is full, its capacity is doubled, but all elements are then placed in a random position. When you're done, you're told the occupancy of the subset of the large container corresponding to the initial size and how many times the container size was doubled. Multiplying that occupancy by the power of two of the number of doubling gives you an approximation of the real size. The small catch is that in the actual algorithm, due to the discarding, the final number of elements, the occupancy, is somewhat erroneous. EDIT Another way to say this: you got a container of limited capacity S. When full, you "virtually" double its size and then randomly move elements over the full "imaginary" size of the virtual container. So after the first filling, you end up with about 1/2 the elements. After the second filling 1/4, etc. Also, since now your "virtual" container is larger, when you add a new element, there is only 1/2^n the it will be place inside your limited-capacity view of the entire virtual container. At the end, the approximate real count is the number of elements you got multiplied by 2 to the power of the number of size doubling. Again, it is as if you have a small window into a limitless container.
- OutOfHere 2y agoThe title is misleading. This is about probabilistic counting, therefore about estimation. It is not clear if the efficiency benefit extends to exact counting. Counting and estimation are not the same concepts.
- u8 2y agoI took a crack at implementing this in Go. For anyone curious I settled for algorithm 2 as I can just use a map as the base set structure. https://github.com/tristanisham/f0 https://github.com/tristanisham/f0
- _xnmw 2y agoCan LLM’s invent a new simple algorithm like this which it has never seen before? I tried to induce ChatGPT to invent this algorithm, giving it hints along the way, but it came up with something else that I’m unsure is correct. Then again, most humans wouldn’t be able to do that either. But how intelligent is AI if it can’t invent anything truly novel and significant?
- leduyquang753 2y agoIn the algorithm depicted in the paper, if no elements manage to be eliminated from the set, why not just retry rather than return ⊥?
- renonce 2y agoRetrying would cause errors in the math. Personally I think a better modification would be to get into next round right away.
- oertl 2y agoThe algorithm is simple, which is why it is also suitable for textbooks. However, it is far from representing the state of the art. In case you are interested in the latest development, I have recently published a new distinct counting algorithm where the estimate does not depend on the processing order, which can be merged and requires only 3.5kB of memory to guarantee a standard error of 1.13% for counts up to exa-scale: https://arxiv.org/abs/2402.13726 https://arxiv.org/abs/2402.13726
- methyanddinky 2y agoThis is actually a really sad, redundant example of the regression of education in the United States. This "sure to be lauded" technique is pretty simple and has been exploited by simpleton gamblers for a very long time. Its basically simple math disguised as "mentalism". But since you, "very new to " "the real world" people figure out your folly. I promise I wont laugh. But I am laughing at how incredibly hollowed out the education system of the USA is when a simple compund method for an old trick, substitutes itself for math. The "math" involved is purely low IQ points on the inventors side.
- j_m_b 2y agoI jumped on the code generation bandwagon pretty soon after ChatGPT was released. I like to think of similar to a catalyst in a chemical reaction, it lowers the activation barrier to writing code, especially in new contexts (to you). It makes it easier to just get started. However, it struggles with solving actual problems or even putting together the right context. If you know how to break the problem down to simpler steps, it can help with those. It won't write a new kernel driver for you.
- helix278 2y agoWrong thread?
- volimKnjige 2y agoWhich books are in background?
- volimKnjige 2y agoWhich books are in the background, I can't read their titles because picture is blurred too much?? Help please !!! :)
- 6510 2y agoCould you pick 1000 randomly and repeat the process endlessly?
- kuldeepmeel 2y agoWe are very grateful for the interest, and I thought I would link to some relevant resources. Paper: https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191 Knuth's note: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf Talk Slides: https://www.cs.toronto.edu/~meel/Slides/meel-distinct.pdf https://www.cs.toronto.edu/~meel/Slides/meel-distinct.pdf Talk Video: https://www.youtube.com/watch?v=K_ugk7OW0bI https://www.youtube.com/watch?v=K_ugk7OW0bI The talk also discusses the general settings where our algorithm resolved the open problem of estimation of the union of high dimensional rectangles.
- Too 2y agoNow we can finally count how many unique UUIDs there really are! My memory was never enough for this task before.
- asah 2y agoparallelism is an important consideration on modern systems. While the memory clearing step parallelizes, the inner loop seems hard to parallelize? also, how do we combine two sketches? (another form of parallelism)