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

101–110 of 299 posts

Re: Computer scientists invent an efficient new way to count

#101

Post by vitus »

From the paper [0]:

> We state the following well-known concentration bound, Chernoff bound, for completeness.

Which variant of the Chernoff bound is this? This is almost the (looser variant of the) multiplicative form, but it's not quite right (per the use of 1+delta instead of a single parameter beta). In particular, that bound is only guaranteed to hold for delta >= 0 (not beta = 1 + delta > 0 as asserted in the paper)

[0] https://arxiv.org/pdf/2301.10191

[1] https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_...

edit: to be clear: I'm not sure at all whether this breaks the proof of correctness, although I'm having a bit of difficulty following the actual details (I think I'd need to work through the intermediate steps on paper).

Re: Computer scientists invent an efficient new way to count

#102

Post by mudiadamz »

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, epsilon, delta)
  print(output)

Re: Computer scientists invent an efficient new way to count

#103

Post by Majromax »

majikandy wrote: post #79
renonce wrote: post #73

At first find this paragraph confusing: > 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. Why would you delete the word already on the list by flipping coins? Doesn't this reduce the accuracy by counting less words than expected? And will the word be added to the list lat…

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

One way to achieve this result is to make the scratch space memory-free. Rather than think of it as "remove the word with probability x", think of it as "always remove the word, then re-add it with probability (1-x)".

Re: Computer scientists invent an efficient new way to count

#104

Post by menthe »

cb321 wrote: post #80

This Nim program might clarify some things for someone. import std/[random, math, sets, times]; type F = float template uniqCEcvm*(it; xfm; k=100, alpha=0.05): untyped = ## Return (unbiased estim. cardinality of `it`, 1-alpha CI ebound*(1 +- e)). var x1 = initHashSet[type(xfm)](k); var x = x1.addr var x2 = initHashSet[type(xfm)](k); var y = x2.addr var p = 1.0 # p always 2^-i means could ditch FP var n = 0 #..RNG & a…

Frankly, who can read this!? I am not sure what's worse, the multi-line comments spanning multiple lines of code, having multiple instructions on a single line, or the apparent disconnect between the pseudo-code of the article.

Re: Computer scientists invent an efficient new way to count

#105

Post by planede »

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…

  return '⊥'
what's this?

Re: Computer scientists invent an efficient new way to count

#106

Post by jbaber »

planede wrote: post #105
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…

return '⊥' what's this?

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.

Re: Computer scientists invent an efficient new way to count

#107

Post by vanderZwan »

gnfargbl wrote: post #74

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 abstract sounds like if determines an a priori unknown number of items that meet the criteria of having a particular value greater than k.

So "find the 100 oldest users" vs "find all users older than 30".

Am I misunderstanding you or the abstract? (English is not my first language)

Re: Computer scientists invent an efficient new way to count

#108

Post by martinsnow »

planede wrote: post #105
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…

return '⊥' what's this?

An easy way to identify who copies code without understanding it.

Re: Computer scientists invent an efficient new way to count

#110

Post by pytness »

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());
    }
The algorithm runs for ~20 iterations:

    Total word count: 31955 | limit: 1000
    End Round: 20, word count: 737
    Unique word count: 7233
    Estimated unique word count: 772800512
But if I save the word first and then delete the same word:

    hash_set.insert(word.to_string());

    if !keep_a_word(round) {
        hash_set.remove(word);
        continue;
    }
It gets the correct answer:

    Total word count: 31955 | 1000
    End Round: 3, word count: 905
    Unique word count: 7233
    Estimated unique word count: 7240
Post reply on HN