Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Computer scientists invent an efficient new way to count

quantamagazine.org

Post reply on HN
Print view View original

261–270 of 299 posts

Re: Computer scientists invent an efficient new way to count

#261

Post by mc32 »

throw10920 wrote: post #230
gspetr wrote: post #210

Earlier quoted context omitted.

Experience and age have diminishing returns. Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.

> Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays. Please don't post flamebaity political tangents on HN. > Eschew flamebait. Avoid generic tangents. https://news.ycombinator.com/newsguidelines.html

It’s a counterpoint anyone can identify with. One can interpret it uncharitably as flame bait if one wants to, but it need not be. It could have been Reagan in his second term, but some may not know who he was. Or Lee Smolin.

Re: Computer scientists invent an efficient new way to count

#262

Post by throw10920 »

mc32 wrote: post #261
throw10920 wrote: post #230

Earlier quoted context omitted.

> Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays. Please don't post flamebaity political tangents on HN. > Eschew flamebait. Avoid generic tangents. https://news.ycombinator.com/newsguidelines.html

It’s a counterpoint anyone can identify with. One can interpret it uncharitably as flame bait if one wants to, but it need not be. It could have been Reagan in his second term, but some may not know who he was. Or Lee Smolin.

This is objectively false. It is not a counterpoint, because it's not an argument. It's an extremely subjective claim that is highly contentious (like jedberg's sibling comment[1]), definitely not something that "anyone can identify with" (as the vast majority of people do not know Joe Biden and instead view him through one of a small number of extremely skewed lenses) and clearly in the realm of "off-topic flamebait" that is not appropriate on HN.

[1] https://news.ycombinator.com/item?id=40394477

Re: Computer scientists invent an efficient new way to count

#263

Post by xpe »

xpe wrote: post #173

I have questions for Quanta Magazine -- this is probably a shot in the dark, but if anyone can ask them a few questions, here would be three of mine: 1. Have independent researchers evaluated the effectiveness of Quanta Magazine at their mission? [1] 2. In the case of this article, did the editors consider including visualization? If not, why not? 3. Does Quanta have interactive designers and/or data scientists on st…

This is not a complaint. For people that downvoted, may I ask why? To be clear, I'm not asking people to _explain_ the downvotes; I am only asking the people that actually downvoted.

Here are some guesses:

- Are my questions too harsh or unfair? Off-topic?

- Do you not like that I openly admit my priors?

- You hold it against me that I don't think science journalism is very good?

- Do you think Quanta is of high quality?

- ... unique? Not worth challenging?

- ... doing all it can?

- As a point of comparison, have you looked at how many IX people and data scientists other news organizations have?

- Am I expecting too much?

I'm genuinely curious. Persuade me that I'm missing something. I'm open to it.

For what it is worth, I've attended many events associated with the Simons Institute; I've never found an organization like it. But I don't hold any organization up as above criticism. I have a feeling that Simons could be doing much more with Quanta.

To me, the downvotes without comments (above) are likely informative, but not for the reasons you might think. They suggests people want to express disapproval, but think a response is not warranted or would take too much time. But why?

My hunch is that I've struck a nerve. When people are uncomfortable, they often downvote. Sacred cows. Confirmation bias. Both are strong, even when you know that these things are cognitive errors. All in all, the downvotes may well suggest that people have huge irrational responses and/or blind spots around this.

Re: Computer scientists invent an efficient new way to count

#264

Post by Out_of_Characte »

PeterisP wrote: post #246
zero_k wrote: post #222

Earlier quoted context omitted.

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…

Worst case complexity matters when the input data can be manipulated by someone malicious, who can then intentionally engineer the degenerate worst case to happen - as we have seen historically in e.g. denial of service attacks exploiting common hash table implementations with bad worst case complexity.

No, you're throwing away a random selection of 50/50. You would have to flood the algorithm with uniques or commons to set the algoritm to a probability of a known state.

Re: Computer scientists invent an efficient new way to count

#265

Post by seadan83 »

Koshkin wrote: post #208
seadan83 wrote: post #207

Earlier quoted context omitted.

The subset is very important, it is the subset of unique elements.

It's not a "subset," it's "the set of equivalence classes."

I think it's by definition that the unique elements of a set is a subset. Nonetheless, the clarification is a good point.

To take a stab at a yet more correct statement, maybe something like the follows captures it: In the algorithm noted, we are extrapolating the size of the unique elements by looking at additional subsets, which themselves are an equivalence class.

Re: Computer scientists invent an efficient new way to count

#267

Post by finnh »

snewman wrote: post #232
pixelmonkey wrote: post #2

This 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…

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 t…

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.

Re: Computer scientists invent an efficient new way to count

#268

Post by willy_k »

jedberg wrote: post #217
gspetr wrote: post #210

Earlier quoted context omitted.

Experience and age have diminishing returns. Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.

Actually quick is definitely something that comes to mind. Quick in politics is of course relative, but the speed with which he has enacted major changes (for example marijuana legalization) is pretty quick in the realm of politics when congress is of the other party.

He’s barely able to read a teleprompter, not too confident that Biden himself enacted those changes.

Re: Computer scientists invent an efficient new way to count

#269

Post by kuldeepmeel »

cb321 wrote: post #91
usgroup wrote: post #22

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

I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1] [1] https://news.ycombinator.co…

You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct).

It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.

Re: Computer scientists invent an efficient new way to count

#270

Post by kuldeepmeel »

klabb3 wrote: post #255
kuldeepmeel wrote: post #236

Earlier quoted context omitted.

[I am one of the authors]. We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf But yes, our theorems can be reworked to estimate the confidence/error rate; that's what Knuth did: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf

Didn’t realize you were here so let me be clear that I did overall find the paper so approachable that I could implement it with only a couple of outside pointers (also a little clever impl optimization around storing p if you’re curious). The above should be read more as “even this well-written simplified paper is not necessarily trivial to understand for practicians”. So more of a general point around academic obsc…

I fully agree with you and this is indeed one of my criticisms of modern academic writing -- we tend to write papers that are just very hard for anyone to read.

So delta refers to the confidence, i.e., how often are you willing to be wrong, and epsilon is tolerance with respect to the actual count.

We have found that in general, setting delta=0.1 and espilon=0.8 works fine for most practical applications.

Post reply on HN