Как Google эффективно вычисляет совместную встречаемость (co-occurrence) терминов в больших наборах структурированных данных с помощью HyperLogLog

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

HyperLogLog (HLL)

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

HLL Sketch (Скетч HyperLogLog)

Компактная структура данных фиксированного размера, генерируемая алгоритмом HLL. Она хранит аппроксимацию множества и позволяет оценить его кардинальность. Скетчи можно объединять (Merge).

Cardinality (Кардинальность)

Количество уникальных элементов в наборе данных.

Overlap (Пересечение)

Степень, в которой два набора данных содержат общие элементы. В контексте патента — как часто два термина встречаются вместе (co-occurrence).

Search Term (Поисковый термин)

Элемент данных в индексе. В контексте патента это категоризированный термин, состоящий из Search Value (значение) и Search Field (поле/категория). Например, значение "Phoenix" и поле "flight_origin".

Second Level Searching (Поиск второго уровня)

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

Weighted Search Index (Взвешенный поисковый индекс)

Индекс, в котором термины ассоциированы с весом (Search Weight), который представляет собой количество уникальных элементов, рассчитанное с помощью HLL.

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

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

1. Система получает первый поисковый термин.
2. Система получает доступ к первому HyperLogLog Sketch первого термина и второму HyperLogLog Sketch второго термина.
3. Система определяет степень пересечения (degree of overlap) между первым и вторым терминами на основе этих двух скетчей.
4. Определение степени пересечения включает объединение (merging) скетчей и определение третьего подсчета (third count) уникальных элементов на основе объединенного скетча.

Claim 4 (Зависимый от 1 и 2): Уточняет механизм определения степени пересечения (реализация принципа включения-исключения).

Степень пересечения рассчитывается как разница между (i) суммой первой и второй оценок (Count 1 + Count 2) и (ii) третьей оценкой (Count 3, полученной из объединенного скетча).

Это математически выражается как: $Count(A \cap B) \approx Count(A) + Count(B) - Count(A \cup B)$. Ключевая особенность HLL, используемая здесь, — это возможность объединять скетчи для оценки $Count(A \cup B)$.

Claims 5-7 (Зависимые): Описывают применение рассчитанного пересечения.

1. Второму термину присваивается значение корреляции (correlation value) на основе степени пересечения.
2. Процесс повторяется для множества дополнительных терминов.
3. Результаты поиска организуются в соответствии со значениями корреляции для приоритизации терминов с более высокими значениями.

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

Этот патент является инфраструктурным и относится к технологиям баз данных и аналитики (Business Intelligence), а не напрямую к архитектуре веб-поиска Google Search.

INDEXING – Индексирование (Обработка данных)
На этом этапе система обрабатывает данные из различных источников (например, таблиц баз данных). Она идентифицирует поисковые термины (Search Terms) в структурированных данных и вычисляет HLL Sketch для каждого термина. Создается Weighted Search Index, хранящий термины и их скетчи.

RANKING / RERANKING (в контексте BI/Data Analytics)
При получении запроса в аналитической системе она может выполнять:

• First Level Searching: Поиск терминов, соответствующих запросу, и их сортировка по весу (частоте).
• Second Level Searching: Ключевое применение патента. Для заданного термина система итеративно рассчитывает корреляцию со всеми остальными терминами в индексе, используя механизм HLL-пересечений.

Важное замечание: Патент не описывает применение этого механизма в контексте ранжирования неструктурированных веб-документов (Google Search). Примеры, приведенные в патенте, относятся исключительно к анализу структурированных наборов данных (данные об авиарейсах, база данных IMDB).

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

• Эффективность по времени: Обработка данных HLL (подсчет или объединение) для пары терминов выполняется за время $\Theta(1)$ (константное время), независимо от объема данных.
• Эффективность по памяти: Требования к хранению HLL Sketches фиксированы и не растут с увеличением объема анализируемых данных.

На что влияет

• Типы данных: Влияет на системы анализа структурированных данных, Business Intelligence (BI) платформы и аналитические базы данных. Позволяет быстро находить взаимосвязи (co-occurrence) между различными измерениями (dimensions) в данных.
• SEO Контекст: Патент не содержит информации о влиянии на конкретные типы контента веб-поиска (статьи, товары), специфические типы запросов, ниши (например, YMYL) или языковые/географические ограничения в контексте SEO.

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

• Условия применения: Алгоритм применяется при обработке запроса к базе данных или аналитической системе, которая имплементирует этот механизм.
• Триггеры активации: Активируется для выполнения Second Level Searching — когда необходимо найти и ранжировать термины по степени их корреляции с заданным термином в аналитическом интерфейсе.

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

