One common use-case one encounters in location-based advertisement is that there is a set of businesses that want to place ads to customers that are nearby. These ads, that are placed on the mobile phones of customers, should first be relevant. The customers receiving the ads should be proximal to the business. The hope here is that the advertisement (that may contain a coupon) customers will incentivise them to go from from their present location to the place where the business is situated. In traditional web-based advertisement world, Click-Through Rate (CTR) is considered a metric of success which roughly corresponds to how many people click on an advertisement. In this local advertisement space, success is measured by Store Visitation Lift (SVL), which is a measure of many people actually end up going to the business and redeeming the coupon they received over the wire. Hence, local advertisement is much more directly connected to the bottomline of a business.

When sending a coupon to a customer, one has to be careful not to send a coupon for a business that a customer cannot really reach. Most existing advertisement companies use crow-flying distance as a measure of proximity of a customer from a business, but this can be very erroneous. For instance, there may be a bay or a lake between the customer’s current location and the business. In this case, even though the customer is proximal when it comes to crow-flying distance, the actual road distance could be very large. There could possibly be a toll road between the person’s current location and the business, which almost guarantees that the person would never end up using the coupon. If one is not careful, the SVL metric could be very low.

For this use-case one needs a method that can accurately compute the actual road distance or the trip time distance between customers and businesses. Another requirement is that as these ads need to be delivered at a very high rate. Hence, one needs a method that can compute road distances or trip time at a very high throughput.

In this article, we develop a simple use-case using two tables, customers and business. In this example, we will show how one can use our technology to find all customers within a fixed distance of a business.The customer table records the current position of the customer, while the business table records the positions of the businesses.

We first create a simple customer table with a id, latitude and longitude information and load synthetic data from a CSV file.

drop table customers;
create table customers (id int, lat double precision, lon double precision);
\copy customers from customers.txt with DELIMITER E'\t';

Create the necessary indices for the customer table. Note that we do not need any kind of special indices.

alter table customers add column code bigint;
update customers set code = Z2(lat, lon);
create index customer_idx on customers (id);
create index customer_code on customers(code);

Create the business table and necessary indices similar to the customer table above.

drop table business;
create table business (id int, lat double precision, lon double precision);
\copy business from business.txt with DELIMITER E'\t';
alter table business add column code bigint;
update business set code = Z2(lat, lon);
create index business_idx on business (id);
create index business_code on business(code);

We first write a simple function that takes an id of a business and a distance value. The MinMaxCode function takes these as inputs and produces two codes corresponding to the morton code of the top-left and bottom-right corner of the bounding box denoting the search region. All the customer.code values that are contained within these values will be found by scanning between these two values.

CREATE OR REPLACE FUNCTION MinMaxCode(INT, DOUBLE PRECISION)
   RETURNS TABLE (minCode BIGINT, maxCode BIGINT,
                  lat double precision, lon double precision)
    LANGUAGE sql IMMUTABLE AS
          'SELECT Z2(business .lat - $2 /110.0,
           business.lon - $2 * COS(RADIANS(business.lat))/110.0)
           as code1,
           NYZ2(business.lat + $2/110.0,
           business.lon + $2 * COS(RADIANS(business.lat))/110.0)
           as code2, lat, lon FROM business
    WHERE id = $1;';

This final function findNearest actually performs the region search around the selected business and is aided by the Btree indices on the tables.

CREATE OR REPLACE FUNCTION findNearest(INT, DOUBLE PRECISION)
   RETURNS SETOF RECORD LANGUAGE sql IMMUTABLE AS
     'SELECT * FROM (
                    SELECT id, dist(customers.lat,
                           customers.lon, (foo.minmaxcode).lat,
                          (foo.minmaxcode).lon) as dist
                    FROM customers,
                        (SELECT MinMaxCode($1, $2/1000)) as foo
     WHERE code >= (foo.minmaxcode).minCode
           AND code <= (foo.minmaxcode).maxCode) AS FOO1
     WHERE dist <= $2;';

We can now quickly search for all customers within 100 meters of business id 321 in a fraction of a second. This will return a customer id and a distance in meters.

SELECT findNearest(321, 100);

One can also use nearest neighbor searches to match businesses with customers. Please look at our use-case for computing the nearest neighbors between two sets of points at a high-throughput, which is directly applicable to this use-case.