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

231–240 of 299 posts

Re: Computer scientists invent an efficient new way to count

#231

Post by throwaway14356 »

lokar wrote: post #229
sesteel wrote: post #216

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.

You want every distinct item to have the same chance at the end. So when items repeat you need to reduce (not increase) the odds of keeping any given occurrence.

does that mean you could also split the set in half multiple times then run it on each half of a half (etc) and combine it with its other half?

that would seem simpler to me.

edit: oh but then you would need to keep the results which defeats the purpose

Re: Computer scientists invent an efficient new way to count

#232

Post by snewman »

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

Re: Computer scientists invent an efficient new way to count

#233

Post by khazhoux »

PartiallyTyped wrote: post #200
zero_k wrote: post #196

Earlier quoted context omitted.

What made me realize is that I saw some snippets of emails he wrote to a colleague. It was... insane. You could see his mind race. He recognized patterns in minutes that would take me days, if not weeks, to recognize. Also, he actually writes and runs code, overnight if need be. It was as bit of a shock to me. He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.

I feel extremely jealous of you.

You are envious of him.

Jealous is when you possess something you don’t want taken away by someone else

Re: Computer scientists invent an efficient new way to count

#234

Post by _xnmw »

Can LLM’s invent a new simple algorithm like this which it has never seen before? I tried to induce ChatGPT to invent this algorithm, giving it hints along the way, but it came up with something else that I’m unsure is correct. Then again, most humans wouldn’t be able to do that either. But how intelligent is AI if it can’t invent anything truly novel and significant?

Re: Computer scientists invent an efficient new way to count

#235

Post by [deleted] »

hollerith wrote: post #118
jbaber wrote: post #106

Earlier quoted context omitted.

In some symbolic logic classes, that character "bottom" represents "false" ad flipped "top" means true. Don't know what they're getting at in the code, though.

>In some symbolic logic classes, that character "bottom" represents "false" That's unfortunate, because in the study of computer programming languages, it means "undefined" (raise an error).

[deleted]

Re: Computer scientists invent an efficient new way to count

#236

Post by kuldeepmeel »

klabb3 wrote: post #226
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.

It's been a while, and maybe my brain has smoothened since my time in CS, but man this looks more confusing than it needs to be. First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine. Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size…

[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

Re: Computer scientists invent an efficient new way to count

#237

Post by kuldeepmeel »

josephernest wrote: post #139
Alexanfa wrote: post #131

Earlier quoted context omitted.

Quanta: Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. To: Round 1. Keep going through Hamlet, but now flipping a coin for each word. If it’s tails, delete the word if it exists; heads, and add the word if it's not already on the list. Old edit: Round 1. Keep go…

> adding words but now flipping a coin immediately after adding it Edit: I thought your formulation was correct but not really: We flip the coin after adding, but we also flip the coin even if we didn't add the word (because it was already there). This is subtle! wrong: if k not in mem: mem += [k] if np.random.rand() > p: mem.remove(k) wrong: if k not in mem: mem += [k] else: if np.random.rand() > p: mem.remove(k) co…

The following is also not correct.

    if k not in mem:
        mem += [k]
    if k in mem:      # not the same than "else" here
        if np.random.rand() > p:
            mem.remove(k)
Your final solution is indeed correct, and I think more elegant than what we had in our paper [I am one of the authors].

Re: Computer scientists invent an efficient new way to count

#238

Post by hiAndrewQuinn »

khazhoux wrote: post #233
PartiallyTyped wrote: post #200

Earlier quoted context omitted.

I feel extremely jealous of you.

You are envious of him. Jealous is when you possess something you don’t want taken away by someone else

Well, that use of jealousy is only really common in certain romantic situations. Like if some super good looking dude hits on your girl and she responds in an ambiguously-flirty way, you might definitely be said to be jealous, even though she didn't run off with him.

In most other domains, though, like this one, jealousy and envy are synonyms. https://www.merriam-webster.com/dictionary/jealousy#did-you-...

Re: Computer scientists invent an efficient new way to count

#239

Post by kuldeepmeel »

josephernest wrote: post #124
pytness wrote: post #110

Is it me or is the description of the algo wrong? > Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; If i follow this description of "check if exists in list -> delete": if hash_set.contains(word) { if !keep_a_word(round) { hash_set.remove(word); continue; } } else { hash_set.insert(word.to_string());…

I got the same problem. When implementing the exact method as described in quanta magazine (without looking at the arxiv paper), I always had estimates like 461746372167462146216468796214962164. Then after reading the arxiv paper, I got the the correct estimate, with this code (very close to mudiadamz's comment solution): import numpy as np L = np.random.randint(0, 3900, 30557) print(f"{len(set(L))=}") thresh = 100 p…

Yes, there is an error in the Quanta article [at the same time, I must add that writing popular science articles is very hard, so it would be wrong to blame them]

Your fix is indeed correct; we may want to have either while loop instead of "if len(mem) == thresh" as there is very small (but non-zero) probability that length of mem is still thresh after executing: mem = [m for m in mem if np.random.rand() ["While" was Knuth's idea; and has added benefit of providing unbiased estimator.]

Re: Computer scientists invent an efficient new way to count

#240

Post by usgroup »

klabb3 wrote: post #226
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.

It's been a while, and maybe my brain has smoothened since my time in CS, but man this looks more confusing than it needs to be. First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine. Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size…

> First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.

I suspect due to the details of the proof. This condition looks likely to me for very small set cardinality making the algorithm inappropriate for all-weather. See page 3 of the paper where Algorithm 2 is introduced. They show that in the failure condition, the likelihood of the algorithm returning a value outside of the epsilon bounds is higher.

> Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not.

m sizes the threshold, if it is too small, the error bounds guaranteed by the algorithm will be larger than expected, and vice versa if m is too large.

> And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.

Papers typically do not spend words on basics and those are standard concepts.

> Perhaps there should be a method for estimating the confidence/error rate.

You can't resize the stream easily because p implicitly depends on m via the thresh cardinality condition and if you were to change m then your p updates would not correspond. As a result you may not be able to rely on the error bounds. Note though that stream doesn't mean infinite or very large: take it to mean one item at a time. The point of this algorithm is to bound space complexity to something small. Have a look at thresh and note that log2(1e50) is just 166: if you did have a very large stream of indeterminate length you could also just pick a very large m.

Post reply on HN