company_banner

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

    Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке.
    Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.
    Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?
    Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.

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

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



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



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

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

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

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

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



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

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

    Марко Кевац, разработчик-исследователь
    Badoo 354,78
    Big Dating
    Поделиться публикацией
    Похожие публикации
    Комментарии 31
    • –11
      Если это на первое апреля, то могли бы что-нибудь позабавнее придумать.
      • +1
        Можно еще покурить HEALPix
        • –4
          Почему-то напомнило:
          image
          • +2
            В с большой натяжкой можно считать за развертку сферы. Но применимость такой проекции — низкая.
        • +1
          В течение прошлой недели мы плотно поработали вместе с австрийцами, доработали наш алгоритм, и добились абсолютно равномерного распределения нагрузки по шардам.

          Нарезка земли на равны кусочки ведет к равномерности нагрузки? Но ведь кусочек, содержащий условный Дели будет гораздо более нагружен, чем кусочек с условной Антарктидой.

          Мы в подобной задаче просто брали проекцию Меркатора, да там искажения на полюсах, но ведь на полюсах и пользователей сильно меньше, не так ли?
          • 0
            Они использовали правило календаря для тестирования математической модели.
            • 0
              Что за правило календаря такое?
              • +3
                Открываешь текущую дату и проверяешь (ровна ли разница между днем и месяцем 3) и (день месяца первый)? аааа! все правильно:))): бред какой — то;
            • 0
              Будет гораздо более нагружен. Вы правы. Смотрите ответ на этот комментарий: habrahabr.ru/company/badoo/blog/254643/#comment_8356027
            • 0
              Круто! А вот предлагать знакомых рядом с учетом языка вы так и не научились. Живу в Париже и в Лионе и мне постоянно чернокожих красавиц предлагают. Спасибо, но пока нет)
              • 0
                Вам бы русских русых красавиц в Париже отыскать? :-)
                • 0
                  Именно! Французские девушки не такие интересные. Кроме того, тут много русских, ищущих именно русских. И это стандартное желание среди эмигрантов.
                  И еще: а нужно ли равномерное разбиение сферы? Ведь наверняка нагрузка там больше, где плотность населения больше? Может имеет смысл сгущать сетку в густонаселенных районах? Это представит возможности по более детальному поиску. Например, в мегаполисах как Москва и Мехико можно делить по районам.
                  • –1
                    Имеет. Вы правы.
                    Но разве можно отказаться от такого революционного открытия, как гексасфера? Можно ее просто сделать гуще! Равномерно гуще! :-)
                    • 0
                      Вот и я про это же говорю.

                  • 0
                    мне постоянно чернокожих красавиц предлагают

                    Радоваться надо.
                  • +1
                    А у вас какой язык интерфейса?
                  • +1
                    В веб-версии (badoo.com), в People Nearby (Люди рядом) есть настройки поиска, в которых есть advanced search. Там можно искать девушек всяко-разно. Можно найти рыжеволосую, зелёноглазую, без вредных привычек, выше 170 сантиметров, не занятую, живущую отдельно, говорящую по-русски девушку за секунду. Если повезёт, и не одну. =) Удачи!
                    • 0
                      В мобильной веб-версии есть только мальчик/девочка, разброс возрастов и цель знакомства. А настольной версией неудобно на телефоне пользоваться.
                  • +18
                    Сидят в гримерке два клоуна — молодой и старый, выдумывают репризу. Молодой говорит: давайте вы выйдете на манеж, уроните кошелек, нагнетесь, а я выбегу из-за кулисы и дам вам сапогом по ж*пе. Старый печально отвечает: не годится. Слишком тонкая шутка для нашего цирка…
                    • +1
                      Мне кажется или австрийцы изобрели футбольный мяч с более мелким разбиеним?
                      image
                      • 0
                        мяч у вас неправильный. Пятиугольники где?
                      • +6
                        Если никто не заметил, это разбиение невозможно. :)
                        • 0
                          Ну так было уже сегодня GT — http://geektimes.ru/post/248214/
                          • 0
                            Возможно, более того — стандартно — en.wikipedia.org/wiki/Geodesic_grid
                            image
                            • 0
                              У вас прямо на приведенной картинке видны пятиугольники :)
                          • 0
                            Вопрос — а если граница такого треугольника/шестиугольника проходит ну допустим прямо по середине города, значит поиск будет произведен только в одном шарде, и живущие, например прямо возле её границы никогда не найдут свою вторую половину из соседней улицы только потому что шарды так разбиты? Прямо как Берлинская стена…
                            • 0
                              Штуки в сторону, такие ситуации у нас обходятся таким образом, что треугольники пересекаются, накладываются друг на друга. Т.е. пользователи в какой-то области будут дублироваться в накладывающихся треугольниках.
                            • 0
                              А почему вы решили использовать свое, вместо уже известных R-деревьев (и вагона других spatial индексов)?
                              • 0
                                Какие вы порекомендуете из «вагона»?

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

                              Самое читаемое