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

Термины и определения

Client Device (Клиентское устройство)

Устройство (компьютер, смартфон, планшет), используемое пользователем для взаимодействия с интерактивной картографической системой.

Containment Relationship (Отношение вложенности)

Связь между двумя сущностями в графе, указывающая, что одна сущность географически содержится внутри другой (например, город внутри страны).

Entity (Сущность)

Объект, представленный узлом в графе. Может включать географические объекты (страны, города, улицы), конкретные места (бизнесы, достопримечательности, остановки транспорта), а также категории и подкатегории (отели, рестораны).

Expanded Query Suggestion (Расширенное предложение запроса)

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

Graph (Граф)

Структура данных, состоящая из узлов (Nodes), представляющих сущности, и связей (Links), представляющих отношения между ними (например, containment, proximity, category).

Interactive Mapping System (Интерактивная картографическая система)

Система (например, Google Maps), предоставляющая картографические данные и функциональность поиска по ним.

Node (Узел)

Элемент в структуре данных Graph или Trie.

Prefix (Префикс)

Начальная последовательность символов строки. Например, "new y" является префиксом "New York".

Proximity Relationship (Отношение близости)

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

Query Logs (Логи запросов)

Хранилище ранее выполненных поисковых запросов. Используется для определения популярных запросов и выявления связей между сущностями.

Trie (Префиксное дерево)

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

Viewport (Область просмотра)

Текущая географическая область, отображаемая на карте в интерфейсе пользователя.

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает основной метод предоставления расширенных подсказок.

1. Система получает один или несколько символов, введенных в интерфейс.
2. Идентифицируется узел в графе (identified node) на основе введенных символов. Этот узел представляет сущность, название которой содержит префикс, соответствующий введенным символам. Граф содержит узлы (сущности) и связи (отношения между узлами).
3. Идентифицируется узел-кандидат (candidate node) в графе, который связан с идентифицированным узлом на основе одной или нескольких связей в графе. Узел-кандидат представляет сущность, название которой имеет префикс, НЕ содержащий введенные символы.
4. Название сущности, представленной узлом-кандидатом, предоставляется как Expanded Query Suggestion.

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

Claim 2 (Зависимый от 1): Детализирует процесс ранжирования нескольких кандидатов.

1. Идентификация включает определение множества узлов-кандидатов.
2. Для каждого кандидата рассчитывается оценка предложения (suggestion score).
3. Кандидаты ранжируются на основе этой оценки.
4. Ранжированный список названий сущностей, представленных одним или несколькими кандидатами с наивысшим рейтингом, предоставляется как Expanded Query Suggestions.

Claim 3 (Зависимый от 2): Описывает фильтрацию на основе географической близости к Viewport.

1. Множество кандидатов фильтруется путем расчета географической близости конкретного кандидата к географическому региону, представленному в Viewport.
2. Кандидат удаляется, если его географическая близость превышает пороговое значение (т.е. он слишком далеко).

Claim 4 (Зависимый от 2): Описывает фильтрацию на основе размера географического объекта (сужение поиска).

1. Множество кандидатов фильтруется путем удаления кандидата, если связанный с ним географический объект больше, чем географический объект, связанный с идентифицированным узлом.

Это гарантирует, что подсказки сужают область поиска, а не расширяют ее (например, не предлагать "Калифорния" для запроса "Mountain View").

Claims 5-8 (Зависимые от 1): Уточняют типы отношений в графе, используемые для поиска кандидатов.

• Claim 5: Отношение вложенности (containment relationship).
• Claim 6: Отношение близости (proximity relationship).
• Claim 7: Отношение категория/сущность (category/entity relationship).
• Claim 8: Отношение категория/подкатегория (category/subcategory relationship).

Claim 9 (Зависимый от 1): Описывает использование Trie для идентификации узла.

1. Идентификация узла в графе включает идентификацию узла в структуре Trie, соответствующего введенным символам, при этом узел в Trie связан с узлом в графе.

Где и как применяется

Изобретение применяется на этапах индексирования и понимания запросов для обеспечения работы системы поисковых подсказок (Autocomplete).

INDEXING – Индексирование и извлечение признаков

• Построение Графа Сущностей: На этом этапе система анализирует картографические данные (Map Data) и строит Graph. Устанавливаются связи между сущностями на основе географических данных (containment, proximity) и классификации (category).
• Анализ Логов Запросов: Query Logs анализируются для определения популярных запросов и выявления дополнительных связей между сущностями, которые могут не следовать из географических данных (например, связь "Париж" и "Диснейленд" из-за популярности запроса "Диснейленд Париж").
• Построение Trie: Все префиксы названий сущностей индексируются в Trie. Узлы Trie ассоциируются с соответствующими узлами Graph.

QUNDERSTANDING – Понимание Запросов (в реальном времени)

