Simon Willison’s Weblog

Reservoir Sampling (via) Yet another outstanding interactive essay by Sam Rose (previously), this time explaining how reservoir sampling can be used to select a "fair" random sample when you don't know how many options there are and don't want to accumulate them before making a selection.

Reservoir sampling is one of my favourite algorithms, and I've been wanting to write about it for years now. It allows you to solve a problem that at first seems impossible, in a way that is both elegant and efficient.

I appreciate that Sam starts the article with "No math notation, I promise." Lots of delightful widgets to interact with here, all of which help build an intuitive understanding of the underlying algorithm.

Sam shows how this algorithm can be applied to the real-world problem of sampling log files when incoming logs threaten to overwhelm a log aggregator.

The dog illustration is commissioned art and the MIT-licensed code is available on GitHub.

# 8th May 2025, 9 pm / explorables, sam-rose, algorithms, rate-limiting, logging

Understanding the BM25 full text search algorithm (via) Evan Schwartz provides a deep dive explanation of how the classic BM25 search relevance scoring function works, including a very useful breakdown of the mathematics it uses.

# 19th November 2024, 11:09 pm / search, algorithms

Load Balancing. Sam Rose built this interactive essay explaining how different load balancing strategies work. It's part of a series that includes memory allocation, bloom filters and more.

# 13th July 2024, 10:51 pm / explorables, algorithms, load-balancing, sam-rose

SQLite Internals: Pages & B-trees (via) Ben Johnson provides a delightfully clear introduction to SQLite internals, describing the binary format used to store rows on disk and how SQLite uses 4KB pages for both row storage and for the b-trees used to look up records.

# 27th July 2022, 2:57 pm / sqlite, algorithms, databases, ben-johnson

Sha256 Algorithm Explained (via) Absolutely beautiful interactive animated explanation by Domingo Martin of the SHA256 hashing algorithm.

# 7th February 2022, 7:27 pm / explorables, algorithms

The humble hash aggregate (via) Today I learned that “hash aggregate” is the name for the algorithm where you split a list of tuples on a common key, run an aggregation against each resulting group and combine the results back together again—I’d previously thought if this in terms of map/reduce but hash aggregate is a much older term used widely by SQL engines—I’ve seen it come up in PostgreSQL explain query output (for GROUP BY) before but didn’t know what it meant.

# 6th June 2021, 4:03 pm / mapreduce, sql, algorithms

I was wrong. CRDTs are the future (via) Joseph Gentle has been working on collaborative editors since being a developer on Google Wave back in 2010, later building ShareJS. He’s used Operational Transforms throughout, due to their performance and memory benefits over CRDTs (Conflict-free replicated data types)—but the latest work in that space from Martin Kleppmann and other researchers has seen him finally switch allegiance to these newer algorithms. As a long-time fan of collaborative editing (ever since the Hydra/SubEthaEdit days) I thoroughly enjoyed this as an update on how things have evolved over the past decade.

# 28th September 2020, 9:03 pm / collaboration, algorithms, crdt

Creating Shazam in Java. Using a Fast Fourier Transformation.

# 22nd September 2010, 9:39 pm / algorithms, java, shazam, recovered

OpenStreetMap: QuadTiles. Fascinating explanation of a proposal for replacing lat, lon pairs in the OpenStreetMap database with a QuadTile-based addressing system.

# 10th September 2009, 3:54 pm / quadtiles, openstreetmap, algorithms, gis

How to Build a Popularity Algorithm You can be Proud of. Filed for future reference.

# 6th September 2009, 9:25 pm / popularity, algorithms

Visualising Sorting Algorithms. Aldo Cortesi dislikes animations of sorting algorithms, so he designed a beautiful technique for statically visualising them instead (using Python and Cairo to generate the images).

# 14th April 2009, 8:55 am / aldo-cortesi, python, cairo, sorting, algorithms, visualisation

Neil Fraser: Differential Synchronization. Paper describing a robust method for “keeping two or more copies of the same document synchronized with each other in real-time”, over a variable network connection using clever diff algorithms.

# 24th January 2009, 11:57 pm / paper, algorithms, diff, neil-fraser

Animated Sorting Algorithms (via) JavaScript animations of various sorting algorithms, running against four different initial conditions (random, nearly ordered, reversed and few unique). I wish I’d had this during my computer science degree.

# 21st October 2008, 12:17 am / sorting, algorithms, computer-science, animation

Core Techniques and Algorithms in Game Programming. Scarily detailed online book on games programming, including 2D and 3D graphics, AI, multiplayer network code, indoor and outdoor rendering, character animation and much more. UPDATE: Removed the original link, which appeared to be a pirated copy.

# 1st May 2008, 12:26 am / games, programming, algorithms

Google Maps API gets clickable polylines and polygons. Interesting explanation of how they optimised calculating the distance to the nearest point on a polyline.

# 8th September 2007, 12:58 pm / polygons, polylines, algorithms, google, googelmaps, javascript