Как Google создает специализированный индекс для сверхбыстрого поиска по Графу Знаний (включая гео-запросы и диапазоны)

Описание

Какую задачу решает

Патент решает проблему неэффективности и высокой задержки (high latency) при поиске информации в очень больших графовых базах данных (таких как Google Knowledge Graph) с использованием традиционных методов индексирования. Традиционные одномерные индексы плохо справляются со сложными запросами, требующими обхода графа (graph traversal), объединения данных (joins), а также с диапазонными (например, «фильмы 1990-2000 годов») и пространственными/временными запросами (например, «рестораны в радиусе 5 км»).

Что запатентовано

Запатентована система и метод создания специализированной инфраструктуры индексирования и обработки запросов для графовых данных. Ядром изобретения является двухмерная (two-dimensional) структура индекса, которая отличается от стандартных индексов для поиска документов. Также описаны методы оптимизации поиска путем предварительного вычисления сложных путей в графе и создания специальных структур для эффективной обработки диапазонных и пространственных запросов (Range Queries и Proximity Queries).

Как это работает

Система обрабатывает данные графа в виде триплетов (Triples): Субъект-Предикат-Объект. Она создает двухмерный индекс, где для каждого значения хранится список Идентификаторов Пересечения (первое измерение), и для каждого из них — список Идентификаторов Результата (второе измерение).

Для оптимизации система использует несколько ключевых механизмов:

• Предварительное вычисление путей (Pre-computed Paths): Сложные, но частые запросы (соединения) вычисляются заранее (Chain Paths и Converge Paths) и сохраняются в индексе.
• Диапазонные запросы (Range Queries): Для числовых или временных данных создаются Bucket Posting Lists, группирующие результаты по диапазонам значений для быстрого отсева.
• Пространственные запросы (Proximity Queries): Для географических или временных данных используется иерархия местоположений (Location Hierarchy) и специальные Proximity Posting Lists, чтобы минимизировать количество вычислений расстояний во время запроса.

Актуальность для SEO

Высокая. Граф Знаний (Knowledge Graph) является центральным компонентом современного поиска Google. Описанные в патенте механизмы обеспечивают инфраструктурную основу для быстрого извлечения структурированных данных, особенно в локальном поиске (гео-запросы) и поиске с уточнениями по датам или числам. Эффективность и низкая задержка остаются критически важными для Google.

Важность для SEO

Патент имеет инфраструктурное значение (4/10 по прямому влиянию на SEO-тактики). Он не описывает сигналы ранжирования, а фокусируется на том, как Google хранит и извлекает структурированные данные. Для Senior SEO-специалистов он важен для понимания того, что данные Графа Знаний индексируются иначе, чем веб-документы, и что Google обладает мощными инструментами для обработки сложных структурированных, локальных и диапазонных запросов с минимальной задержкой. Это подчеркивает стратегическую важность точных структурированных данных и оптимизации сущностей (Entity Optimization).

Детальный разбор

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

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

Базовая единица данных в графе, состоящая из Субъекта (Subject), Предиката (Predicate/Relationship) и Объекта (Object). Например, <Tom Hanks; acted in; Larry Crowne>.

Two-dimensional Index (Двухмерный индекс)

Структура индекса, используемая для графовых данных. В отличие от одномерного индекса (Термин -> Список Документов), двухмерный индекс имеет структуру: Значение Списка -> Идентификаторы Пересечения (Измерение 1) -> Идентификаторы Результата (Измерение 2).

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

Первое измерение в двухмерном индексе. Это измерение, по которому список сортируется и которое участвует в операциях пересечения (intersections).

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

Второе измерение в двухмерном индексе. Это данные, которые извлекаются на основе Идентификатора Пересечения.

Context (Контекст)

Дополнительная информация, связанная с Result Identifier. Может использоваться для хранения пола, оценки ранжирования, ранга объекта или точного местоположения.

Reverse Triple (Обратный триплет)

Искусственно созданный триплет <Объект; обратный_предикат; Субъект>. Позволяет осуществлять обратный обход графа.

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

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

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

Предварительно вычисленный путь, представляющий последовательность из двух и более ребер в графе (например, Актер -> Фильм -> Режиссер). Оптимизирует операции соединения (join).

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

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

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

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

Bucket Posting Lists (Списоки по бакетам/сегментам)

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

Proximity Posting Lists (Списки близости)

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

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

