Как Google оптимизирует инфраструктуру своего индекса для ускорения поиска подстрок и фраз

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

Range Query (Диапазонный запрос)

Запрос, требующий перечисления всех значений в определенном диапазоне. В контексте поиска: найти все позиции в документе (j), которые соответствуют диапазону позиций (i) в Suffix Array.

Suffix Array (Суффиксный массив)

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

Bitmap Binary Tree (Бинарное дерево с битовыми картами)

Стандартная структура данных для диапазонных запросов (иногда называется Wavelet Tree). Узлы содержат битовые карты (0 и 1), указывающие направление обхода (влево или вправо).

Hybrid Range Query Data Structure (Гибридная структура данных для диапазонных запросов)

Запатентованная структура. Верхние уровни — это Bitmap Binary Tree; нижние уровни (k) устранены и заменены листовыми узлами, хранящими фактические значения.

Bitrank Structure (Структура Bitrank)

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

Popcount (Population Count)

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

Node Offset (Смещение узла)

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

Depth-First Traversal (Обход в глубину)

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

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

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

1. Генерация бинарного дерева с битовыми картами (bitmap binary tree).
2. Во время генерации определяется, равно ли количество битов в следующем промежуточном узле заранее определенному числу (pre-specified number).
3. Если ДА, генерируются листовые узлы, хранящие фактические значения, вместо генерации дополнительных нижних уровней (тем самым устраняя их). У каждого листа есть смещение (node offset).
4. Структура сохраняется в памяти.
5. В ответ на диапазонный запрос система возвращает значения, вычисленные путем суммирования значений в листовых узлах и соответствующих node offsets.

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

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

Claim 5 (Зависимый от 4, который зависит от 1): Детализирует механизм быстрой сортировки.

1. При достижении листового узла.
2. Установка (маркировка) битов во временной битовой карте (bitmap), соответствующих найденным значениям.
3. Вывод результата (суммы) на основе позиций установленных битов (это и есть процесс сортировки).

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

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

INDEXING – Индексирование (Хранение данных)
На этом этапе создается Hybrid Range Query Data Structure для эффективного хранения отображения между Suffix Arrays и позициями в документах. Патент определяет, как индекс хранится для оптимизации скорости доступа и использования памяти.

RANKING – Ранжирование (L1 Retrieval / Отбор кандидатов)
Эта структура используется на этапе извлечения кандидатов, когда системе необходимо быстро найти документы, содержащие определенные фразы или подстроки. Она оптимизирует скорость этого поиска.

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

• Диапазон целочисленных значений (например, индексы Suffix Array).

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

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

Ключевые технические особенности:

• Устранение нижних уровней дерева (например, k=8) для сокращения глубины обхода и уменьшения cache misses.
• Использование Node Offsets для сжатия данных в листовых узлах.
• Высокоскоростная сортировка с использованием побитовых операций (XOR, AND, Popcount).

На что влияет

• Производительность поиска: Патент влияет на скорость поиска подстрок во всех типах контента, запросов и ниш, где используются Suffix Arrays. Это общее улучшение инфраструктуры, не зависящее от тематики или языка контента.

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

• Во время запроса (Retrieval): Всякий раз, когда поисковая система выполняет поиск подстроки или фразы, требующий определения позиций терминов в документах.
• Во время индексирования (Indexing): Структура строится, когда размер узлов при построении дерева достигает заранее определенного предела (зависит от параметра k).

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

Процесс А: Построение гибридной структуры (Индексирование)

1. Инициализация: Начать построение стандартного Bitmap Binary Tree для отображения данных.
2. Мониторинг размера узлов: Отслеживать размер создаваемых узлов на каждом уровне.
3. Прекращение расширения: Остановить построение дерева в глубину, когда достигнута заданная глубина или размер узла (определяется параметром k).
4. Генерация гибридных листьев: Заменить оставшиеся нижние уровни листовыми узлами, хранящими фактические значения. Эти значения сжимаются с использованием Node Offsets.

Процесс Б: Выполнение диапазонного запроса (Извлечение)

1. Получение запроса: Получить входной диапазон значений.
2. Обход верхних уровней: Начать Depth-First Traversal гибридного дерева, используя стандартные методы навигации (например, Bitrank).
3. Достижение листового узла: Прибыть в гибридный листовой узел.
4. Инициализация сортировки: Инициализировать временную битовую карту нулями (размер карты равен размеру узла, например, $2^k$ бит).
5. Маркировка значений: Для каждого релевантного значения в листовом узле установить соответствующий бит во временной битовой карте в единицу.
6. Эффективное извлечение (Быстрая сортировка): Извлечь позиции установленных битов в порядке возрастания с помощью побитовых операций:
   • Идентификация младшего значащего бита с помощью w XOR (w-1).
   • Подсчет позиции с помощью Popcount.
   • Сброс этого бита для следующей итерации с помощью w AND (w-1).
7. Расчет фактических значений: Добавить Node Offset к извлеченным позициям.
8. Вывод результатов: Вернуть значения и продолжить Depth-First Traversal.

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

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

Патент фокусируется на структуре данных, а не на внешних факторах ранжирования (контентных, ссылочных, поведенческих и т.д.).

• Данные для индексирования: Отображение целых чисел на целые числа (например, позиции в Suffix Array, отображаемые на позиции в документе).
• Данные во время запроса: Диапазон целых чисел.

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

Патент направлен на оптимизацию вычислительной сложности и минимизацию промахов кэша.

• k (Количество устраненных уровней): Заранее определенное число. В патенте упоминается k=8 как эффективная реализация.
• Размер листового узла: Определяется как $2^k$.
• Node Offset (Смещение узла): Используется для вычисления фактического значения по формуле: $v + (n*2^k)$, где v – значение в листовом узле, n – номер листового узла.
• Побитовые операции для сортировки: Использование XOR, AND и Popcount для оптимизации сортировки на уровне машинного слова (например, 64 бита), что повышает эффективность кэша процессора.

Патент описывает внутренние процессы Google, связанные с оптимизацией инфраструктуры, без прямых рекомендаций для SEO.

1. Инфраструктурная оптимизация: Это чисто технический патент, сфокусированный на повышении производительности доступа к данным. Он описывает, как Google ускоряет фундаментальный процесс извлечения данных из индекса (в частности, поиск подстрок через Suffix Arrays).
2. Гибридный подход к данным: Основная инновация заключается в сочетании эффективности бинарных деревьев на верхних уровнях со скоростью таблиц прямого поиска на нижних уровнях. Это позволяет избежать медленного обхода глубоких деревьев.
3. Оптимизация на уровне CPU: Патент демонстрирует использование сложных низкоуровневых методов (побитовых операций) для чрезвычайно быстрой сортировки небольших наборов данных, оптимизированных под кэш процессора.
4. Отсутствие SEO-значимости: Патент описывает, как Google быстрее извлекает информацию, а не какая информация считается важной или почему один результат ранжируется выше другого. Прямых последствий для SEO нет.

ВАЖНО: Этот патент ориентирован на инфраструктуру и не предоставляет прямых практических рекомендаций для SEO-стратегий, направленных на улучшение ранжирования.

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

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

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

• Патент не направлен против каких-либо конкретных SEO-манипуляций или тактик.

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

Патент дает представление о сложности инфраструктуры Google и о том, какое внимание уделяется скорости и эффективности на фундаментальном уровне. Он подтверждает использование Suffix Arrays для индексирования текста. Однако он не меняет понимание приоритетов Google в отношении качества контента (E-E-A-T) или факторов ранжирования и не влияет на долгосрочную SEO-стратегию.

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

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