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

Описание

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

Патент решает фундаментальную инфраструктурную проблему: как быстро и эффективно оценить количество уникальных (distinct) результатов поиска в масштабе интернета. Точный подсчет уникальных элементов в огромных распределенных системах требует значительных вычислительных ресурсов (памяти, времени, сетевого трафика). Это критично для отображения общего числа результатов («Найдено примерно X результатов») и для реализации Faceted Search (фасетного поиска), где нужно быстро подсчитать результаты для гистограмм (например, количество товаров в ценовом диапазоне).

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

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

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

Механизм работает следующим образом:

• Хеширование: Информация из каждого результата (например, URL или контент) преобразуется в случайное число с помощью хеш-функции.
• Отслеживание минимумов (Скетчинг): Система хранит только предопределенное количество (K) наименьших уникальных хеш-значений (Smallest Hash Values).
• Оценка: Общее количество уникальных результатов оценивается по формуле, основанной на значении K-го наименьшего хеша. Идея в том, что плотность наименьших значений коррелирует с общим количеством элементов.
• Распределенный подсчет: Процесс выполняется параллельно на Index Servers, которые генерируют локальные наборы минимумов. Центральный Search Server объединяет эти наборы и выполняет финальную оценку.
• Повышение точности: Для повышения надежности (Confidence) процесс может повторяться с несколькими хеш-функциями, а результаты усредняться (например, медианой).

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

Высокая (с инженерной точки зрения). Вероятностные алгоритмы для оценки количества уникальных элементов (Cardinality Estimation) являются стандартом в индустрии больших данных. Хотя конкретный алгоритм KMV, описанный здесь, мог быть заменен более современными (например, HyperLogLog), базовые принципы, изложенные в патенте (вероятностный подсчет, распределенная агрегация скетчей), остаются крайне актуальными для инфраструктуры Google.

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

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

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

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

Bucket (Бакет/Сегмент)

Категория внутри фасета в Faceted Search. Например, ценовой диапазон «$100-$200» является бакетом в фасете «Цена».

Confidence (Достоверность)

Вероятность того, что погрешность оценки находится в пределах заданного значения Error. Определяет необходимое количество используемых хеш-функций.

Error (Погрешность)

Допустимое отклонение оценки от фактического числа уникальных результатов. Определяет значение K (Predetermined Number).

Faceted Search (Фасетный поиск)

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

Hash Function (Хеш-функция)

Функция, преобразующая входные данные (например, URL) в псевдослучайное число фиксированной длины.

Hash Value Range Size (R) (Размер диапазона значений хеша)

Общее количество возможных выходных значений хеш-функции (например, 2^64).

Index Server (Индексный сервер)

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

Predetermined Number (K) (Предопределенное число K)

Количество наименьших уникальных хеш-значений, которые система отслеживает. Определяется на основе желаемой погрешности (Error).

Search Server (Поисковый сервер)

Центральный сервер, который распределяет запрос, объединяет скетчи от Index Servers и выполняет финальную оценку.

Smallest Hash Values (Наименьшие значения хеша)

Набор из K самых маленьких уникальных хеш-значений. Является статистическим скетчем данных.

V_k (Largest Hash Value in the Smallest Hash Values)

Наибольшее значение среди K наименьших хеш-значений. Ключевой параметр для формулы оценки.

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

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

1. Создание хеш-значений для уникальных результатов поиска с использованием первой хеш-функции с определенным Hash Value Range Size (R).
2. Получение информации о количестве наименьших хеш-значений (K), которые необходимо выбрать, исходя из допустимой погрешности (margin of error).
3. Идентификация K наименьших хеш-значений.
4. Генерация первой оценки количества уникальных результатов на основе (i) R, (ii) K и (iii) наибольшего значения среди K наименьших хешей (V_k).
5. Генерация второй оценки с использованием второй хеш-функции.
6. Определение среднего количества уникальных результатов на основе первой и второй оценок.

Claim 2 (Зависимый от 1): Уточняет формулу оценки.

Генерация оценки включает умножение Hash Value Range Size (R) на K и деление на наибольшее значение среди K наименьших хешей (V_k). Формула оценки: E ≈ (R * K) / V_k.

Claim 7 (Зависимый от 1): Описывает применение к фасетному поиску.

Если результаты поиска включают фасеты, связанные с Buckets, то метод (хеширование, идентификация K наименьших, оценка) выполняется для каждого Bucket в гистограмме фасета.

Claim 8 (Зависимый от 1): Уточняет метод усреднения.

Среднее количество может быть определено как медиана (median) полученных оценок.

Claim 10, 11 (Зависимые от 1): Описывают работу в распределенной системе.

Создание хешей и идентификация K наименьших значений выполняются раздельно на нескольких устройствах (Index Servers) (Claim 10). Система объединяет (merging) эти раздельно идентифицированные наборы и идентифицирует глобальные K наименьших значений из объединенного набора (Claim 11).

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

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

INDEXING – Индексирование и извлечение признаков
В патенте упоминается возможность предварительного вычисления хеш-значений и их хранения в индексе для оптимизации скорости.

RANKING / METASEARCH – Ранжирование / Метапоиск и Смешивание
Это основная область применения. После того как система идентифицировала набор результатов для запроса, описанный механизм активируется для оценки их количества.

