Advertisement System Tips

Question

I am creating an advertisement system which shows the highest bidder's ads more frequently.

Here is an example of the table structure I am using, but simplified...

+----+----------+------------------------+----------------------+-----+
| id | name     | image                  | destination          | bid |
+----+----------+------------------------+----------------------+-----+
| 1  | abc, co  | htt.../blah            | htt...djkd.com/      | 3   |
+----+----------+------------------------+----------------------+-----+
| 2  | facebook | htt.../blah            | htt...djkd.com/      | 200 |
+----+----------+------------------------+----------------------+-----+
| 3  | google   | htt.../blah            | htt...djkd.com/      | 78  |
+----+----------+------------------------+----------------------+-----+

Now, right now I am selecting the values from the database and then inserting them into an array and picking one out by random similar to the following:

$ads_array = [];
$ads = Ad::where("active", "=", 1)->orderBy("price", "DESC");

if ($ads->count() > 0) {
    $current = 0;
    foreach ($ads->get() as $ad) {
        for ($i = 0; $i <= ($ad->price == 0 ? 1 : $ad->price); $i++) {
            $ads_array[$current] = $ad->id;
            $current++;
        }
    }

    $random = rand(0,$current-1);
    $ad = Ad::where("id", "=", $ads_array[$random])->first();

    ...
}

So, essentially what this is doing is, it is inserting the advert's ID into an array 1*$bid times. This is very inefficient, sadly (for obvious reasons), but it was the best way I could think of doing this.

Is there a better way of picking out a random ad from my database; while still giving the higher bidders a higher probability of being shown?

Answer 1

Looks like this might do the trick (but all the credit go to this guy in the comments)

SELECT ads.*
FROM ads
ORDER BY -log(1.0 - rand()) / ads.bid
LIMIT 1

A script to test this :

<?php
$pdo = new PDO('mysql:host=localhost;dbname=test;', 'test', 'test');


$times = array();

// repeat a lot to have real values
for ($i = 0; $i < 10000; $i++) {
    $stmt = $pdo->query('SELECT ads.* FROM ads ORDER BY -log(1.0 - rand()) / bid LIMIT 1');
    $bid = $stmt->fetch()['bid'];
    if (isset($times[$bid])) {
        $times[$bid] += 1;
    } else {
        $times[$bid] = 1;
    }
}

// echoes the number of times one bid is represented
var_dump($times);

The figures that comes to me out of that test are pretty good :

// key is the bid, value is the number of times this bid is represented
array (size=3)
  200 => int 7106
  78 => int 2772
  3 => int 122

Further reference on mathematical explanation

Many important univariate distributions can be sampled by inversion using simple closed form expressions. Some of the most useful ones are listed here.

Example 4.1 (Exponential distribution). The standard exponential distribution has density f(x) = e−x on x > 0. If X has this distribution, then E(X) = 1, and we write X ∼ Exp(1). The cumulative distribution function is F(x) = P(X x) = 1 − e−x, with F−1(u) = −log(1 − u). Therefore taking X = − log(1 − U ) for U ∼ U(0, 1), generates standard exponential random variables. Complementary inversion uses X = − log(U ).

The exponential distribution with rate λ > 0 (and mean θ = 1/λ) has PDF λexp(−λx) for 0 x < ∞. If X has this distribution, then we write X ∼ Exp(1)/λ or equivalently X ∼ θExp(1), depending on whether the problem is more naturally formulated in terms of the rate λ or mean θ. We may generate X by taking X = − log(1 − U )/λ.

coming from http://statweb.stanford.edu/~owen/mc/Ch-nonunifrng.pdf