Иерархическая структура, разделяющая пространство (географическое или временное) на дискретные единицы. Включает Basic Units (базовые единицы, например, квадратный метр или секунда) и Ancestors (предки, более крупные единицы, например, район или час).

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

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

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

Патент является продолжением (Continuation) более ранней заявки. Хотя его описание (Description) охватывает общую систему двумерного индексирования, его Claims (Формула изобретения) в этой версии сфокусированы конкретно на механизмах обработки пространственных запросов (Proximity Queries).

Claim 1 (Независимый пункт): Описывает систему индексирования для эффективного ответа на запросы близости (Proximity Queries).

1. Система хранит индекс для графовой базы данных.
2. Индекс включает списки (posting lists) для одного или нескольких диапазонов близости (proximity ranges) в определенном пространстве (например, географическом).
3. Список содержит сущности, совместимые с этим пространством. Каждая сущность имеет местоположение (location), которое является базовой единицей (basic unit) в иерархии местоположений (location hierarchy).
4. Для каждой сущности список также содержит узел (node/ancestor) в иерархии, который попадает в указанный диапазон близости от местоположения сущности. Этот узел связан с контекстом (context).
5. Система использует этот индекс и контекст для ответа на запрос, включающий диапазон близости.
6. Цель использования индекса и контекста — уменьшение количества вычислений расстояний, что приводит к снижению задержки (latency) ответа на запрос.

Claim 12 (Независимый пункт): Конкретизирует Claim 1 для географического пространства.

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

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

1. Получение запроса с диапазоном близости и параметрами сущностей.
2. Определение базовых сущностей (base entity), соответствующих параметрам.
3. Выбор списка близости (Proximity Posting List) с предопределенным диапазоном, который больше, чем диапазон в запросе.
4. Использование выбранного списка для определения областей (areas/ancestors), связанных с базовой сущностью.
5. Использование списка предиката расстояния (distance-predicate posting list) для поиска целевых сущностей (target entities) в этих областях. Этот список предоставляет контекст (context) для целевых сущностей.
6. Контекст используется для уменьшения количества вычислений расстояний при определении того, попадают ли целевые сущности в диапазон запроса (точная фильтрация).
7. Генерация результата с уменьшенной задержкой.

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

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

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

На этом этапе происходит вся основная работа по созданию описанной инфраструктуры:

• Обработка триплетов и создание базового двухмерного индекса.
• Генерация искусственных триплетов (Artificial Triples) для текстового поиска и пространственных данных.
• Предварительное вычисление Chain Paths и Converge Paths.
• Создание структур для диапазонных запросов (Object-Rank, Bucket Posting Lists).
• Построение иерархии местоположений (Location Hierarchy) и создание Proximity Posting Lists и Distance Predicate списков.

RANKING – Ранжирование (L1 Retrieval) / METASEARCH

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

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

• Триплеты из графовой базы данных (Knowledge Graph).
• Данные о местоположении сущностей (географические или временные).
• Числовые данные, связанные с сущностями.
• Обновления графа (Deltas).

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

• Эффективный двухмерный индекс графа (Index 155).
• Быстрые результаты поиска по запросам, включающим обход графа, диапазонные и пространственные ограничения.

На что влияет

• Локальный поиск (Local Search): Механизмы Proximity Queries напрямую влияют на обработку запросов типа «рядом со мной» или «в радиусе X км». Это критично для страниц Google Business Profile и локальных лендингов.
• E-commerce и запросы с числовыми фильтрами: Механизмы Range Queries (Bucket Posting Lists) влияют на запросы с фильтрацией по цене, рейтингу, размеру и т.д.
• Временные запросы: Влияет на запросы, ограниченные временными рамками (события, даты выпуска, исторические периоды).
• Сложные структурированные запросы: Механизмы предварительного вычисления (Chain/Converge Paths) влияют на скорость ответов на запросы, требующие соединения данных (например, «актеры, которые также являются режиссерами»).

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

• Индексирование: Применяется постоянно или периодически для поддержания актуальности индекса графа. Также включает механизмы для обработки обновлений в реальном времени (real-time updates).
• Обработка запросов: Активируется всякий раз, когда запрос пользователя требует извлечения данных из графа. Специализированные механизмы активируются при обнаружении в запросе диапазонных или пространственных ограничений.

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

Патент описывает несколько алгоритмов. Ниже приведены ключевые процессы индексирования и обработки пространственного запроса.

Процесс А: Общее индексирование графа

