Как Google использует двухмерный индекс и пре-компьютерные пути для ультрабыстрого поиска в Knowledge Graph

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

Artificial Triple (Искусственный триплет)

Триплет, создаваемый системой индексирования, которого нет в исходном графе. Используется для интеграции текстового поиска (связывая сущность с текстовыми токенами — Text Search Aid) или для оптимизации запросов (например, Proximity Triples).

Bucket Posting Lists (Списки публикаций по бакетам)

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

Chain Path (Цепочечный путь)

Предварительно вычисленный путь в графе, состоящий из двух или более последовательных ребер (например, Актер → Фильм → Режиссер). Индексируется для ускорения многошаговых запросов.

Converge Path (Сходящийся путь)

Предварительно вычисленное пересечение двух или более предикатов, сходящихся на одной сущности (например, Актер И Певец). Индексируется для ускорения запросов с несколькими условиями.

Distance Predicate (Предикат расстояния)

Специальный предикат, который связывает сущность со всеми её предками (ancestors) в иерархии местоположений (прямой список) или связывает предков с сущностями внутри них (обратный список). Используется для обработки запросов на близость.

Entity Map (Карта сущностей)

Структура данных, генерируемая во время выполнения запроса (в прямом проходе). Хранит пары Intersection ID → Result ID, но индексируется по Result ID. Используется в обратном проходе для эффективного сопоставления отфильтрованных результатов с исходными идентификаторами.

Filterable Predicate (Фильтруемый предикат)

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

Intersection Identifier (Идентификатор пересечения)

Первое измерение (First Dimension) в двумерном индексе. Значения в этом измерении отсортированы и используются для выполнения операций пересечения (intersections) между списками.

Location Hierarchy (Иерархия местоположений)

Иерархическая структура, разделяющая пространство (географическое или временное) на базовые единицы (листья) и более крупные области (предки/ancestors). Используется для Proximity Queries.

Object Map (Карта объектов)

Структура, которая сопоставляет значение объекта с его рангом (rank) в отсортированном списке всех значений для данного предиката.

Posting List Value (Значение списка публикаций)

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

Proximity Posting Lists (Списки публикаций по близости)

Специализированные списки для оптимизации запросов близости. Связывают сущности с областями (ancestors) в Location Hierarchy, находящимися в пределах заданного радиуса.

Result Identifier (Идентификатор результата)

Второе измерение (Second Dimension) в двумерном индексе. Значения, связанные с конкретным Intersection Identifier. Могут содержать контекст (context), например, ранг или точное местоположение.

Triple (Триплет/Кортеж)

Базовая единица данных в графе: Субъект, Предикат, Объект (Subject, Predicate, Object).

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

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

Группа 1: Структура индекса и Пре-компьютинг (Claims 21-26)

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

1. Система использует графовую базу, поставляющую триплеты.
2. Создается индекс с двумерной структурой: Posting List Value → множество Intersection Identifiers → (для каждого) один или более Result Identifiers.
3. Система генерирует индексные записи для Субъекта, Объекта и Отношения (Предиката) каждого триплета.
4. Система предварительно вычисляет (pre-compute) записи, представляющие пересечение между двумя значениями списков публикаций, и сохраняет их в индексе.

Это фундаментальное утверждение, защищающее двумерный индекс и стратегию оптимизации через офлайн-вычисления (Chain/Converge Paths).

Claim 24 (Зависимый от 21): Определяет условие для пре-компьютинга.

Предварительное вычисление выполняется, когда количество триплетов для первого и второго значения списка велико (large), а результат их пересечения имеет значительно меньше (significantly fewer) членов. (Дорого вычислять, дешево хранить).

Группа 2: Индекс Близости (Claims 9-16)

Claim 9 (Независимый): Описывает механизм обработки Proximity Queries.

1. Индекс включает списки для диапазонов близости (proximity ranges) в пространстве (например, географическом), используя иерархию местоположений (location hierarchy).
2. Список связывает сущность с узлами (областями/ancestors) в иерархии, которые попадают в заданный диапазон близости от локации сущности.
3. Индекс также включает distance-predicate posting list, связывающий узлы иерархии с сущностями внутри них.

Это защищает механизм ускорения локального поиска за счет использования иерархических структур и предварительно рассчитанных областей.

Группа 3: Индекс Диапазонов (Claims 17-20)

Claim 17 (Независимый): Описывает механизм обработки числовых диапазонных запросов.

