3 ms·

How count-min sketches work – frequencies, but without the actual data

• esafak 1y ago
  Nice setup with the Wodehouse. There are lesser-used sketches beyond the basic Bloom, HyperLogLog, and count-min. Maybe for another article.
  • stopachka 1y ago
    Thank you! Are there are particular data structures that you think I should look into?
    • esafak 1y ago
      Cuckoo, XOR, ribbon, and counting Bloom filters.
      • stopachka 1y ago
        Thank you, I'll dive deeper.
  • pshirshov 1y ago
    Hyperminhash!
• iamwil 1y ago
  Cool! How did you do the reactive demos on the site? I assume it was with instantDB? How hard was it to integrate into a blog post?
  • stopachka 1y ago
    Thank you! Since all the reactive demos are local, I didn't add Instant in this case. One little trick I did for data was here: https://github.com/instantdb/instant/blob/main/client/www/components/essays/sketch/exactCounts.ts#L51 https://github.com/instantdb/instant/blob/main/client/www/co... Mainly: I wanted to get all counts for Wodehouse, but didn't want to block the page load for that. So what I did was take a small subset of the data that's needed to render the page, and have that written into the file. Then after load I fetch all the other counts. In the tutorial I also used Bun.xxHash3, but to make sketches run on the client, I had to replace that with a library. The actual sketch implementation that backs the demos is here: https://github.com/instantdb/instant/blob/main/client/www/components/essays/sketch/sketch.ts https://github.com/instantdb/instant/blob/main/client/www/co...