4 ms·

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

by tpetry 5y ago

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.

Bootvis 5y ago
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.
matzf 5y ago
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.

by tpetry 5y ago

Bootvis 5y ago

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.

matzf 5y ago

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.