1. Индекс включает Bucket Posting Lists, представляющие диапазоны значений объектов.
2. Индекс включает Object-Rank Posting Lists, где объекты ассоциированы с рангом (rank).
3. Диапазоны бакетов основаны на этих рангах.

Это защищает механизм сегментации (bucketing) числовых данных для ускорения фильтрации по диапазонам.

Группа 4: Выполнение Запросов (Claims 1-8)

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

1. Система получает запрос из минимум двух этапов (stages).
2. Выполняется прямой путь (forward query path). На первом этапе применяется оператор expand, генерируются пары ID, и результаты передаются следующему этапу как входящие идентификаторы (incident identifiers).
3. Выполняется обратный путь (reverse query path) для генерации финальных результатов, отличных от результатов прямого пути.

Это защищает двухэтапный механизм выполнения запросов (вперед и назад) для эффективного обхода графа и применения ограничений.

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

Изобретение описывает фундаментальную архитектуру индекса и механизма запросов для Knowledge Graph.

INDEXING – Индексирование и извлечение признаков
Это основной этап применения патента. Вся система индексирования работает здесь.

• Построение Индекса: Обработка триплетов из графового хранилища и построение двумерного индекса (Index 155).
• Генерация Вспомогательных Структур: Создание искусственных триплетов (для текста и близости), обратных триплетов.
• Оптимизация (Офлайн): Расчет частот, присвоение ID (частые получают более короткие ID), вычисление и сохранение Chain Paths и Converge Paths.
• Обработка Атрибутов: Генерация Bucket Posting Lists (для чисел/дат) и Proximity Posting Lists (для геолокации).
• Обновления: Обработка изменений в графе и обновление индекса, включая отслеживание измененных сущностей (Updated Entities) для коррекции Pre-computed Paths.

RANKING (Этап Retrieval) / QUNDERSTANDING
На этих этапах система использует созданный индекс для быстрого извлечения данных и сопоставления запросов с сущностями.

• Извлечение данных: Query Resolver использует индекс для выполнения графовых операций (обход, пересечение) с низкой задержкой.
• Выполнение Запроса: Используется описанный механизм выполнения запросов (Forward/Reverse Path, Retrieval/Filling phase).
• Сопоставление текста: Искусственные триплеты помогают на этапе Query Understanding связывать текст запроса с сущностями графа.

Входные данные (Индексирование):

• Триплеты (S-P-O) из Knowledge Graph.
• Числовые и временные атрибуты сущностей.
• Географические координаты сущностей.
• Текстовые описания сущностей.

Выходные данные (Индексирование):

• Двумерный индекс (Index 155), включающий все типы списков публикаций.

Входные данные (Запрос):

• Структурированный запрос к графу (после этапа QUNDERSTANDING).

Выходные данные (Запрос):

• Набор сущностей и/или триплетов, удовлетворяющих запросу.

На что влияет

• Типы контента и форматы: Влияет на данные, хранящиеся в графе знаний. Это основа для генерации Knowledge Panels, Featured Snippets, каруселей сущностей.
• Специфические запросы:
  • Сложные фактологические запросы (например, "фильмы режиссера X с актером Y") — ускоряются через Pre-computed Paths.
  • Диапазонные запросы (например, "книги, изданные в 1980-х") — ускоряются через Bucket Lists.
  • Локальные запросы (например, "рестораны рядом со мной") — ускоряются через Proximity Lists.
• Ниши и тематики: Критическое влияние на локальный поиск (Local SEO) и тематики с большим количеством структурированных данных (E-commerce, Медиа, Биографии, YMYL).

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

• Во время индексирования: Постоянно, при построении и обновлении индекса Knowledge Graph (как в пакетном режиме, так и в реальном времени).
• Во время обслуживания запросов: Каждый раз, когда поисковая система обращается к Knowledge Graph.
• Триггеры оптимизаций:
  • Пре-компьютинг активируется офлайн, если пересечение дорого вычислять, но дешево хранить (большие входы, маленький результат).
  • Bucket/Proximity Lists активируются онлайн при наличии в запросе соответствующих условий (диапазон или близость).

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

Процесс А: Построение Индекса (Обобщение FIG. 5, 9, 11)