1. Получение триплетов: Система получает триплеты из графа.
2. Генерация искусственных триплетов: Создаются дополнительные триплеты для поддержки текстового поиска (search triples) и пространственных запросов (proximity triples).
3. Расчет частотности и назначение ID: Вычисляется частота сущностей и предикатов. Более частым элементам назначаются более короткие идентификаторы для оптимизации памяти.
4. Генерация базового индекса: Создаются записи в двухмерном индексе для Субъектов, Предикатов и Объектов.
5. Генерация обратного индекса: Создаются записи для обратных триплетов (Reverse Triples) для обеспечения обратного обхода графа.
6. Генерация предварительно вычисленных путей: Идентифицируются и вычисляются Chain Paths и Converge Paths для оптимизации сложных запросов.
7. Генерация диапазонных индексов: Создаются Object-Rank и Bucket Posting Lists для фильтруемых предикатов.
8. Генерация пространственных индексов: Создаются Proximity Posting Lists и Distance Predicate списки на основе иерархии местоположений.

Процесс Б: Обработка пространственного запроса (Proximity Query)

1. Получение запроса: Система получает запрос, содержащий диапазон близости (например, 8 км) и параметры сущностей (например, База=Рестораны, Цель=Заправки).
2. Определение базовых сущностей: Идентифицируются все сущности, соответствующие базовым параметрам (все Рестораны).
3. Выбор списка близости: Выбирается наименьший предопределенный Proximity Posting List, который полностью покрывает диапазон запроса (например, список «10-км-радиус»).
4. Поиск предков (Ancestors) — Грубая фильтрация 1: Базовые сущности пересекаются с выбранным списком близости. Результат — набор Предков (областей в иерархии местоположений), которые находятся в радиусе 10 км от каждого ресторана.
5. Поиск целевых сущностей (Targets) — Грубая фильтрация 2: Полученные Предки пересекаются с обратным списком Distance Predicate. Результат — набор всех сущностей (включая Заправки), расположенных в этих областях.
6. Фильтрация по типу: Из набора целевых сущностей отбираются те, которые соответствуют целевым параметрам (только Заправки).
7. Точное вычисление расстояния (Pruning): Для оставшихся пар (Ресторан-Заправка) система вычисляет точное расстояние, используя данные о местоположении, хранящиеся в Контексте (Context).
8. Финальная проверка диапазона: Проверяется, попадает ли точное расстояние в исходный диапазон запроса (8 км).
9. Формирование результата: Пары, прошедшие проверку, добавляются в результат поиска.

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

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

Патент фокусируется на использовании структурированных данных для построения индекса.

• Структурные факторы (Граф): Основные данные — это триплеты (Субъект, Предикат, Объект), определяющие структуру графа и связи между сущностями.
• Географические факторы: Для Proximity Queries используются точные местоположения сущностей (например, широта/долгота), которые затем преобразуются в базовые единицы (Basic Units) иерархии местоположений.
• Временные факторы: Аналогично географическим, используются для временных пространственных запросов (например, события в течение X дней от даты).
• Числовые данные: Значения объектов для фильтруемых предикатов (цены, рейтинги, даты), используемые для Range Queries.
• Контентные (Текстовые) факторы: Текстовые описания или имена сущностей используются для создания искусственных триплетов (Artificial Triples), позволяющих выполнять текстовый поиск по графу.

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

• Частотность (Frequency): Используется для назначения идентификаторов (более частые получают короткие ID) и для выбора кандидатов на предварительное вычисление путей (пересечение двух больших списков, дающее маленький результат).
• Ранг объекта (Object Rank): Для диапазонных запросов система сортирует все уникальные значения объектов фильтруемого предиката и присваивает им ранг. Этот ранг хранится в Object-Rank Posting Lists.
• Бакеты (Buckets): Диапазоны рангов группируются в бакеты фиксированного размера для ускорения поиска.
• Иерархия Местоположений (Location Hierarchy): Метрика для пространственных запросов. Пространство делится на базовые единицы (Basic Units) и агрегируется в предков (Ancestors).
• Контекст (Context): Используется для хранения вспомогательных метрик, таких как точное местоположение (для финального расчета дистанции) или ранг объекта.

Выводы