В распределенной архитектуре процесс запускается параллельно на Index Servers. Они выполняют локальный подсчет (генерацию скетчей) и передают данные на Search Server. Search Server выполняет слияние скетчей и финальную оценку перед формированием SERP.

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

• Набор результатов поиска (идентификаторы, URL или контент).
• Хеш-функция(и) и их Hash Value Range Size (R).
• Predetermined Number (K).

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

• Оценка общего количества уникальных результатов поиска или оценки для Buckets в фасетном поиске.

На что влияет

• Отображение SERP: Влияет на число, отображаемое как «Примерное количество результатов» (Estimated number of results).
• Фасетная навигация (Faceted Search): Влияет на счетчики в фильтрах и гистограммах (например, в Google Shopping, поиске картинок).
• Ранжирование: Патент не описывает никакого влияния на ранжирование документов.

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

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

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

Описание процесса в распределенной среде.

Этап 1: Инициализация и Распределение

1. Получение запроса: Search Server получает запрос.
2. Определение параметров: Система определяет K (на основе Error) и количество хеш-функций (на основе Confidence).
3. Распределение запроса: Search Server отправляет запрос и параметры на Index Servers.

Этап 2: Параллельная обработка на Index Servers (Генерация Скетчей)

4. Поиск результатов: Каждый Index Server выполняет поиск локально.
5. Хеширование: Для каждого результата вычисляется хеш-значение (если не было предвычислено).
6. Идентификация локальных K наименьших хешей: Каждый сервер поддерживает список (скетч) из K самых маленьких уникальных хеш-значений, найденных локально.
7. Передача данных: Index Servers отправляют свои локальные скетчи на Search Server.

Этап 3: Агрегация и Оценка на Search Server

8. Слияние скетчей (Merging): Search Server объединяет все полученные локальные скетчи.
9. Идентификация глобальных K наименьших хешей: Из объединенного набора выбираются глобальные K наименьших уникальных значений. Определяется глобальное V_k.
10. Расчет оценки: Если найдено ≥ K уникальных значений, система рассчитывает оценку по формуле: E ≈ (R * K) / V_k. (В патенте также упоминается вычитание 1 в Pseudo-Code 2).
11. Усреднение (Опционально): Если использовалось несколько хеш-функций, шаги 4-10 повторяются для каждой, и полученные оценки усредняются (например, вычисляется медиана).
12. Предоставление результатов: Search Server формирует SERP, включая рассчитанную оценку.

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

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

Патент фокусируется на статистическом методе подсчета.

• Контентные и Идентификационные факторы: Система использует информацию из результатов поиска для генерации хешей, чтобы определить уникальность. В патенте явно упоминаются:
  • web page addresses (URL, доменные имена, IP-адреса).
  • web page content (HTML код из head, meta, body).
  • web page advertisements (HTML код рекламы или метаданные).

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

Система использует ключевые статистические метрики для контроля точности и достоверности:

• Predetermined Number (K): Определяется желаемой погрешностью (Error). Упоминается формула: K = 1 / Error^2. (Например, для погрешности 10%, K = 100).
• Hash Value Range Size (R): Может быть фиксированным (например, 2^64) или определяться как квадрат ожидаемого числа уникальных результатов ((Expected Number of Unique Items)^2).
• Number of Hash Functions: Определяется желаемой достоверностью (Confidence). Упоминается формула: Number Of Hash Functions ≈ ln(1 / Confidence).
• Формула Оценки (E): Основная формула оценки: E ≈ (R * K) / V_k.

Выводы

1. Инфраструктурный патент, не связанный с ранжированием: Патент описывает исключительно инфраструктурное решение для повышения вычислительной эффективности. Он не содержит информации о факторах ранжирования или оценке качества контента.
2. Приоритет скорости над абсолютной точностью: Google использует вероятностные методы (Probabilistic Counting Algorithms) для быстрой оценки количества результатов. Это означает, что числа в SERP или фасетной навигации являются приблизительными, рассчитанными с контролируемой погрешностью.
3. Оптимизация для распределенных систем: Ключевой особенностью является механизм распределенного подсчета (MapReduce-подобный подход). Index Servers выполняют основную работу, а Search Server агрегирует небольшие наборы данных (скетчи), минимизируя сетевой трафик.
4. Критичность для Фасетного Поиска: Метод явно предназначен для быстрого подсчета уникальных элементов в сегментах (Buckets) фасетной навигации, что важно для E-commerce.
5. Отсутствие практической ценности для SEO: Для SEO-специалистов этот патент не несет практической ценности с точки зрения оптимизации сайтов или улучшения их позиций в выдаче.

Практика

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

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

Не применимо. Патент не предлагает действий, которые могут повлиять на SEO-продвижение.

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

Не применимо. Патент не направлен против каких-либо SEO-тактик и не описывает механизмов пессимизации.

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

Стратегическое значение для SEO минимально. Патент подтверждает использование Google продвинутых алгоритмических методов (Computer Science) для решения задач масштабирования. Единственный полезный вывод — понимание того, что «Примерное количество результатов» в SERP является статистической оценкой, а не точным числом.

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

Практических примеров применения данного патента в SEO-работе нет.

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