1. Сбор и Подготовка Данных: Получение триплетов из графа. Генерация искусственных триплетов (для текста и близости) и обратных триплетов.
2. Анализ и Присвоение ID: Расчет частотности сущностей и предикатов. Присвоение идентификаторов (частые получают более короткие ID).
3. Генерация Базового Индекса: Создание двумерных записей (Субъект, Предикат, Объект) для всех триплетов.
4. Генерация Диапазонных Индексов (Range):
   • Идентификация фильтруемых предикатов.
   • Сортировка объектов и присвоение рангов (Ranks). Создание Object Map и Object-Rank Entries.
   • Разбиение рангов на интервалы и создание Bucket Entries разной гранулярности.
5. Генерация Индексов Близости (Proximity):
   • Построение иерархии местоположений (Location Hierarchy).
   • Генерация Proximity Entries (связь сущности с областями в заданном радиусе) и Distance Predicate Entries.
6. Предварительное Вычисление Путей: Идентификация кандидатов (дорого вычислять, дешево хранить). Генерация и сохранение Chain-Path Entries и Converge-Path Entries.

Процесс Б: Выполнение Запроса (Обобщение FIGS. 13A, 13B, 14)

1. Разбор Запроса: Преобразование запроса в план выполнения (стадии и операторы).
2. Прямой Путь (Forward Path) - Фаза Поиска (Retrieval):
   • Стадии выполняются последовательно (или параллельно). Результат стадии (Incident Identifiers) передается следующей стадии.
   • Применение операторов (Expand, Seek). При использовании Expand/Seek генерируется Entity Map.
   • Результаты каждой стадии сохраняются (State). Цель — найти минимальный набор релевантных сущностей.
3. Обратный Путь (Reverse Path) - Фаза Заполнения (Filling):
   • Результаты передаются в обратном направлении. Каждая стадия получает от последующей отфильтрованный (pruned) набор идентификаторов.
   • Стадия фильтрует свои сохраненные результаты.
   • Используется Entity Map для преобразования отфильтрованных Result IDs обратно в Intersection IDs.
   • Генерируются итоговые кортежи (tuples) для ответа пользователю.
4. Обработка Обновлений (FIGS. 6, 7, 8): Если запрос использует Pre-computed Path, система проверяет измененные сущности (delta identifiers), пересчитывает путь только для них и объединяет с сохраненными данными.

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

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

Патент фокусируется на инфраструктуре индексирования графовых данных.

• Структурные факторы (Граф): Основные данные — это триплеты (Субъект, Предикат, Объект), определяющие структуру графа и связи между сущностями.
• Контентные факторы (Текст): Текстовые названия и описания сущностей используются для создания искусственных триплетов (Text Search Aids), обеспечивая текстовый поиск по графу.
• Географические факторы: Точные данные о местоположении сущностей используются для привязки к Location Hierarchy и генерации Proximity Posting Lists.
• Временные и Числовые факторы: Значения атрибутов (даты, цены, рейтинги), которые можно упорядочить. Используются для определения Filterable Predicates и генерации Bucket Posting Lists и Object-Rank Entries.

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

• Частотность (Frequency): Подсчет частоты встречаемости сущностей и предикатов. Используется для назначения эффективных идентификаторов (ID) и для выбора кандидатов на пре-компьютинг.
• Размер пересечения (Intersection Size): Метрика для определения целесообразности пре-компьютинга пути. Если результат пересечения значительно меньше исходных списков, путь вычисляется заранее.
• Ранг (Rank): Порядковый номер значения объекта в отсортированном списке всех значений для данного предиката. Используется для создания Bucket Posting Lists.
• Контекст (Context): Дополнительная информация, хранящаяся вместе с Result Identifier. Может содержать ранг (для диапазонных запросов), точное местоположение (для запросов близости) или оценочные сигналы (scoring signals).
• Единицы Иерархии Местоположений (Location Hierarchy Units): Базовые единицы (basic units) и предки (ancestors) используются для определения покрытия территории или времени при обработке запросов близости.

