Optimizing Targetings

One of the oldest ideas for the optimization of targetings is to use reverse indices.

I worked in a few companies over 15 years ago, and they utilized it to their benefit. But the first time I read about it, though, was in an O’Reilly book on the use of Redis, just a few years ago. You can look it up there.

However, here it is with a very simple approach.

Campaign Example

Imagine that you have an ad network that has only demographic information about the users, and campaigns use age and gender targeting.

(And this is a formulation I had when I interviewed for my first adtech job, where I was able to come up with a concept by the end of a 4-hour interview. And I’m still grateful to this company and the amazing people I met there.)

So let’s talk about the campaigns for a while.

  • Campaign 1 targets male audience between ages 35 and 40.
  • Campaign 2 targets people between 21 and 40.
  • Campaign 3 has no targetings (it’s a catch-all campaign).

And there are 10k campaigns like that.

So what would be an efficient way to match campaigns, so that we can choose between them?

Creating Reverse Indices with Bitsets

The answer is simple. We create reverse indices!

For age:

  • 21 → bitset of campaigns targeting 21-year-olds
  • 22 → bitset of campaigns targeting 22-year-olds
  • …
  • 40 → bitset of campaigns targeting 40-year-olds
  • And, a bitset of campaigns that have no age targeting

For gender:

  • male → bitset of campaigns targeting male audience
  • female → bitset of campaigns targeting female audience
  • other → bitset of campaigns targeting ‘other’ audience
  • And, a bitset of campaigns that have no gender targeting

When we create bitsets, for simplicity, we can just assume that we have 10k campaigns, and they are numbered from 0 to 9999. And when campaigns 1 and 2 target 36-year-olds, the bits 1 and 2 will be set in a 10k-bit-long bitset.

Applying Targetings

So let’s say we have a 22-year-old male. To find all the campaigns that match, we just need to do two things:

  1. Find these bitsets:

    • Bitset for 22-year-olds (bitset(age, 22))
    • Bitset for campaigns without age targeting (bitset(age, any))
    • Bitset for campaigns targeting male audience (bitset(gender, male))
    • Bitset for campaigns without gender targeting (bitset(gender, any))

  2. Apply targetings:

    (bitset(age, 22) | bitset(age, any)) & (bitset(gender, male) | bitset(gender, any))

And because vectorized bit operations are a part of many processors’ instruction sets, and the operation of creating bitsets only happens on config load, this is a ridiculously efficient way of evaluating targetings.

Extending to Geolocation Targeting

And for geo, what we’d get for New York City, NY, US:

(bitset(city, NYC) | bitset(city, ANY)) & (bitset(region, NY) | bitset(region, ANY)) & (bitset(country, US) | bitset(country, ANY))

Seems very straightforward. What gives?

Well, 10k campaigns make about a 1KB bitset. 10k cities will be about 10MB in memory, which isn’t that bad.

And this seems to work perfectly for the fields with lower cardinality.

High-Cardinality Fields

However, there are fields with higher cardinality.

Domains, apps, etc.

These might require gigabytes of memory.

My answer to this is: if we filter out SOME of the campaigns and then apply targetings, that’d be good enough.

And so with certain field value distributions, simple hash-based buckets can work quite nicely.

Meaning, we decide from the start how many bitsets we are ready to maintain for a specific field, and assign campaigns to bitsets based on a hash of the field value modulo the number of buckets.

So with this approach, bitsets will contain campaigns that might match the field.

The success of this will mostly depend on the distribution of targetings, with the worst case being having a lot of values being in all of the campaigns (e.g., a super popular allowlisted domain).

But if you have a lot of these high-cardinality fields with a very unfortunate distribution of values in targetings, and if you filter out 10–15% of campaigns on each of them, this will very positively compound.

There can be other approaches to a more intelligent assignment of bitsets to values. Again, even with a very high-cardinality field, it’s easy to maintain a reverse index hashmap with a million values pointing to just a handful of bitsets. And if we go for filtering rather than exact matching approach here, we can actually have an array of references to bitsets, or just an index of a bitset. E.g., we don’t have to store the value of the field, because hash collision is fine, since we are going to evaluate targetings exactly anyway.

Let’s talk about something more fun next time, like pacing!