Re:Computer Scientists Invent an Efficient New Way to Count
by usgroup on Friday May 17, 2024 @06:25AM
(#40388315)
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
by swores on Friday May 17, 2024 @06:28AM
(#40388338)
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.
Re:Computer Scientists Invent an Efficient New Way to Count
by adgjlsfhk1 on Friday May 17, 2024 @09:40AM
(#40389724)
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)
Re:Computer Scientists Invent an Efficient New Way to Count
by aidenn0 on Friday May 17, 2024 @05:53PM
(#40394522)
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).
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?