3 ms·

You 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 advanc

You 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 ago
Was 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 ago
Merging 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.

finnh 2y ago

Was 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 ago

Merging 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.