1. Специализированный индекс для Knowledge Graph: Google использует архитектуру индекса (двумерный индекс), фундаментально отличающуюся от веб-индекса. Она создана для эффективного хранения триплетов и быстрого выполнения операций обхода графа и соединений (joins).
2. Агрессивная оптимизация производительности: Система построена для обеспечения очень низкой задержки. Это достигается за счет предварительного вычисления сложных путей (Chain Paths и Converge Paths) и специализированных структур для диапазонных (Bucket Lists) и локальных (Proximity Lists) запросов.
3. Интеграция текста и графа: Механизм искусственных триплетов (Artificial Triples) является ключом к тому, как Google связывает текстовые запросы с сущностями в графе. Система индексирует текстовые токены из описаний сущностей для обеспечения текстового поиска по графу.
4. Критичность структурированных атрибутов: Числовые, временные и географические данные обрабатываются специальным образом для обеспечения быстрой фильтрации. Это подчеркивает важность точности этих атрибутов в данных о сущностях.
5. Сложный механизм выполнения запросов: Использование прямого и обратного пути (Forward/Reverse Path) и фаз Retrieval/Filling позволяет эффективно обрабатывать сложные запросы с множеством ограничений, минимизируя объем обрабатываемых данных на каждом этапе.
6. Инфраструктура для семантического SEO: Патент демонстрирует техническую реализацию хранения фактов. Для SEO это означает, что попадание в этот индекс требует максимальной ясности, структурированности и связанности данных о сущностях.

Best practices (это мы делаем)

• Четкое определение сущностей и связей (Structured Data): Используйте Schema.org для точного определения ключевых сущностей (Организация, Продукт, Автор, Место) и их взаимосвязей (worksFor, author, location, offers). Это напрямую соответствует формату триплетов, который индексируется в этой двумерной структуре.
• Обеспечение точности локальных данных (для Proximity Lists): Для локального бизнеса критически важны точные и консистентные координаты (NAP). Это позволяет системе корректно определить местоположение в Location Hierarchy и эффективно использовать Proximity Posting Lists для быстрого локального поиска.
• Указание фильтруемых атрибутов (для Bucket Lists): Четко размечайте числовые и временные данные (цены, даты публикаций, рейтинги). Это Filterable Predicates, которые индексируются в Bucket Posting Lists, ускоряя поиск с диапазонами и фильтрами.
• Использование ясного и описательного языка (для Artificial Triples): Оптимизируйте текстовые описания сущностей. Google токенизирует этот текст и связывает токены с сущностью через искусственные триплеты (Text Search Aids). Используйте естественный язык и релевантные термины для максимизации точек входа в граф через текстовый поиск.
• Построение связей для E-E-A-T (для Pre-computed Paths): Создавайте контент и разметку, которые формируют авторитетные связи между сущностями (например, эксперт -> организация -> награда). Это увеличивает вероятность того, что ваши сущности станут частью предварительно вычисленных путей (Chain/Converge Paths) и будут чаще извлекаться.

Worst practices (это делать не надо)

• Неоднозначное определение сущностей: Использование противоречивой информации или разметки, которая не позволяет однозначно идентифицировать сущность. Это затрудняет формирование корректных триплетов и индексацию в описанной структуре.
• Изоляция информации: Публикация фактов без привязки к контексту или другим сущностям. Изолированные сущности менее полезны, так как не участвуют в сложных пересечениях и обходах графа.
• Игнорирование структурированных данных или ошибки в них: Ошибки в Schema.org снижают вероятность того, что информация будет корректно интерпретирована и сохранена в этом высокооптимизированном индексе.
• Неточные или ложные гео-данные: Предоставление неверных координат может привести к некорректной работе Proximity Lists, что негативно скажется на видимости в локальном поиске.

Стратегическое значение

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

Практические примеры

Сценарий 1: Оптимизация локального бизнеса (Proximity Query)

1. Задача: Улучшить ранжирование ресторана по запросам "ресторан рядом со мной".
2. Действия: Обеспечить точные координаты в Google Business Profile и разметке LocalBusiness на сайте.
3. Как работает (по патенту): Система индексирования определяет местоположение ресторана в Location Hierarchy и генерирует Proximity Entries, связывая ресторан с географическими областями (ancestors) для разных радиусов (например, 1 миля, 5 миль).
4. Результат: Когда пользователь делает запрос, система использует эти предварительно вычисленные списки для мгновенного поиска ресторанов в нужной области, вместо того чтобы вычислять расстояние до каждого ресторана в городе в реальном времени.

Сценарий 2: Оптимизация интернет-магазина (Range Query)

1. Задача: Обеспечить видимость товаров при использовании фильтров по цене (например, "ноутбуки от $500 до $1000").
2. Действия: Использовать точную разметку Product и Offer с указанием цены.
3. Как работает (по патенту): Предикат "цена" является Filterable Predicate. Система присваивает ценам ранги и создает Bucket Posting Lists (например, бакет $500-$1000). Товары попадают в соответствующие бакеты.
4. Результат: При запросе с диапазоном цен система быстро сужает поиск до нужных бакетов, что значительно ускоряет получение результатов.