Hacker News Reader

Comment by tpetry | Hacker News Reader

Your randomness may also sometimes be at the edge. I am the author of the article, if you do know any failure in my approach i am happy to fix it.

View on HN

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.

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.

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.

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.

The benefit of this solution is that we don't want to depend on SQL to generate unlimited random numbers: one for each row of the table is a lot of work.

While this approach does have this benefit, it's no longer "random" in the sense that all rows are equally likely to be selected. So, it depends on your purpose as to whether this is an acceptable solution. I don't see any reason to do it in 2D over 1D, except that some of the flaws in the approach are more obscured.

I'm unclear why you can't do traditional gold standard simple random sampling, where you repeatedly generate random numbers and look up the index of those numbers.

The k-NN algorithm should still be at least O(n) (I think?)

Simple random sampling is O(1), with respect to the total number of table rows.

Is the problem that you want exactly three rows, and some numbers will be rejected if you don't re-index? SQL can manage while loops:

https://dev.mysql.com/doc/refman/8.0/en/while.html

i think mostly because this is even more complicated than the approach taken, and the proposed solution is good enough. If you do have large gaps in your dataset you can also account for them by just blocking a range of numbers ahead of time, optionally with a monthly cron job to identify new gaps larger than X rows, depending on how often new such gaps form.

if you have thousands of rows, it doesn't really matter if one is 3 times as likely to show up as another one, as long as the odds aren't stacked too heavily towards any one row (at least for what I assume to be the typical use case of showing users a random product/page/whatever)

> i think mostly because this is even more complicated than the approach taken

I understand that SQL is considered simpler if you have code-golfed it into one line, but the procedure of simple random sampling is much simpler than generating a 2D map of points and finding the nearest one.

I guess you have a point there. My gut instinct was that it'd be more complicated to understand/modify but thinking about it a bit more I don't think that's really necessarily the case. And even with much more rows being filtered out than being included in the predicate, it would take looking at the same amount of rows on average (I think) to find the desired amount of results. It might be worse if there's significantly more deleted rows than existing ones, though.

Reply on news.ycombinator.com