• Основное применение патента происходит здесь, в момент ввода запроса пользователем.
• Система использует Trie для быстрого поиска сущностей, соответствующих префиксу.
• Система использует Graph для обхода связей и генерации Expanded Query Suggestions.
• Применяются механизмы фильтрации и скоринга для выбора наилучших подсказок.

Входные данные:

• Последовательность символов, введенных пользователем.
• Текущая область просмотра карты (Viewport).
• Граф сущностей (Graph).
• Префиксное дерево (Trie).

Выходные данные:

• Список ранжированных поисковых подсказок, включающий как стандартные автодополнения, так и Expanded Query Suggestions.

На что влияет

• Конкретные типы контента: Наибольшее влияние на локальные страницы, страницы бизнесов, достопримечательности и географические объекты.
• Специфические запросы: Влияет на информационные и транзакционные запросы, связанные с поиском мест, категорий бизнесов или маршрутов. Особенно актуально для запросов, указывающих на географическую область (например, название города), где система может предложить конкретные популярные места в этой области.
• Конкретные ниши или тематики: Критически важно для Локального SEO, туризма, недвижимости, ритейла и любых бизнесов, привязанных к физическому местоположению.

Когда применяется

• Условия работы: Алгоритм работает в реальном времени при вводе каждого символа в строку поиска интерактивной картографической системы.
• Триггеры активации: Активируется, когда система идентифицирует в Trie узел, соответствующий введенному префиксу, и этот узел связан с сущностями в Graph, которые, в свою очередь, имеют связи с другими релевантными сущностями.
• Ограничения: Эффективность зависит от качества и полноты Graph и Trie, а также от наличия данных в Query Logs для определения популярности и связей.

Пошаговый алгоритм

Процесс А: Предварительная обработка (Офлайн)

1. Индексация префиксов: Система индексирует префиксы всех названий географических объектов и сущностей в Trie.
2. Построение связей: Система строит Graph сущностей, устанавливая связи (containment, proximity, category, связи на основе Query Logs).
3. Ассоциация структур: Узлы графа ассоциируются с соответствующими узлами Trie, хранящими префиксы их названий.

Процесс Б: Обработка запроса (Реальное время)

1. Получение символа: Система получает очередной символ запроса от клиентского устройства.
2. Обход Trie: Система перемещается по Trie к узлу, соответствующему текущему полному префиксу.
3. Идентификация кандидатов: Для каждого узла графа, ассоциированного с текущим узлом Trie, система следует по связям в графе для идентификации связанных узлов-кандидатов (потенциальных Expanded Query Suggestions).
4. Фильтрация (Сужение поиска): Система отбрасывает узлы-кандидаты, если соответствующий географический объект не сужает запрос (т.е. если он больше, чем исходная сущность).
5. Фильтрация (Близость к Viewport): Система отбрасывает узлы-кандидаты, если соответствующий географический объект находится за пределами порогового расстояния от текущей области просмотра (Viewport). (Исключение: связи, основанные на сильных сигналах из Query Logs, могут игнорировать это ограничение).
6. Скоринг: Система оценивает оставшиеся узлы-кандидаты. Оценка может основываться на вероятности упоминания сущности в запросе (P(f)) или условной вероятности (P(f2|f1)), полученной из Query Logs.
7. Генерация подсказки: Система генерирует расширенный запрос с использованием названия сущности из узла-кандидата с наивысшей оценкой.
8. Предоставление подсказки: Система отправляет расширенный запрос клиентскому устройству для отображения пользователю.

Какие данные и как использует

Данные на входе

• Географические факторы: Критически важные данные. Используются координаты сущностей, размеры географических областей, иерархия административных единиц. Эти данные необходимы для построения связей Containment и Proximity в графе, а также для фильтрации по Viewport.
• Структурные факторы (Классификация): Данные о категориях и типах сущностей (бизнес, достопримечательность, город, отель, ресторан). Используются для построения связей Category/Entity и Category/Subcategory.
• Поведенческие факторы (Query Logs): Анонимизированные логи запросов используются для:
  • Определения популярности сущностей (для скоринга).
  • Выявления связей между сущностями на основе частоты совместного упоминания в запросах (например, связь "Париж" и "Диснейленд").
  • Расчета условных вероятностей P(f2|f1) для скоринга.
• Пользовательские факторы: Текущая область просмотра карты (Viewport) используется как контекст для фильтрации предложений по близости. Язык интерфейса может использоваться при скоринге.

Какие метрики используются и как они считаются

• Proximity Threshold (Порог близости): Пороговое значение расстояния, используемое для установления связи Proximity между двумя сущностями в графе, а также для фильтрации кандидатов относительно Viewport. Порог может зависеть от типа сущностей.
• Suggestion Score (Оценка предложения): Метрика для ранжирования кандидатов. Патент предлагает несколько вариантов расчета:
  • На основе вероятности P(f), что сущность будет упомянута в запросе.
  • На основе кумулятивной вероятности связанных сущностей (CPRF(f)). Формула для расширенной подсказки f2, связанной с f1: