Социальный поиск Facebook в деталях. Тестирование и внедрение

15.03.2013 Соцсети

Facebook-Algorithm-Changes.jpgНачало статьи: 

Социальный поиск Facebook в деталях. Предпосылки

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

  • Лучшие рестораны для сотрудников Facebook;
  • Выпускники школы Ганн и студенты Стэнфорда;
  • Рестораны Сан-Франциско, одобренные выпускниками Кулинарного института.

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

В том же 2009 году разработчики создали инвертированный индекс, в котором хранился полный набор адресов, поставленных в соответствие с ключом для каждой лексемы, обозначенной пользователем. Алгоритм был назван Unicorn ("Единорог"), и к 2010 году стал основным алгоритмом поиска во всей соцсети. В 2011 году было принято решение использовать его как основной поисковый движок Facebook, объединив с ним остальные алгоритмы. Можно сказать, это и был первый шаг навстречу Graph Search.

"Единорог" состоял из трех основных компонентов:

  1. Индекс, представленный отображением свойств объекта и помогающий "связать" узлы лучами;
  2. Платформа для генерации индекса на основе других данных и с поддержкой постоянных обновлений;
  3. Платформа для извлечения объектов из базы данных с некоторыми ограничениями по атрибутам.

В качестве примера возьмем Пользователя, который является другом Дэвида. Внутренний номер Пользователя (fbid) - 1234, он проживает в Нью-Йорке и отметил "Аббатство Даунтон" в качестве любимого сериала. В результате его индексы станут следующими:

Друг: 10003 > 1234

Живет в: 111 > 1234

Любит: 222 > 1234

Очевидно, что fbid Дэвида - 10003, Нью-Йорка - 111, и сериала - 222. Аналогичным образом разбираются и атрибуты других пользователей.

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

Суть работы алгоритма проста:

Друзья Дэвида: «друг»: 10003

Жители Нью-Йорка: проживают в: 111

Поставили "Лайк" сериалу «Аббатство Даунтон»: 222

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

Например, поиск "tennyson frost" даст следующие результаты: страницы, на которых встречаются оба слова, и страницы, где встречается одно из них. На этом же принципе работает и Unicorn, выбирая релевантных и схожих пользователей из всей массы.

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

Так, пользователь, заинтересовавшийся должностью знакомых и спросивший "места работы друзей, проживающих в Нью-Йорке", задаст "Единорогу" следующие действия. Прежде всего, он создаст список узлов, связанных с профилем пользователя. Цепочка окажется следующей - профиль -> профили друзей -> место жительства друзей. На втором этапе алгоритм наложит связи с работодателями на имеющийся список узлов, принимая во внимание условие "проживающих в Нью-Йорке". В результате Unicorn "увидит" работодателей, подходящих под описание, и добавит их в качестве узлов. 

Окончание статьи:

Социальный поиск Facebook в деталях. Адаптация

 
Больше интересных статей

Оставьте номер телефона, чтобы наш менеджер связался с вами в удобное для вас время

Ваше имя*
Ваш номер телефона*
Тема для обсуждения
Выберите удобное время для звонка
9:00 9:15 9:30 9:45 10:00 10:15 10:30 10:45 11:00 11:15 11:30 11:45 12:00 12:15 12:30 12:45 13:00 13:15 13:30 13:45 14:00 14:15 14:30 14:45 15:00 15:15 15:30 15:45 16:00 16:15 16:30 16:45 17:00 17:15 17:30 17:45
Виды услуг
ОбзорМаксимальный размер файла - 10 мб