4 ms·

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 a

by onos 4y ago

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?

stevage 4y ago
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.
bawolff 4y ago
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.
bombcar 4y ago
Added is easy. It’s removed that is the tricky part, though perhaps you could reuse IDs somehow. Maybe a hashing function could work.
zarzavat 4y ago
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.
HALtheWise 4y ago
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.
anewhnaccount2 4y ago
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.
blackboxlogic 4y ago
For the smallest change with the fairest result, I would reseed the random IDs on a schedule.
amai 4y ago
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 https://en.wikipedia.org/wiki/Low-discrepancy_sequence

by onos 4y ago

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?

stevage 4y ago

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.

bawolff 4y ago

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.

bombcar 4y ago

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

zarzavat 4y ago

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.

HALtheWise 4y ago

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.

anewhnaccount2 4y ago

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.

blackboxlogic 4y ago

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

amai 4y ago

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 https://en.wikipedia.org/wiki/Low-discrepancy_sequence