Hacker News Reader

Comment by Sesse__ | Hacker News Reader

It doesn't make any sense at all. Draw the Voronoi diagram; the cells will be of non-uniform size, so some points are much more likely to be picked than others. And why is this 2D? 2D doesn't give you any more randomness than 1D, it's just obfucscation.

If you computed the cell points anew for each sampling, it would indeed be random. But for repeated sampling, you've made up a very skewed distribution, where the successive samples are highly correlated.

View on HN

It‘s the best randomness that is achievable i am aware of. Do you have ideas for improvements?

It‘s 2d because databases do not have kNN with index support for a single float value. And without kNN you are building approach #2 with all of it‘s problems.

If you want quality randomness you can always do some equivalent of ORDER BY RAND() as long as you get a new RAND() for each row.

I've Googled around but didn't find anything about this trick:

You can calculate a score and do something like ORDER BY RAND() * score to bias towards certain rows. This could be useful, e.g. you want to randomly show your most profitable items. The kNN method seems harder to generalize.

This already has the same problems as #2, but worse;this already has uneven distribution from the beginning, even without deletions. Perhaps it may be worth pointing this out: you mention that this creates a "perfect random distribution" but that "with only a few records the distribution is not as perfect". This is a misconception; this perceived imperfection, the clumps etc, that's what random points always look like. The size of the voronoi cells, which determine the probability of a point to be sampled, are of very different sizes here. What you are thinking of is a random distribution of points where the points will have somewhat uniform distance to their neighbors. This is called blue noise. Creating scattered points with blue noise properties in 2d is not very complicated, but it is a bit more complicated than just combining two uniform random values. FWIW, uniform randomness does not even have blue noise properties in 1d, perhaps much more obviously.

Anyway, if you had this blue noise, whether 1d or 2d, would still not solve your problem; once you start deleting points, you lose your beautiful properties of uniform voronoi cell sizes and your back to square one.

Reply on news.ycombinator.com