Geo индекс для поиска новых знакомых или революционное открытие ученых из Австрии

Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке.

Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.

Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?

Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.



Каким же образом разбить поверхность земного шара так, чтобы ячейки были равны друг другу? Хотя бы примерно. Мы в Badoo вспомнили про один из правильных многоугольников, а именно икосаэдр. Его грани представляют из себя равные правильные треугольники. Граней у икосаэдра всего 20, что слишком мало для эффективного расшардивания нагрузки по поисковому кластеру. Но ведь его грани тоже можно разбить на треугольники.

Спроецируем вершины и ребра икосаэдра на сферу Земли. Разобьем рекурсивно треугольники задаваемые икосаэдром на 4 более мелких треугольника. И так два раза. Получим в итоге 320 граней. К сожалению, уже не равных. Далее — программкой на питоне сгенерируем ~100000 строк кода на C, которые умеют делать трансформацию lon/lat -> треугольник.

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

Такой «большой» треугольник, в зависимости от желаемой точности поиска, мы можем и дальше разбивать на треугольники, все более и более «мелкие». Когда треугольники становятся достаточно мелкими по сравнению с радиусом земли — можно уже считать их «плоскими» и строить расстояния в «высотах треугольников», а не метрах.

Каждый из таких «маленьких» треугольников однозначно задается тройкой (a, b, c), где a, b, c являются номерами пересекающихся линий.

Как эффективно искать людей в маленьком треугольнике, используя нашу систему координат мы обязательно расскажем в будущем, если вам интересно, но мы бы хотели сегодня вернуться и более подробно поговорить о «больших» треугольниках.

Предложенное нами решение по разбиению земного шара имеет недостатки, связанные как с неравномерностью, так и с точностью. Несмотря на 320 шард, мы зачастую сталкиваемся с перекосами в нагрузке.

И вот, пару неделю назад, с нами связались наши друзья — сотрудники Австрийского Института Науки и Технологий и рассказали об их открытии.

Используя разработанную ими технику поиска симметричных сечений многомерных решеток и ресурсоемкие компьютерные вычисления им удалось построить новое симметричное разбиение сферы на шестиугольники с достаточно большим количеством вершин. Полученные дизайн они назвали «Гексасфера». На сайте с анонсом статьи выложена интерактивная модель данного разбиения. Вставить ее сюда мы не смогли, так что перейдите по ссылке, чтобы поиграться с ней.

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

Badoo для своих пользователей стал точнее, для нас система стала более предсказуемой и устойчивой к нагрузкам, а ученые из Австрии, надеемся, увидели интересное применение для своих идей.

В следующей статье мы обязательно более подробно расскажем как работает этот алгоритм и покажем на графиках те улучшения, которых нам удалось добиться.

Марко Кевац, разработчик-исследователь

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.