Our video homepage now shows a fresh set of 24 recommendations on every refresh, thanks to a switch to weighted reservoir sampling (A-Res). The change eliminated the “same-grid-forever” problem that plagued our earlier score-sorted feed.
Why the old approach broke the experience
Every two hours we pull the latest trending videos from eight regions and dump the results into a SQLite table. The naïve solution was to sort the entire set—by a relevance score—and take the top 24. That method guarantees the highest-scoring items appear, but it also guarantees they stay there. A single viral clip can dominate position 1 for days, and users see an identical grid each time they reload.
Beyond the stale experience, sorting the whole table for every request forces SQLite to load a large temporary structure into memory, which is wasteful.
What weighted reservoir sampling gives us
Weighted reservoir sampling solves two problems at once:
- Freshness with bias – each video’s chance of being selected is proportional to its weight (e.g., relevance score). A video with double the weight is twice as likely to appear, but no item is guaranteed a spot.
- Memory efficiency – the algorithm keeps only a fixed-size “reservoir” of k items (k = 24 for our feed). It processes the stream in a single pass, so memory stays O(k) regardless of how many candidates arrive.
The core idea is simple. As we scan the incoming rows, we assign each item a random key that incorporates its weight, then retain the k items with the highest keys.
The algorithm in practice
For each video we:
- Draw a uniform random number u ∈ (0, 1).
- Compute a key k = u^(1/weight).
(The higher the weight, the larger the expected key.) - Insert the item into a min-heap that stores the current top k keys.
If the heap exceeds size k, we discard the smallest key.
When the stream ends, the heap contains the 24 videos we will display.
Dealing with floating-point limits
When a video’s weight is very large, u^(1/weight) collapses to a value indistinguishable from 1.0 in double-precision arithmetic, causing many heavy items to share the same key and lose randomness. The fix is to work in log space:
- Compute log_key = log(u) / weight instead of the power expression.
Because logarithms turn exponentiation into multiplication, the ordering of keys is preserved while avoiding the precision cliff. The calculation costs virtually nothing extra.
Implementation checklist
- Data structure: a min-heap (priority queue) of size k keeps the largest keys efficiently (O(log k) per insertion).
- Numeric type: use 64-bit floating-point numbers for u and the log-based keys; they provide ample precision for typical weight ranges.
- Statistical sanity check: run a quick Monte-Carlo test on a small sample set. If items with weight 10 appear roughly ten times as often as weight 1, the implementation is correct.
- Single-pass streaming: the algorithm does not need to know the total number of candidates ahead of time, which fits naturally with our SQLite cursor that yields rows one by one.
Takeaway
Weighted reservoir sampling lets a video recommendation service keep its homepage fresh, respect relevance scores, and stay memory-light—all with a single pass over tens of thousands of candidates. By moving the key calculation into log space and using a min-heap, the method stays both precise and performant.