New interview question: Tell me how you would estimate the number of unique words in Hamlet using only 100 elements.
Computer scientists invent an efficient new way to count
151–160 of 299 posts
Re: Computer scientists invent an efficient new way to count
#152This 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…
It’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/
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.
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/...
Re: Computer scientists invent an efficient new way to count
#153Earlier quoted context omitted.
I don't think there is a single variable name or comment in this entire code block that conveys any information. Name stuff well! Especially if you want random strangers to gaze upon your code in wonder.
Speaking of, one of my favorite discoveries with Unicode is that there is a ton of code points acceptable for symbol identifiers in various languages that I just can't wait to abuse. >>> ᚨ=3 >>> ᛒ=6 >>> ᚨ+ᛒ 9
You're even using a and b, very good.
Re: Computer scientists invent an efficient new way to count
#154I 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…
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.Re: Computer scientists invent an efficient new way to count
#155This 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…
It’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/
Iirc intersection requires the HLLs to have similar cardinality, otherwise the result is way off.
Re: Computer scientists invent an efficient new way to count
#156Earlier quoted context omitted.
Frankly, who can read this!? I am not sure what's worse, the multi-line comments spanning multiple lines of code, having multiple instructions on a single line, or the apparent disconnect between the pseudo-code of the article.
I would blame the majority of your criticism on the fact that HN is not the best place to read code. Also, syntax highlighting & basic familiarity with Nim helps. His code is doing a few more things than necessary. The actual algorithm is inside the `uniqCEcvm` template. The `it` it receives is anything you can iterate over (a collection or an iterator). Multiple things in one line really only appear where they direc…
Thank you very much for having taken the time.. Your comments and function are both very helpful!
Re: Computer scientists invent an efficient new way to count
#157Earlier quoted context omitted.
It’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/
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…
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.
> 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
Re: Computer scientists invent an efficient new way to count
#158Am 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?
It 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.
Re: Computer scientists invent an efficient new way to count
#159Earlier quoted context omitted.
I don't think there is a single variable name or comment in this entire code block that conveys any information. Name stuff well! Especially if you want random strangers to gaze upon your code in wonder.
Speaking of, one of my favorite discoveries with Unicode is that there is a ton of code points acceptable for symbol identifiers in various languages that I just can't wait to abuse. >>> ᚨ=3 >>> ᛒ=6 >>> ᚨ+ᛒ 9
Ah yes, programming like the vikings intended.
Re: Computer scientists invent an efficient new way to count
#160Python 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() = 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, ep…
That's not streaming if you're already aware of the length of the iterable.
In python, you can simply substitute `A` with an iterable or generator object, which can be a of unknown length.