241–250 of 299 posts
Earlier quoted context omitted.
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.
"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.
Earlier quoted context omitted.
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 fir…
Yes, you're supposed to throw it away. 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 permutatio…
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.
Earlier quoted context omitted.
Estimation is counting with error bars. 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…
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 pre…
I 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-approx... And the code here: 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…
Maybe you'd know, but why would one choose to not sort favoring larger counts and drop the bottom half when full? It may be obvious to others, but I'd be curious.
Earlier quoted context omitted.
Maybe you'd know, but why would one choose to not sort favoring larger counts and drop the bottom half when full? It may be obvious to others, but I'd be curious.
The guarantees would not hold, I'm pretty sure ;) Maybe one of the authors could chip in, but my hunch is that with that you could actually introduce arbitrarily large errors. The beauty of this algorithm really is its simplicity. Of course, simple is.. not always easy. This absolute masterpiece by Knuth should demonstrate this quite well: https://www.sciencedirect.com/science/article/pii/0022000078... It's an absolu…
In the algorithm depicted in the paper, if no elements manage to be eliminated from the set, why not just retry rather than return ⊥?
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 Karp, Shenker & Papadimitriou https://www.cs.umd.edu/~samir/498/karp.pdf
> 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 a…