GeoEnrichment is one of the important building blocks deciding the success of an ad tech platform. The easiest way to leverage your campaign’s success is to pinpoint your audience location accurately.

You must target the right area with the right content at the right time.

For instance, let’s consider that you have a business based in Bangalore and you don’t offer shipping to anywhere else across India or abroad. In such a scenario you should only focus on advertising your offerings to the audience residing in Bangalore. This is called Geo targeting.

Here, we will demonstrate how using a special category of Geo targeting called Radius targeting we precisely served relevant ads to our customers at specific locations.
 

Geo Polygons – S2 Cells and Aerospike

Geo polygons are a series of (x, y) coordinate pairs that enclose an area of interest (like a supermarket store, a school, or an airport) on the earth’s map. At InMobi, we fetch these data with the help of external vendors and also manually create them as needed using our inhouse tools.
 

Problem Statement

For a given ad request we need to find the list of polygons that encircles the latitudes and longitudes of the concerned request. As an example, let’s consider that you are at a café inside an airport, and then you open an app that triggers an ad request to InMobi. For this particular request you should return two polygons – first the café where you are sitting, and then the airport where the café is located. Now InMobi will serve you relevant ads like offers from the café and nearby bars and restaurants within the airport.

InMobi receives billions of ads requests every minute and our polygon data is huge. Just imagine all the manmade structures we created on the planet. So, finding an optimum solution to the problem is quite a challenge.
 

The 3-Step Solution

STEP 1: Convert the Polygon to a List of S2 Cell

We used spatial indexing using Google’s open source S2 Geometry Library. The S2 library helps in decomposing a sphere (planet earth in our case) into a hierarchy of cells (known as S2 cells) that represent compact regions and points. These cells have a few noteworthy features:

• They are compact and represented by 64-bit integers.

• They follow hierarchical levels wherein similar levels have similar areas.

• The containment query for arbitrary regions is processed fast.

The cell hierarchy in the S2 library starts from Level 1 that covers the entire earth to Level 30 that covers an area of 0.72 sq. cm. only. While conducting a few proof-of-concepts we observed that levels ranging from 17 to 21 best suits our use case and we used these cells to create our polygon

Take a look at the example shown above. Imagine a big polygon that represents an area of interest. Let's convert it into minimum sized list of S2 cells ranging from levels 17 to 21, and accurately create the shape of the polygon.
 

STEP 2: Store the S2 Cells in Aerospike Database

Use an in-memory datastore like Redis or Aerospike to store this polygon data. The data is in key-value format where your key is an S2 cell, and your value is a JSON array containing the metadata of all the polygons that encompass this S2 cell.
 

STEP 3: Serving Relevant Ads

Now that all our pre-processing needs have been completed let’s observe our serving stac

Once we receive an ad request the following steps are executed while serving the ad.

• Extract the latitudes and longitudes of the region from where the request arrived.

• Find the S2 cells that encompasses these latitudes and longitudes from levels ranging from17 to 21. This will fetch you exactly four S2 cells.

• Query your datastore to fetch all the polygons that encompass these S2 cells and send them back as a response.

In this particular problem the data was ranged while the query was a point. Now let’s take another challenge where the data is a set of points, and the query is ranged.
 

Geo-based Content Recommendation

Consider a social media forum where users post content from different locations. Let’s say that we want to show 50 posts to all the users from their nearby locations.
 

Geohashing in Redis

The Geohash of a point is computed based on its geographic coordinates and it uniquely identifies a rectangular cell in a two-dimensional coordinate system. Geohash has several useful properties that are significantly useful for geospatial indices.

Arbitrary Precision

Geohash is arbitrarily precise. Redis automatically computes and stores an internal representation of the Geohash.

Shared Prefix for Nearby Points

If the Geohash of two distinct points share the same prefix, it’s safe to assume that they are spatially closer to each other. Longer the prefix, closer will the point be together. Evidently, each character in the Geohash uniquely identifies a rectangular cell at varying resolutions.

Geo API in Redis

Now that we are familiarized with the internal representation of geospatial objects by Redis, let’s discuss the API that enables using these features.

GeoAdd Text

To add points to the key Redis computes the Geohash based on the coordinates shared.

127.0.0.1:6379> GEOADD cities -122.34 47.61 Seattle
(integer) 1

Location QueryText

You may query a point using the BYBOX argument.
127.0.0.1:6379> GEOSEARCH posts FROMLONLAT -77.0368707 38.9071923 BYRADIUS 500 km WITHCOORD WITHDIST WITHHASH
1) 1) "post01"
   2) "0.0000"
   3) (integer) 1790437241089913
   4) 1) "-77.03687041997909546"
      2) "38.90719290381756679"
2) 1) "post02"
   2) "56.2166"
   3) (integer) 1790521436838452
   4) 1) "-76.61219090223312378"
      2) "39.29038444452294954"
3) 1) "post03"
   2) "198.4242"
   3) (integer) 1791689799529163
   4) 1) "-75.16521960496902466"
      2) "39.95258288212141196"
4) 1) "post04"
   2) "327.6765"
   3) (integer) 1791873974571312
   4) 1) "-74.00594204664230347"
      2) "40.71278377862454789"