Hacker News Reader

Comment by onos | Hacker News Reader

Great sleuthing. Is there a convenient alternative algorithm that might be used for random article that would also continue to work fine as more articles are added or removed?

View on HN

You can make a binary tree where each node counts the total (recursive) number of children. Updating these counts is log(N).

To insert a node, generate a random bit string: descend the tree and when the counts are equal then take the branch corresponding to that position in the bit string. When the counts are unequal, take the branch with the smallest count.

To remove a node just remove it from the tree and update the counts up along its path to the root. This assumes that articles are added as often as they are removed.

To sample, just generate another random bit string and traverse the tree according to it.

But I agree with the sibling comment that the current non-uniform algorithm is fine for a cute “Random article” button.

If the articles have some reasonably dense small IDs associated with them, then an easy algorithm is to simply pick a random ID between 0 and the max, check if it's a still-existing article, and repeat if not. There are plenty of distributed queue designs capable of distributing IDs to servers so they can be given to new articles, and re-using the id from a deleted article is fine to keep things denser.

The database itself may internally store a more dense identifier than an autoincrementing primary key. For e.g. ctid in Postgres or, under certain conditions rowid in sqlite. These should be fully dense after a vacuum, and rejection sampling can be used to paper over tombstones generated between vacuums.

Seems like it would be pretty easy to just maintain an alternative index of articles, with an integer ID counting from 1 to N. Then just pick a random number from 1 to N.

It could even be maintained entirely outside the Wikimedia servers, relying on database dumps.

I disagree that anything is wrong with the current algorithm.

However there was a brief time period where randomPage used elasticsearch to get the random article instead.

To get a more equal spacing between the articles maybe one can make use of quasirandom numbers instead of random numbers: https://en.wikipedia.org/wiki/Low-discrepancy_sequence

For the smallest change with the fairest result, I would reseed the random IDs on a schedule.

Added is easy. It’s removed that is the tricky part, though perhaps you could reuse IDs somehow.

Maybe a hashing function could work.

Reply on news.ycombinator.com