Florian writes about algorithms, probabilistic data structures and machine learning, including the XOR trick, count-min sketch and federated learning.
HN commenters link his XOR trick post for details and applications, and discuss it alongside other sketch data structures and reservoir sampling.
I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c.
What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before.
I hope they are as useful or intriguing to you as they are to me.
1. https://github.com/tdunning/t-digest
2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html
3. https://florian.github.io/count-min-sketch/
4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketching.pdf
5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf
6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-lec.pdf
7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf
8. https://www.sciencedirect.com/science/article/abs/pii/S002002551000397X
9. It may better be described as error-speed and…
No, the real problem is that people keep giving LLMs the ability to take nontrivial actions without explicit human verification - despite bulletproof input sanitization not having been invented yet!
Until we do so, every single form of input should be considered hostile. We've already seen LLMs run base64-encoded instructions[0], so even something as trivial as passing a list of commit shorthashes could be dangerous: someone could've encoded instructions in that, after all.
And all of that is before considering the possibility of a LLM going "rogue" and hallucinating needing to take actions it wasn't explicitly instructed to. I genuinely can't understand how people even for a second think it is a good idea to give a LLM access to production systems...
[0]: https://florian.github.io/base64/
Knuth's presentation of this [1] seems very very similar to the heap-version (top-k on a uniform deviate) of reservoir sampling as mentioned in [2]. The difference is in how duplicates are handled. I wouldn't be surprised if this algorithm was in fact already in use somewhere!
[1] https://cs.stanford.edu/~knuth/papers/cvm-note.pdf [2] https://florian.github.io/reservoir-sampling/
Edit: Another commenter [3] brought up the BJKST algorithm which seems to be similar procedure except using a suitably "uniform" hash function (pairwise independence) as the deviate instead of a random number.
[3] https://news.ycombinator.com/item?id=40389178
https://florian.github.io//xor-trick/ if you want detailed information and a list of possible applications.