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

121–130 of 299 posts

Re: Computer scientists invent an efficient new way to count

#121

Post by adgjlsfhk1 »

swores wrote: post #71
usgroup wrote: post #69

Earlier quoted context omitted.

From the abstract: "All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory."

That still only speaks to it being simple enough for students, not whether its too simple for any other use vs. useful enough that students who learn it will spend the rest of their lives using it. For example word processor software is commonly described as simple enough for children to use at school, that doesn't mean that word processor software is of no use to adults.

the reason it's too simple for most real world use is that hyper-log-log is the "good" version of this technique (but is harder to prove that it works)

Re: Computer scientists invent an efficient new way to count

#122

Post by Alexanfa »

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());…

Was just now solving it and came to see if others had the same issue. Yep, you are right.

    function generateRandomNumbers(c, n) {
      let randomNumbers = new Array(c);
      for (let i = 0; i {
                const flip = new Boolean(Math.round(Math.random()))
                if (flip == false) {
                    wS.delete(ith)
                }
            })
        }
        const done = round(r);
        if (!done) {
            purge(wS)
            return run(w, wS, r+1,m)
        }
        console.log(`Round ${r} done. ${wS.size} Estimate: ${wS.size / (1/Math.pow(2,r))}`)
    }
    const memory = 1000
    const words = generateRandomNumbers(3000000,15000)
    const w = words[Symbol.iterator]() // create an iterator
    const wS = new Set();
    run(w,wS, memory,0);

Re: Computer scientists invent an efficient new way to count

#123

Post by davidmurdoch »

ilya_m wrote: post #61

"In a recent paper" - really? The paper first appeared in ESA 2022. The revised version (with some errors fixed) is from May 2023. To be fair, compared to the rate of progress in this area between Flajolet & Martin (1985) and the previous SOTA (Blasiok, 2018), a couple of years of sitting on this news is not a lot.

Sounds like this qualifies as "recent" to me.

Re: Computer scientists invent an efficient new way to count

#124

Post by josephernest »

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 = 1
    mem =  set()  
    for k in L:
        if k in mem:
            mem.remove(k)
        if np.random.rand()
Or equivalently:

    import numpy as np
    L = np.random.randint(0, 3900, 30557)
    print(f"{len(set(L))=}")
    thresh = 100
    p = 1
    mem = []
    for k in L:
        if k not in mem:
            mem += [k]
        if np.random.rand() > p:
            mem.remove(k)
        if len(mem) == thresh:
            mem = [m for m in mem if np.random.rand()
Now I found the quanta magazine formulation problem. By reading:

> 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. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outcome of 100 coin tosses. That concludes Round 1.

we want to write:

    for k in L:
        if k not in mem:
            mem += [k]
        else:
            if np.random.rand() > p:
                mem.remove(k)
        if len(mem) == thresh:
            mem = [m for m in mem if np.random.rand()
whereas it should be (correct):

    for k in L:
        if k not in mem:
            mem += [k]
        if np.random.rand() > p:    # without the else
            mem.remove(k)
        if len(mem) == thresh:
            mem = [m for m in mem if np.random.rand()
Just this little "else" made it wrong!

Re: Computer scientists invent an efficient new way to count

#125

Post by foobarian »

ericmcer wrote: post #117
mudiadamz wrote: post #102

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

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

Re: Computer scientists invent an efficient new way to count

#126

Post by m3kw9 »

eterevsky wrote: post #83

Computer scientists invent a memory-efficient way to estimate the size of a subset

It seems fast too as you can use less rounds of flips and get an estimate meaning you may not need to go thru the entire “book” to get an estimate of distinct words

Re: Computer scientists invent an efficient new way to count

#127

Post by rcarmo »

mudiadamz wrote: post #102

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

Re: Computer scientists invent an efficient new way to count

#128

Post by imglorp »

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…

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation.

    X ← X \ {ai}

Re: Computer scientists invent an efficient new way to count

#129

Post by tgv »

ericmcer wrote: post #117
mudiadamz wrote: post #102

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

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.

The names are literally taken from the paper.

Re: Computer scientists invent an efficient new way to count

#130

Post by michaelmior »

willvarfar wrote: post #85
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…

Just curious, dusting off my distant school memories :) How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning? I once had a job at a hospital (back when 'whiz kids' were being hired by pretty much every business) where I used reservoir sampling to make small subsets of records that were stored on DAT tapes.

I guess there is a connection in the sense that with reservoir sampling, each sample observed has an equal chance of remaining when you're done. However, if you have duplicates in your samples, traditional algorithms for reservoir sampling do not do anything special with duplicates. So you can end up with duplicates in your output with some probability.

I guess maybe it's more interesting to look at the other way. How is the set of samples you're left with at the end of CVM related to the set of samples you get with reservoir sampling?

Post reply on HN