В среду, 6 марта 2013 года, в официальном блоге Facebook появился пост, опубликованный командой разработчиков социального поиска Facebook Шрирамом Санкаром (Sriram Sankar), Сореном Лассеном (Soren Lassen) и Майком Куртиссом (Mike Curtiss). В публикации создатели социального поиска соцсети (Graph Search) делятся секретами  работы алгоритма с широкой аудиторией.

От истоков к современности

История создания алгоритмов социального поиска от Facebook восходит к самому началу работы соцсети: первый внутренний поисковый алгоритм носил название PPS. Принцип его работы сводился к поиску по ключевым словам. Однако, по заявлению разработчиков, уже тогда поисковый движок соцсети был персонализированным, а специальные фильтры позволяли пользователю осуществлять поиск по людям, страницам, местам и группам.

В 2009 году команда Facebook начала работу над новым поисковым алгоритмом, который впоследствии получил название Typeahead (буквально: опережающий ввод с клавиатуры). Как видно из названия, алгоритм начинал предлагать пользователю результаты еще в процессе ввода поискового запроса в строку. Анализ происходил в результате сопоставления «префиксов» т.е. частей слова с персонализированной базой, построенной на основе анализа активности пользователя и его контактов в соцсети. Это требовало от разработчиков кардинального пересмотра «внутреннего устройства» алгоритма. Работа по его созданию была окончательно завершена в 2010 году.

Строго говоря, Typeahead вобрал в себя огромное количество новых алгоритмов. Кроме того, в него был интегрирован PPS. В случае, если пользователю была необходима расширенная информация – поиск Facebook обращался именно к первично разработанному алгоритму.

В последствии синтез этих двух алгоритмов позволил создать множество других программ и формул. Так, например, алгоритм Nearby, позволил пользователям указывать свое местоположение, что соответствующим образом отразилось на внутреннем поиске Facebook. Результатом такой эволюции стала идея создать социальный поиск Graph Search. Однако для этого было необходимо разработать  такую систему индексирования, которая могла бы поддерживать качественную работу всех существующих алгоритмов.

Рождение «Единорога»

В итоге, у программистов Facebook родилась идея создания поиска на основе социального графа. Это могло бы позволить алгоритмам анализировать взаимосвязи пользователей, их интересы, предпочтения, местоположение и пр. При таком подходе профиль пользователя выступает в качестве ключевого «узла», вокруг которого будут формироваться определенные связи «лучи» (стрелки на схеме). Таким образом, каждый пользователь, страница, фото, место, пост выступают в качестве ключевых узлов в алгоритме поиска. Связи между этими узлами - это контакты пользователей, их чекины, ссылки, связи, подписки и т.п.

Далее алгоритм анализирует взаимосвязь «узлов» и «лучей» на основе метаданных. Так, например, алгоритм анализирует имя пользователя, дату его рождения, интересы, а затем связывает с другим узлом в случае нахождения его заголовка и описания в системе метаданных. Каждому узлу в системе графа присваивается уникальный номер (внутренне название: fbid).

В целом, социальный граф включает в себя такую информацию, как лайки пользователя, его дружбу, социальную активность. На эти данные накладывается информация, релевантная абсолютно для каждого пользователя. К примеру, это может быть дружба между Королевой Елизаветой и Георгом VI или история «Звездных Войн». Этот «микс» общей информации и социального контекста в каждом отдельно взятом графе и делает Facebook ресурсом с огромной базой персонализированного контента, позволяющей пользователю «подстраивать выбор информации под себя». Основная идея социального поиска заключается в том, чтобы искать все новые и новые связи («лучи») для объединения «узлов».

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

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

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

Основные компоненты Unicorn представляли собой:

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

Таким образом, совокупное fbid профиля Дэвида равно 10003; fbid Нью-Йорка и сериала «Аббатство Даунтон» - 111 и 222, соответственно. Дополнительные обозначения «друг» с fbid -10003, «живет в» - 111 и «любит» - 222 будут присвоены в качестве атрибутов и другим пользователям аналогичным образом.

Особенности алгоритма Unicorn позволяют с легкостью находить подобные «узлы» и обозначать их связи среди больших массивов данных. Алгоритм анализирует связи и «привязывает» их к ключевому узлу, тем самым наращивая социальную базу.

Принцип работы алгоритма таков:

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

Так, например, если человек забьет в поисковой строке словосочетание [tennyson frost] – абсолютно любая поисковая система предложит ему варианты страниц: 1. на которых встречаются оба этих слова (в случае использования оператора AND) ; 2. страницы со словом [tennyson]; страницы со словом [frost] (в случае использования оператора OR). Аналогичным способом работает и алгоритм «Единорог».

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

К примеру, если пользователь ищет [места работы друзей, живущих в Нью-Йорке], алгоритм, на первом этапе работы составит список «узлов», связанных с исходным профилем. Цепочка будет выглядеть следующим образом. Профиль пользователя – «узлы» профилей друзей – друзья, живущие в Нью-Йорке. На следующем этапе алгоритм возьмет итоговый список узлов и наложит на его связи с работодателям, используя для установки связей формулировку [живущих в Нью-Йорке], а затем, накладывая на нее «узлы» работодателей, выявленные на основании этих связей.

Адаптация поискового алгоритма под особенности соцсети

По заявлению разработчиков алгоритма, Unicorn представляет собой мощную систему, способную существенно ускорить поиск для пользователя.

Вот как происходит индексация: к примеру, необходимо проиндексировать профили пяти пользователей: Марк Цукерберг [Mark Zuckerberg] (fbid: 4), Рэнди Цукерберг [Randi Zuckerberg] (fbid: 13755), Марк Дэвид Джонсон [Mark David Johnson] (fbid: 1001), Рэнди Джонсон [Randi Johnson] (fbid: 5542), и Дэвид Джонсон [David Johnson] (fbid: 10003).

Вот как будут выглядеть, присвоенные их профилям индексы:

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

Вертикальные линии диаграммы называются списки взвешенных значений (posting lists) – это суммарный индекс fbid. Таким образом, список взвешенных значений для профиля “mark” включает индексы 4 и 1001. Горизонтальные линии, изображенные на диаграмме описывают объекты . Таким образом, объект с fbid 4 будет проиндексирован как “mark” и “zuck” (fbid 4 имеет сразу 2 атрибута). Аналогичным образом производится присвоение атрибутов и другим профилям и связям.

Алгоритм Unicorn позволяет осуществлять поиск и сопоставление объектов: 

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

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

С этой целью в алгоритм был введен параметр static rank. Он служит определенным фильтром и позволяет находить «узлы» значимые для каждого конкретного пользователя.

В ходе индексации учитываются все возможные особенности и ограничения. Кроме того, алгоритм постоянно дописывается и развивается. Это обусловлено тем, что в соцсети ежедневно создается более 2,5 млрд. новых единиц контента, добавляется более 2,7 млрд. лайков и т.п. Это означает, что помимо индексации статических данных, алгоритм должен уметь работать с постоянно обновляемыми данными. Все изменения, которые регулярно вносятся пользователями в соцсеть мгновенно попадают в индекс, обрабатываются и выводятся в результатах поиска буквально через несколько секунд после их появления на страницах Facebook.

Дополнительная информация о том, как работает алгоритм Unicorn и социальный поиск Fcebook в целом, доступна в видеоролике здесь.

Перевод Анастасии Матвеевой