What is geotargeting?

With the near-ubiquity of smartphones, consumers are now almost always carrying around GPS-enabled devices. This GPS data allows companies to target consumers with advertisements based on their real-time location. This is called geotargeting.

What are the benefits of geotargeting?

Geotargeting allows companies to customize their advertising based on where their consumers are at any given point. For example, a brick-and-mortar clothing company could use GPS data to track and target potential customers within a 20 km radius with a specific ad. Or, a food delivery company could focus their advertising efforts on people living in certain areas of busy cities who may not have a car or live within walking distance of a supermarket and would therefore be ideal new customers. Of course, before any usage of geotargeting data, a clear user-consent must be collected in Europe.

According to General Data Protection Regulation (GDPR), the new European regulation that strengthen and unify data protection for all individuals within the European Union, companies have to obtain explicit consent from users in order to collect their geolocation data.

Our geotargeting solution

In the past, our geotargeting techniques at mediarithmics were constrained by our only being able to target large regions defined by governmental parameters. This was not precise enough for our clients so we decided to rebuild our geotargeting system following the specs below.

We wanted our clients to be able to:

• target specific and separate regions, e.g. both Paris and New York but nowhere else;
• exclude a sub-region from a larger region, e.g. all of Paris except for the 9th district;
• target hyperlocal areas, e.g. areas within 5 meters of any Paris bus stop;
• mix hyperlocal and administrative-based targeting data.

We also knew that our bidding bot must be able to run the targeting quickly, regardless of its complexity.

Creating a nice API

Our initial solution was to represent both hyperlocal targets (such as the radius around a bus stop) as well bigger regions (such as Paris) as polygons. The polygons would then be assembled using predicates and boolean operators. In scala, it would look like this:

Example of possible targeting API

And on the map it would look like this:

(1) Paris (2) Paris 9th district (3) Paris without the 9th district

Using this solution, the first three specs are met (target specific and separate regions; exclude a sub-region from a larger region; target hyperlocal areas). However, the solution did not meet our final criteria — to run the target quickly, regardless of its complexity.

If we were only targeting Paris and using one polygon then it would take one unit of time to check and see whether a specific consumer were in Paris. However, if we wanted to blend that data with hyperlocal data and look at all the 12,000+ Paris bus stops — say for a taxi company — we’d have to look at every single bus stop to see whether a consumer was close to that stop. That would take 12,000 units of time.

This was obviously a no-go for our bid bot which has to make a decision on whether to target a consumer within milliseconds.

Fortunately, we were able to develop a simple solution to fix this issue. This solution does not use polygons in the targeting. Instead, it runs in time proportional to the logarithm of the geotargeting precision which, in CS parlance is O(ln(n)). It means the bidbot can decide whether a person is, for example, in mainland France in ~5 units of time, in Paris in ~11 units of time or near any Paris bus stops in ~22 units of time. This solution utilizes a quadtree data structure to map a region.

Introducing quadtrees

In a quadtree structure, we create a series of nodes linked by branches. Each node has either four “children” or no children. Each childless node (or “leaf”) is black or white. The black leaves represent the areas we would target and the white leaves represent the areas we would not target. It is an incredibly useful data structure for efficiently dividing up a two-dimensional space. Here is what this quadtree solution would look like if the world were divided into a tree while targeting central Europe with the ABCC node:

A representation of the targeting of central Europe

The above targeting of central Europe, represented as a tree

Making quadtrees

Now, we don’t need our clients to feed us a quadtree. We still want them to describe their geotargeting using expressions such as, “users in Paris as well as users in London” therefore we needed to transform the high-level description of targeting (the one with nice boolean operators) into an optimized quadtree.

We do this by recursively checking whether each square of the quadtree is inside the polygon. If the square is entirely inside the polygon, it becomes a black leaf. If the square is entirely outside, it becomes a white leaf. And if it is neither in nor out, the square is further divided into 4 sub-squares and each sub-square is then tested.

This is a gif showing what that geotargeting strategy would look subdividing South America as a region:

Instead of indefinitely subdividing squares that are neither in nor outside the polygon, we stop at pre-defined depth in the tree (e.g. four in the gif) and consider the overlapping squares as inside the target. Thus, the overlapping squares will become black leaves in the tree. We then proceed to merge levels that are entirely made of same color leaves into a higher level of a single leaf (i.e. when four leaves of a node are black, the node is replaced by a single black leaf). This improves the tree performance by minimizing its depth. You can see this merge happening in the gif over the western coast of South America (CAB and CAC in the tree).

When there are several polygons in the geotargeting, we build a quadtree for each of the polygons and merge all those quadtrees into one. At the end, regardless of the original number and complexity of polygons, we have only one quadtree remaining. This quadtree is then used by the bidbot to determine whether a consumer is inside a targeted area.

Using quadtrees

Let’s say we want to target customers in “ABCC” as illustrated in this picture:

Here’s what the typical process would look like of deciding whether or not a consumer whose GPS coordinates indicates he is in Tokyo is within the target or not:

• We look at the the root of the tree.
• We see that the root has 4 children.
• Using the GPS coordinates, we determine that we have to look at its “A” child.

Looking at the root

• We look at the “A” node of the tree.
• We see that “A” has 4 children.
• Using the GPS coordinates, we determine that we have to look at its “AD” child.

Looking at “A”

• We look at the “AD” node of the tree.
• We see that “AD” is a leaf, with no child.
• We look at the color of the leaf. We see that the leaf is white, therefore the consumer is not within the targeted area.

Looking at “AD”

Giving our clients this quadtree solution allows them to be extremely creative with how they use geotargeting in their advertising. They can target thousands of custom hyperlocal areas or giant regions as they did before with no performance issues on our side.