"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.
Computer scientists invent an efficient new way to count
61–70 of 299 posts
Re: Computer scientists invent an efficient new way to count
#62Estimating 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.
It's an approximation, not an estimation.
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.
Re: Computer scientists invent an efficient new way to count
#63I 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.
Your intuition is correct. See https://en.wikipedia.org/wiki/BPP_(complexity)
Re: Computer scientists invent an efficient new way to count
#64It 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.
Re: Computer scientists invent an efficient new way to count
#65I found the paper took about as long to read as the blog post and is more informative: 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.
> "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
Re: Computer scientists invent an efficient new way to count
#66Does 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.
> Does finding the number of unique elements in a set
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.
Re: Computer scientists invent an efficient new way to count
#67"Computer scientists invent an efficient new way to approximate counting large unique entries" - fixed the title
Re: Computer scientists invent an efficient new way to count
#68I found the paper took about as long to read as the blog post and is more informative: 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.
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 dec…
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 ...."
Re: Computer scientists invent an efficient new way to count
#69I found the paper took about as long to read as the blog post and is more informative: 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.
> "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?
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."
Re: Computer scientists invent an efficient new way to count
#70I found the paper took about as long to read as the blog post and is more informative: 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.
> The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks. Doesn't seem like it. Seems like an algorithm (similar to other approximate cardinality estimation algorithms) with huge applicability.
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."