Geo індекс для пошуку нових знайомих або революційне відкриття вчених з Австрії

Як ви знаєте, Badoo — сервіс для пошуку нових людей. Крім усього іншого, ми дозволяємо шукати людей навколо і в «грі» теж показуємо людей, які знаходяться недалеко від вас. Ця частина «навколо» дуже і дуже важлива. Адже молодій людині з Новосибірська набагато цікавіше познайомитися з дівчиною, яка живе в п'яти хвилинах ходьби від нього, а не у Владивостоці.
Ми досі не розповідали публічно про те, як ми це робимо. Але нове відкриття австрійських вчених настільки нас порадувало, що ми зважилися це зробити. Перейдемо ж до справи.
Badoo працює по всьому світу і наш пошук працює абсолютно однаково, незалежно від того, в якій точці земної кулі ви знаходитесь. Як же ефективно шукати серед усіх людей навколо 200+ мільйонів користувачів?
Рішення нетривіально, чесно кажучи. Нам потрібен якийсь індекс, якийсь спосіб відразу ж звузити область пошуку. У випадку з земною кулею, самим простим поділом є сітка географічних широт і довгот. Однак проблема з цією сіткою в її нерівномірності. Осередок у північного полюса і осередок біля екватора мають зовсім різні форми. Таке несиметричне розбиття вносить великі проблеми, якщо ми хочемо рівномірно розподілити навантаження по пошуковому кластеру.

Яким чином розбити поверхню земної кулі так, щоб осередки були рівні один одному? Хоча б приблизно. Ми в Badoo згадали про один з правильних многокутників, а саме ікосаедр. Його грані-рівні правильні трикутники. Граней у ікосаедра всього 20, що занадто мало для ефективного расшардивания навантаження по пошуковому кластеру. Але ж його межі теж можна розбити на трикутники.

Спроектуємо вершини і ребра ікосаедра на сферу Землі. Розіб'ємо рекурсивно трикутники задаються икосаэдром на 4 дрібніших трикутника. І так два рази. Отримаємо в підсумку 320 граней. На жаль, вже не рівних. Далі — програмкою на пітоні згенеруємо ~100000 рядків коду на C, які вміють робити трансформацію lon/lat -> трикутник.



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



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

Як ефективно шукати людей у маленькому трикутнику, використовуючи нашу систему координат ми обов'язково розповімо в майбутньому, якщо вам цікаво, але ми б хотіли сьогодні повернутися і більш докладно поговорити про «великих» трикутниках.

Запропоноване нами рішення по розподіленню земної кулі має недоліки, пов'язані з нерівномірністю, так і з точністю. Незважаючи на 320 шард, ми часто стикаємося з перекосами в навантаженні.

І ось, пару тиждень тому, з нами зв'язалися наші друзі — співробітники Австрійського Інституту Науки і Технологій і розповіли про їх відкриття.

Використовуючи розроблену ними техніку пошуку симетричних перерізів багатовимірних решіток і ресурсомісткі комп'ютерні обчислення їм вдалося побудувати нове симетричне розподіл сфери на шестикутники з досить великою кількістю вершин. Отримані дизайн вони назвали «Гексасфера». На сайті з анонсом статті викладена інтерактивна модель даного поділу. Вставити її сюди ми не змогли, так що відвідайте посилання, щоб погратися з нею.



Протягом минулого тижня ми щільно попрацювали разом з австрійцями, допрацювали наш алгоритм, і домоглися абсолютно рівномірного розподілу навантаження по шардам.

Badoo для своїх користувачів став точніше, для нас система стала більш передбачуваною і стійкою до навантажень, а науковці з Австрії, сподіваємося, побачили цікаве застосування для своїх ідей.
У наступній статті ми обов'язково більш докладно розповімо як працює цей алгоритм і покажемо на графіках ті поліпшення, яких нам вдалося досягти.

Марко Кевац, розробник-дослідник

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.