Процесс: Second Level Searching (Поиск корреляций)

1. Получение запроса: Система получает запрос, включающий первый поисковый термин (Термин А).
2. Выбор кандидата: Из поискового индекса выбирается кандидат — второй поисковый термин (Термин Б).
3. Доступ к скетчам: Извлекаются HLL Sketch для Термина А и HLL Sketch для Термина Б.
4. Расчет индивидуальных оценок: Оценивается кардинальность для каждого термина (Count A, Count B).
5. Объединение скетчей (Merge): Скетчи А и Б объединяются. Это достигается путем сравнения соответствующих бакетов (buckets) в обоих скетчах и выбора максимального значения для каждого бакета в новом объединенном скетче.
6. Расчет объединенной оценки: Оценивается кардинальность объединенного набора (Count Union).
7. Расчет пересечения (Overlap): Вычисляется степень пересечения по формуле: (Count A + Count B) - Count Union.
8. Назначение корреляции: Паре терминов (А, Б) присваивается Correlation Value на основе рассчитанного пересечения.
9. Итерация: Система проверяет, все ли кандидаты были оценены. Если нет, возвращается к шагу 2 для следующего термина.
10. Организация результатов: После завершения итераций система организует (сортирует) список терминов-кандидатов на основе их Correlation Values для приоритизации наиболее связанных терминов.

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

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

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

• Системные данные: HyperLogLog Sketches для каждого индексированного термина. Это ключевые данные, позволяющие проводить вычисления.
• Структурные данные (в индексе): Search Value (значение термина) и Search Field (категория или поле термина), которые вместе формируют категоризированный поисковый термин в структурированной базе данных.

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

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

• Cardinality Estimation (Оценка кардинальности): Количество уникальных элементов для термина. Рассчитывается на основе его HLL Sketch.
• Overlap (Пересечение / Intersection): Количество уникальных элементов, общих для двух терминов (А и Б). Рассчитывается с использованием принципа включения-исключения: $Count(A \cap B) \approx Count(A) + Count(B) - Count(A \cup B)$.
• Correlation Value (Значение корреляции): Метрика, присваиваемая паре терминов на основе их Overlap. Может быть как самим значением Overlap, так и нормализованным показателем.

1. Инфраструктурное решение, не алгоритм SEO: Патент описывает высокоэффективное инфраструктурное решение для Data Analytics и Business Intelligence (BI). Он не является патентом на алгоритм ранжирования Google Search.
2. Эффективность вычислений: Ключевая инновация заключается в применении HyperLogLog для расчета корреляций (совместной встречаемости). Это позволяет анализировать огромные наборы данных с фиксированными и минимальными затратами памяти (HLL Sketches имеют фиксированный размер независимо от объема данных).
3. Скорость обработки: Определение корреляции между двумя любыми терминами выполняется за постоянное время O(1), так как требует только обработки двух компактных скетчей. Полный анализ корреляций одного термина со всеми остальными (N) выполняется за линейное время O(N).
4. Фокус на структурированных данных: Примеры в патенте (авиарейсы, IMDB) и контекст изобретения (Looker) указывают на применение в средах со структурированными (табличными) данными, а не в поиске по неструктурированным веб-документам.
5. Отсутствие практической ценности для SEO: Практических выводов для SEO-специалистов, работающих над продвижением сайтов в органическом поиске Google Search, этот патент не дает. Он не описывает факторы ранжирования, методы оценки качества контента или сигналы релевантности для веб-документов.

ВАЖНО: Патент является инфраструктурным и ориентирован на анализ структурированных данных (Data Analytics/BI). Он не дает практических рекомендаций для SEO в контексте ранжирования Google Search.

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

Патент не содержит информации для формирования Best Practices в SEO.

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

Патент не содержит информации для формирования Worst Practices в SEO.

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

Стратегическое значение для SEO минимально. Патент демонстрирует компетенции Google в области эффективной обработки больших данных и разработки аналитических инструментов (что подтверждается связью с платформой Looker). Для Senior SEO-специалистов важно уметь отличать патенты на инфраструктуру баз данных и BI от патентов, описывающих алгоритмы веб-поиска, и не строить SEO-стратегии на основе инфраструктурных решений, не относящихся к их области.

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

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

Например, при анализе базы данных авиарейсов в BI-инструменте по запросу "destination.city: SACRAMENTO" система может использовать этот механизм, чтобы мгновенно определить, что этот термин имеет 100% пересечение с термином "destination.state: CA" и высокое пересечение с термином "aircraft_models.manufacturer: BOEING". Это аналитические инсайты, а не факторы ранжирования веб-поиска.