Благодаря тому, что смартфоны стали почти повсеместными, потребители теперь почти всегда носят с собой устройства с поддержкой GPS. Эти данные GPS позволяют компаниям показывать потребителям рекламу на основе их местоположения в реальном времени. Это называется геотаргетингом.

В чем преимущества геотаргетинга?

Геотаргетинг позволяет компаниям настраивать свою рекламу в зависимости от того, где находятся их потребители в любой момент. Например, обычная компания по производству одежды может использовать данные GPS для отслеживания и нацеливания на потенциальных клиентов в радиусе 20 км с помощью конкретной рекламы. Или компания по доставке еды может сосредоточить свои рекламные усилия на людях, живущих в определенных районах оживленных городов, которые могут не иметь машины или жить в нескольких минутах ходьбы от супермаркета и поэтому будут идеальными новыми клиентами. Конечно, перед любым использованием данных геотаргетинга в Европе необходимо получить четкое согласие пользователя.

В соответствии с Общим регламентом защиты данных (GDPR), новым европейским регламентом, который усиливает и унифицирует защиту данных для всех лиц в Европейском Союзе, компании должны получать явное согласие пользователей на сбор их геолокационных данных.

Наше решение для геотаргетинга

В прошлом наши методы геотаргетинга в mediarithmics были ограничены только тем, что мы могли ориентироваться только на большие регионы, определяемые государственными параметрами. Это не было достаточно точным для наших клиентов, поэтому мы решили перестроить нашу систему геотаргетинга в соответствии со спецификациями ниже.

Мы хотели, чтобы наши клиенты могли:

  • таргетинг на конкретные и отдельные регионы, например и Париж, и Нью-Йорк, но больше нигде;
  • исключить подобласть из более крупного региона, например весь Париж, кроме 9-го округа;
  • целевые гиперлокальные области, например районы в пределах 5 метров от любой автобусной остановки Парижа;
  • смешивать гиперлокальные и административные данные таргетинга.

Мы также знали, что наш торгующий бот должен уметь быстро запускать таргетинг, независимо от его сложности.

Создание хорошего API

Наше первоначальное решение состояло в том, чтобы представить как гиперлокальные цели (например, радиус вокруг автобусной остановки), так и более крупные регионы (например, Париж) в виде полигонов. Затем многоугольники будут собраны с использованием предикатов и логических операторов. В scala это будет выглядеть так:

А на карте это будет выглядеть так:

При использовании этого решения выполняются первые три спецификации (целевые и отдельные регионы; исключение подобласти из более крупного региона; целевые гиперлокальные области). Однако решение не соответствовало нашим последним критериям - быстро выполнить цель, независимо от ее сложности.

Если бы мы настраивали таргетинг только на Париж и использовали один многоугольник, то для проверки и определения того, был ли конкретный потребитель в Париже, потребовалась бы одна единица времени. Однако, если бы мы хотели объединить эти данные с гиперлокальными данными и посмотреть на все более чем 12 000 автобусных остановок в Париже - скажем, для таксомоторной компании - нам пришлось бы посмотреть на каждую автобусную остановку, чтобы увидеть, находится ли потребитель рядом с этой остановкой. . На это потребуется 12000 единиц времени.

Очевидно, это был запрет для нашего бота для ставок, который должен принять решение о том, нацеливаться ли на потребителя в течение миллисекунд.

К счастью, нам удалось разработать простое решение для устранения этой проблемы. Это решение не использует полигоны в нацеливании. Вместо этого он выполняется по времени, пропорциональному логарифму точности геотаргетинга, которая на языке CS равна O(ln(n)). Это означает, что робот может решить, находится ли человек, например, на материковой части Франции за ~ 5 единиц времени, в Париже через ~ 11 единиц времени или рядом с любой остановкой парижского автобуса за ~ 22 единицы времени. Это решение использует структуру данных квадродерева для отображения региона.

Представляем квадродеревья

В структуре квадродерева мы создаем серию узлов, связанных ветвями. У каждого узла есть четыре «потомка» или нет потомков. Каждый бездетный узел (или «лист») бывает черным или белым. Черные листья представляют собой области, на которые мы нацелены, а белые листья - области, на которые мы не нацелены. Это невероятно полезная структура данных для эффективного разделения двухмерного пространства. Вот как выглядело бы это решение quadtree, если бы мир был разделен на дерево, ориентируясь на центральную Европу с помощью узла ABCC:

Изготовление квадродеревьев

Теперь нам не нужно, чтобы наши клиенты кормили нас деревом квадрантов. Мы по-прежнему хотим, чтобы они описывали свой геотаргетинг с помощью таких выражений, как «пользователи в Париже, а также пользователи в Лондоне», поэтому нам нужно было преобразовать высокоуровневое описание таргетинга (с красивыми логическими операторами) в оптимизированное дерево квадрантов.

Мы делаем это, рекурсивно проверяя, находится ли каждый квадрат квадродерева внутри многоугольника. Если квадрат полностью находится внутри многоугольника, он становится черным листом. Если квадрат полностью находится снаружи, он становится белым листом. И если он ни внутри, ни снаружи, квадрат далее делится на 4 подквадрата, и каждый подквадрат затем проверяется.

Это гифка, показывающая, как будет выглядеть эта стратегия геотаргетинга при разделении Южной Америки на регион:

Вместо того, чтобы бесконечно разделять квадраты, которые не находятся ни внутри, ни за пределами многоугольника, мы останавливаемся на заранее определенной глубине в дереве (например, четыре на гифке) и рассматриваем перекрывающиеся квадраты как внутри цели. Таким образом, перекрывающиеся квадраты станут черными листьями на дереве. Затем мы переходим к объединению уровней, которые полностью состоят из листьев одного цвета, в более высокий уровень одного листа (т.е. когда четыре листа узла черные, узел заменяется одним черным листом). Это улучшает производительность дерева за счет минимизации его глубины. Вы можете увидеть это слияние на гифке над западным побережьем Южной Америки (CAB и CAC на дереве).

Когда в геотаргетинге несколько полигонов, мы строим квадродерево для каждого из полигонов и объединяем все эти квадродерева в одно. В конце концов, независимо от исходного количества и сложности многоугольников, у нас остается только одно дерево квадрантов. Затем это дерево квадратов используется ботом для определения того, находится ли потребитель в целевой области.

Использование квадродеревьев

Допустим, мы хотим привлечь клиентов из ABCC, как показано на этом рисунке:

Вот как будет выглядеть типичный процесс определения того, находится ли потребитель, чьи координаты GPS указывают, что он находится в Токио, в пределах цели:

  • Смотрим на корень дерева.
  • Мы видим, что у рута 4 потомка.
  • Используя координаты GPS, мы определяем, что должны посмотреть на его дочерний элемент «A».

  • Смотрим на узел «А» дерева.
  • Мы видим, что у «А» 4 ребенка.
  • Используя координаты GPS, мы определяем, что должны посмотреть на его дочерний элемент «AD».

  • Смотрим на узел «AD» дерева.
  • Мы видим, что «AD» - это лист без дочернего элемента.
  • Смотрим на цвет листа. Мы видим, что лист белый, следовательно, потребитель не попадает в целевую зону.

Предоставление нашим клиентам этого решения quadtree позволяет им проявлять крайнюю изобретательность в том, как они используют геотаргетинг в своей рекламе. Они могут нацеливаться на тысячи настраиваемых гиперлокальных областей или гигантских регионов, как и раньше, без каких-либо проблем с производительностью с нашей стороны.