1. Инфраструктурный фокус: Это глубоко инфраструктурный патент. Он описывает не то, что Google считает важным для ранжирования, а то, как Google технически реализует хранение и сверхбыстрое извлечение данных из Графа Знаний.
2. Двухмерный индекс для графов: Google использует специализированный two-dimensional index для структурированных данных, который принципиально отличается от индекса веб-документов и оптимизирован для обхода связей между сущностями.
3. Оптимизация сложных запросов: Система разработана для обработки сложных запросов на огромных масштабах с очень низкой задержкой (десятки миллисекунд). Это достигается за счет предварительных вычислений (Pre-computed Paths) для соединений данных.
4. Критичность скорости для Local/E-commerce: Значительная часть патента посвящена оптимизации диапазонных (Range) и пространственных (Proximity) запросов. Использование Bucket Lists и Location Hierarchies позволяет мгновенно обрабатывать фильтры по ценам, рейтингам, датам и расстояниям.
5. Эффективность пространственного поиска: Механизм Proximity Queries позволяет избежать ресурсоемкого вычисления расстояний между всеми парами объектов. Система сначала грубо определяет область (Ancestor), а затем выполняет точные расчеты только для небольшого числа кандидатов в этой области, используя Context.

Практика

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

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

• Точность структурированных данных (Schema.org, GBP): Критически важно предоставлять четкие, точные и полные структурированные данные. Это гарантирует, что сущности и их атрибуты будут корректно обработаны и помещены в соответствующие структуры двухмерного индекса.
• Корректность локальных данных (Local SEO): Для локального бизнеса точность координат и адреса имеет решающее значение. Механизмы Proximity Queries полагаются на точное позиционирование сущности в Location Hierarchy. Ошибки в адресе могут привести к некорректному индексированию и потере видимости в запросах «рядом».
• Полнота данных для E-commerce: Убедитесь, что числовые атрибуты (цены, рейтинги, размеры, даты наличия) передаются корректно через фиды и микроразметку. Это позволяет системе правильно ранжировать их и включать в Bucket Posting Lists, обеспечивая видимость при использовании фильтров пользователями.
• Оптимизация сущностей (Entity Optimization): Работайте над тем, чтобы ваш бренд, продукты и ключевые персоны были четко определенными сущностями в Графе Знаний со множеством связей (предикатов). Это увеличивает вероятность их участия в предварительно вычисленных путях и улучшает извлечение данных.

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

• Предоставление противоречивых данных: Конфликтующая информация о сущности (например, разные адреса в GBP и на сайте, разные цены в разметке и на странице) может привести к некорректной индексации в специализированных структурах (например, неправильное определение Ancestor или Rank).
• Игнорирование структурированных данных: Полагаться только на текстовый контент означает игнорировать мощную инфраструктуру, описанную в патенте, и упускать возможности видимости в структурированных и локальных запросах.

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

Патент подтверждает, что Google рассматривает структурированные данные как отдельный, высоко оптимизированный корпус информации. Инфраструктура, описанная здесь, позволяет Google мгновенно отвечать на сложные, многофакторные запросы, такие как «лучшие рестораны итальянской кухни рядом со мной, открытые сейчас, с рейтингом 4+». Способность системы выполнять такие запросы с низкой задержкой основана на механизмах, описанных в этом патенте. Стратегия SEO должна учитывать, что извлечение на основе сущностей (Entity Retrieval) работает по иным принципам, нежели традиционный поиск по ключевым словам.

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

Сценарий: Оптимизация локального ресторана для Proximity Search

1. Действие: SEO-специалист обеспечивает абсолютную точность NAP (Name, Address, Phone) и географических координат в Google Business Profile, Schema.org на сайте и в ключевых каталогах.
2. Как это работает (по патенту): Система индексирования точно определяет местоположение ресторана (Basic Unit) и связывает его с соответствующими областями (Ancestors) в Location Hierarchy. Для ресторана генерируются Proximity Posting Lists (например, 1 км, 5 км, 10 км). Точное местоположение сохраняется как Context.
3. Ожидаемый результат: Когда пользователь ищет «ресторан рядом», система может мгновенно использовать Proximity Posting Lists и Distance Predicate для эффективного извлечения этого ресторана в качестве кандидата, минимизируя задержку ответа.

Сценарий: Оптимизация товара E-commerce для Range Queries

1. Действие: SEO-специалист гарантирует, что цена товара корректно и единообразно передается через Product Schema и фид Merchant Center.
2. Как это работает (по патенту): Система индексирования идентифицирует цену как Filterable Predicate, присваивает ей ранг (Object Rank) относительно других товаров и помещает товар в соответствующие Bucket Posting Lists (например, бакет $100-$150).
3. Ожидаемый результат: Когда пользователь применяет фильтр по цене (например, «до $140»), система быстро использует Bucket Posting Lists для извлечения этого товара, не сканируя весь индекс товаров.

Вопросы и ответы