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

161–170 of 299 posts

Re: Computer scientists invent an efficient new way to count

#161

Post by j-pb »

refset wrote: post #157
j-pb wrote: post #152

Earlier quoted context omitted.

It's a really interesting open problem to get the cost of these down so that they can be used to heuristically select the variable order for worst case optimal joins during evaluation. It's somewhere on the back of my todo list, and I have the hunch that it would enable instance optimal join algorithms. I've dubbed these the Atreides Family of Joins: - Jessicas Join: The cost of each variable is based on the smallest…

Having read something vaguely related recently [0] I believe "Lookahead Information Passing" is the common term for this general idea. That paper discusses the use of bloom filters (not HLL) in the context of typical binary join trees. > Letos join God-Emperor Join has a nice ring to it. [0] "Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis" - https://www.vldb.org/pvldb/vol16/p…

Thanks for the interesting paper!

  We now formally define our _God-Emperor Join_ henceforth denoted join_ge...
Nice work with TXDB btw, it's funny how much impact Clojure, Datomic and Datascript had outside their own ecosystem!

Let me return the favour with an interesting paper [1] that should be especially relevant to the columnar data layout of TXDB. I'm currently building a succinct on-disk format with it [2], but you might be able to simply add some auxiliary structures to your arrow columns instead.

1: https://aidanhogan.com/docs/ring-graph-wco.pdf

2: https://github.com/triblespace/tribles-rust/blob/archive/src...

Re: Computer scientists invent an efficient new way to count

#162

Post by _a_a_a_ »

michaelmior wrote: post #130
willvarfar wrote: post #85

Earlier quoted context omitted.

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

Was wondering the same, thanks for an answer.

Re: Computer scientists invent an efficient new way to count

#163

Post by _a_a_a_ »

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…

I've known that symbol for decades, never knew it's name - up-tack it is. Ta!

Re: Computer scientists invent an efficient new way to count

#164

Post by Alexanfa »

Alexanfa wrote: post #122
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/Mat…

Noticed an error;

    return run(w, wS, r+1,m)
Should be changed to:

    return run(w, wS, m, r+1)

Re: Computer scientists invent an efficient new way to count

#165

Post by seaman1921 »

tgv wrote: post #129
ericmcer wrote: post #117

Earlier quoted context omitted.

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.

well the paper also contains the code so I doubt anyone who looked at the paper cares about this paste - for folks who did not read the paper this is not very readable

Re: Computer scientists invent an efficient new way to count

#166

Post by refset »

j-pb wrote: post #161
refset wrote: post #157

Earlier quoted context omitted.

Having read something vaguely related recently [0] I believe "Lookahead Information Passing" is the common term for this general idea. That paper discusses the use of bloom filters (not HLL) in the context of typical binary join trees. > Letos join God-Emperor Join has a nice ring to it. [0] "Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis" - https://www.vldb.org/pvldb/vol16/p…

Thanks for the interesting paper! We now formally define our _God-Emperor Join_ henceforth denoted join_ge... Nice work with TXDB btw, it's funny how much impact Clojure, Datomic and Datascript had outside their own ecosystem! Let me return the favour with an interesting paper [1] that should be especially relevant to the columnar data layout of TXDB. I'm currently building a succinct on-disk format with it [2], but…

> Nice work with TXDB btw

It's X.T. (as in 'Cross-Time' / https://xtdb.com), but thank you! :)

> 1: https://aidanhogan.com/docs/ring-graph-wco.pdf

Oh nice, I recall skimming this team's precursor paper "Worst-Case Optimal Graph Joins in Almost No Space" (2021) - seems like they've done a lot more work since though, so definitely looking forward to reading it:

> The conference version presented the ring in terms of the Burrows–Wheeler transform. We present a new formulation of the ring in terms of stable sorting on column databases, which we hope will be more accessible to a broader audience not familiar with text indexing

Re: Computer scientists invent an efficient new way to count

#167

Post by sangnoir »

Levitz wrote: post #146
jameshart wrote: post #99

Earlier quoted context omitted.

It’s not a fundamental difference, it’s a fundamental constraint. There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway. We still call procedures for counting things under those circumstances ‘counting’. The constraints on this problem (insufficient memory to reme…

I agree with you, but we are talking theory here. The algorithm doesn't count, it estimates. You can make an algorithm that counts, you can make an algorithm that estimates, this is the second.

Estimation is counting with error bars.

Frankly, most of what you consider counting in your comment needs error bars - ask anyone who operated an all-cash cash-register how frequently end-of-day reconciliation didn't match the actual cash in the drawer (to the nearest dollar.)

The following is a list from my personal experience - of presumably precisely countable things that didn't turn out to be the case: the number of computers owned by an fairly large regional business, the number of (virtual) servers operated by a moderately sized team, the number of batteries sold in a financial year by a battery company.

Re: Computer scientists invent an efficient new way to count

#168

Post by martinsnow »

mudiadamz wrote: post #113
martinsnow wrote: post #108

Earlier quoted context omitted.

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

You can just replace it with something like: print ('Invalid thresh or something')

This however looks scary so an innocent copy/paste programmer wouldn't touch it.

Re: Computer scientists invent an efficient new way to count

#169

Post by j-pb »

refset wrote: post #166
j-pb wrote: post #161

Earlier quoted context omitted.

Thanks for the interesting paper! We now formally define our _God-Emperor Join_ henceforth denoted join_ge... Nice work with TXDB btw, it's funny how much impact Clojure, Datomic and Datascript had outside their own ecosystem! Let me return the favour with an interesting paper [1] that should be especially relevant to the columnar data layout of TXDB. I'm currently building a succinct on-disk format with it [2], but…

> Nice work with TXDB btw It's X.T. (as in 'Cross-Time' / https://xtdb.com ), but thank you! :) > 1: https://aidanhogan.com/docs/ring-graph-wco.pdf Oh nice, I recall skimming this team's precursor paper "Worst-Case Optimal Graph Joins in Almost No Space" (2021) - seems like they've done a lot more work since though, so definitely looking forward to reading it: > The conference version presented the ring in terms of t…

My apologies! It's even more emberrasing given the fact that I looked up the website, knowing that I _always_ swap them after having written too many `tx-listen` in my career.

They expanded their work to wider relations and made the whole framework a lot more penetrable. I think they over-complicate things a bit with their forward-extension, so I'm keeping every column twice (still much better than all permutations), which in turn allows for ad-hoc cardinality estimation.

Also the 1 based indexing with inclusive ranges is really not doing them any favours. Most formula become much more streamlined and simpler with 0 based indexing and exclusive ranges. (see `base_range` and `restrict_range` in [0])

0: https://github.com/triblespace/tribles-rust/blob/e3ad6f21cdc...

Re: Computer scientists invent an efficient new way to count

#170

Post by mattkrause »

axitanull wrote: post #160
rcarmo wrote: post #127

Earlier quoted context omitted.

That's not streaming if you're already aware of the length of the iterable.

In python, you can simply substitute `A` with an iterable or generator object, which can be a of unknown length.

But for this algorithm, you need to know the total length ("m") to set the threshold for the register purges.

Does it still work if you update m as you go?

Post reply on HN