Paper: What’s the Difference? Efficient Set Reconciliation without Prior Context (2011)
00:04:22 Sodium : <3
00:04:54 Quinn Wilton: https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
00:04:55 Philipp Krüger: https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
00:09:42 Michael Mure: I have to say, reading that paper was really enjoyable. Even after understanding how it works, it still feels like cheating on the universe. Thanks for running that group :-)
00:10:03 Quinn Wilton: "cheating on the universe" 🤣
00:12:44 Michael Mure: well, you put elements in the IBF way way past the saturation point, yet somehow retrieve data from data, looks like they didn't hear about Shannon's information theory
00:16:07 Marc-Antoine Parent: I imagine you can maintain the strata of IBF in memory continuously at low-ish cost; so computation cost is distributed
00:16:35 Brooklyn Zelenka (@expede): 👏👏👏
00:17:18 Zeeshan Lakhani: Btw, fantastic summary of the paper.
00:17:30 Marc-Antoine Parent: Indeed!
00:18:38 Eleanor (they/them): I think Figure 5 shows how Shannon catches up to them
00:20:31 Sodium : re: cheating on the universe, i am always blown away by the sorts of shenanigans you can pull off with xor
00:21:19 Michael Mure: ^ not really, you can still cram a billion elements in a tiny IBF and still recover the diff set from the mashed up bits
00:21:24 Brooklyn Zelenka (@expede): @Sodium — XOR is magic ✨
00:21:34 Zeeshan Lakhani: Agree, XOR is magic
00:21:43 Steve Moyer: re: xor - <3 for CRCs (feed in some data - get a value ... feed in the same data - get zero)
00:39:36 Marc-Antoine Parent: http://vldb.org/pvldb/vol14/p458-gong.pdf
00:46:56 Quinn Wilton: Sorry, I thought you had finished :)
00:47:35 Brooklyn Zelenka (@expede): Core use case
00:58:15 Jagan: isn't this process known as Stochastic averaging?