Как Google использует фильтры Блума для эффективного отслеживания истории кликов пользователя и персонализации отображения SERP

Описание

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

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

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

Запатентовано использование общего или многопользовательского фильтра Блума (Shared Bloom Filter / Multi-user Bloom Filter) для компактного хранения истории доступа к контенту для группы пользователей. Фильтр Блума — это вероятностная структура данных, позволяющая эффективно проверять принадлежность элемента к множеству. Ключевым элементом является использование комбинации идентификатора пользователя (UserID) и идентификатора контента (ContentID) в качестве ключа для фильтра.

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

Система работает в двух основных режимах:

• Запись (Write/Update): Когда пользователь посещает контент, система комбинирует его UserID и ContentID посещенного ресурса, хеширует эту комбинацию и обновляет массив фильтра Блума (устанавливает соответствующие биты в 1).
• Чтение (Read/Check): Когда пользователь выполняет новый поиск, система проверяет каждый результат. Для этого она снова комбинирует UserID и ContentID результата, хеширует и проверяет соответствующие биты в массиве фильтра.
• Персонализация SERP: Если фильтр Блума указывает, что результат уже был посещен (все биты равны 1), система модифицирует выдачу. Это может включать визуальное выделение посещенных ссылок или их исключение из результатов.

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

Высокая (с точки зрения инфраструктуры). Эффективные структуры данных критически важны для работы крупномасштабных систем. Персонализация пользовательского опыта (UX) и отслеживание истории взаимодействия (например, отметки «Просмотрено» на YouTube) остаются важными аспектами поиска и требуют эффективных бэкенд-решений, подобных описанному.

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

Влияние на SEO минимальное (Инфраструктура). Патент не описывает алгоритмы ранжирования или оценки качества контента. Он описывает инфраструктуру для персонализации представления (presentation) уже сформированной поисковой выдачи конкретному пользователю на основе его истории. Это влияет на пользовательский опыт и может влиять на CTR и повторные клики, но не на изначальное ранжирование документа.

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

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

Bloom Filter (Фильтр Блума)

Компактная вероятностная структура данных, используемая для проверки принадлежности элемента к множеству. Состоит из массива битов и набора хеш-функций. Допускает ложноположительные срабатывания (False Positives), но не допускает ложноотрицательных (False Negatives).

Bloom Filter Array (Массив фильтра Блума)

Битовый вектор (массив), в котором хранятся данные фильтра Блума. Изначально заполнен нулями.

ContentID (Идентификатор контента)

Уникальный идентификатор результата поиска или элемента контента (например, URL, внутренний DocID или ID видеофайла).

False Positive (Ложноположительное срабатывание)

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

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

Набор функций, используемых фильтром Блума. Каждая функция преобразует входные данные (например, UserID+ContentID) в адрес (позицию) в массиве фильтра Блума.

Multi-user Bloom Filter / Shared Bloom Filter (Многопользовательский / Общий фильтр Блума)

Реализация фильтра Блума, которая хранит историю доступа для множества пользователей одновременно, используя UserID как часть входных данных для хеш-функций.

Partitioned Bloom Filter (Партиционированный фильтр Блума)

Метод масштабирования, при котором общий фильтр Блума разделен на несколько независимых частей (партиций). Каждый пользователь привязывается к определенной партиции (например, с помощью функции Modulo N от UserID).

Transaction Log (Журнал транзакций)

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

UserID (Идентификатор пользователя)

Уникальный идентификатор пользователя или сессии, чья история отслеживается.

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

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

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

1. Система получает список результатов в ответ на запрос пользователя.
2. Применяется многопользовательский фильтр Блума (multi-user Bloom filter) для идентификации результатов, которые этот пользователь ранее посещал.
3. Ключевой аспект: применение фильтра включает использование набора хеш-функций к значению, которое содержит одновременно идентификатор пользователя (user identifier) и идентификатор контента (content identifier) результата. Это позволяет использовать один фильтр для многих пользователей.
4. На основе этой идентификации генерируется итоговый список результатов.
5. Список отправляется клиенту.

Claim 4 (Зависимый от 1): Уточняет способ генерации итогового списка.

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

Claim 5 (Зависимый от 1): Уточняет альтернативный способ генерации итогового списка.

Генерация исключает (excludes) из итогового списка результаты, которые пользователь ранее посещал.

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

1. Система получает запросы от множества клиентов на доступ к элементам контента и отправляет их.
2. Фильтр Блума, связанный с этими клиентами, обновляется.
3. Обновление включает хеширование значения, которое является комбинацией идентификатора элемента (item identifier) и идентификатора пользователя (user identifier).

Claim 20 (Зависимый от 14): Описывает механизм обслуживания фильтра.

Система поддерживает набор записей (set of records / Журнал транзакций). При наступлении предопределенного события (например, когда фильтр заполнен) текущий фильтр Блума заменяется новым фильтром Блума, сгенерированным из подмножества этих записей (например, недавней истории).

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

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

RANKING – Ранжирование
На этом этапе генерируется стандартный (неперсонализированный) список результатов, отсортированный по релевантности и качеству.

RERANKING – Переранжирование (Слой Персонализации UX) / METASEARCH – Метапоиск и Смешивание
Основное применение патента происходит здесь. Система принимает список результатов с этапа RANKING и применяет к нему фильтр Блума для модификации SERP.

1. Проверка истории: Для каждого результата в списке система формирует ключ (UserID + ContentID) и проверяет его наличие в Shared Bloom Filter.
2. Модификация SERP: В зависимости от результата проверки система применяет логику персонализации: добавляет специальное форматирование или полностью удаляет результат из списка.

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

• Идентификатор пользователя (UserID).
• Список результатов поиска с их идентификаторами (ContentID).
• Общий фильтр Блума (Shared Bloom Filter).

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

• Модифицированный список результатов поиска (с измененным форматированием или составом).

Фоновые процессы:

• Обновление фильтра: Когда пользователь кликает по ссылке, система асинхронно обновляет фильтр Блума и записывает событие в Transaction Log.
• Обслуживание фильтра: Периодическая проверка заполненности фильтра и его замена новым фильтром на основе данных из Transaction Log.

На что влияет

Патент не влияет на ранжирование контента, но влияет на его представление пользователю (UX).

• Конкретные типы контента: Применяется к любым результатам поиска, которые имеют уникальный ContentID. В патенте явно упоминаются мультимедийные файлы (multimedia files), что указывает на возможное применение в YouTube или Google Видео.
• Пользовательские факторы: Влияет только на пользователей, для которых система может определить UserID (например, залогиненные пользователи или пользователи с установленными cookie/session ID) и чья история сохраняется.

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

• Триггеры активации (Чтение): Применяется в реальном времени при генерации страницы результатов поиска (SERP) для идентифицированного пользователя.
• Триггеры активации (Запись): Происходит, когда пользователь запрашивает контент (кликает на результат).
• Обслуживание: Активируется, когда фильтр Блума достигает предопределенного порога заполненности (predefined limit), что приводит к превышению допустимого уровня ложноположительных срабатываний (false positive rate), или по истечении заданного периода времени.

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

Процесс А: Генерация персонализированной SERP (Read)

1. Получение запроса и результатов: Сервер получает запрос и UserID, затем генерирует стандартный список результатов (ContentID).
2. Определение фильтра (Опционально): Если используется партиционирование, система определяет партицию фильтра Блума для данного UserID (например, с помощью функции Modulo N).
3. Применение фильтра Блума: Для каждого результата в списке:
   1. Формируется входное значение путем объединения (конкатенации) UserID и ContentID.
   2. К этому значению применяется набор (L) хеш-функций для получения L позиций в массиве фильтра.
   3. Проверяются значения битов на этих L позициях.
   4. Если все биты равны 1, результат помечается как «вероятно посещенный». Если хотя бы один бит равен 0, результат помечается как «не посещенный».
4. Генерация итогового списка: Система модифицирует список на основе результатов фильтрации:
   1. (Вариант 1 — Claim 4): К посещенным результатам добавляется информация для отличительного форматирования.
   2. (Вариант 2 — Claim 5): Посещенные результаты исключаются из списка.
5. Отправка SERP: Итоговый список отправляется клиенту.

Процесс Б: Обновление истории доступа (Write)

1. Фиксация доступа: Пользователь обращается к элементу контента. Сервер отправляет контент.
2. Подготовка данных: Система формирует входное значение (UserID + ContentID).
3. Хеширование: Применяется набор (L) хеш-функций для получения L позиций в массиве.
4. Обновление фильтра: На всех этих L позициях в массиве фильтра Блума устанавливается значение 1.
5. Запись в журнал: Событие доступа записывается в Transaction Log.

Процесс В: Обслуживание фильтра (Замена)

1. Мониторинг: Система отслеживает количество записей (N) или прогнозируемый False Positive Rate.
2. Триггер замены: При достижении порога (фильтр «полный»).
3. Генерация нового фильтра: Новый фильтр заполняется актуальными данными из Transaction Log за последний период (например, 60 дней).
4. Активация: Новый фильтр активируется вместо старого.

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

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

Патент фокусируется на инфраструктуре и использует минимальный набор данных для работы фильтра:

• Пользовательские факторы: UserID (Идентификатор пользователя). Используется для идентификации пользователя, чья история проверяется или обновляется.
• Технические факторы (Идентификаторы контента): ContentID (Идентификатор контента). Используется для уникальной идентификации результата поиска или файла.
• Системные данные: Transaction Log (Журнал транзакций). Используется для обслуживания фильтра.

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

Патент описывает метрики, связанные с конфигурацией и производительностью фильтра Блума, а не с ранжированием.

• Конфигурация фильтра:
  • k (или L) (Количество хеш-функций): Определяет, сколько битов устанавливается или проверяется для одного элемента.
  • m (Размер массива фильтра): Общее количество битов в массиве (например, 128 Гигабит / 16 Гигабайт).
  • n (Количество сохраненных элементов): Общее количество событий доступа (UserID + ContentID), сохраненных в фильтре. Отслеживается с помощью Filter Fullness Counter.
• False Positive Rate (Уровень ложноположительных срабатываний): Вероятность того, что фильтр ошибочно укажет на посещение контента. Приблизительная формула, указанная в патенте: (1-e^(-kn/m))^k. Система проектируется так, чтобы поддерживать этот показатель ниже заданного порога (например, 1% или 2%).
• Порог заполненности (Fullness Threshold): Предопределенное максимальное значение n, при котором False Positive Rate остается ниже заданного лимита. При достижении этого порога фильтр требует замены. В примере патента порог составляет около 12 миллиардов записей для 16 ГБ фильтра.

Выводы

1. Инфраструктура, а не ранжирование: Это инфраструктурный патент, направленный на обеспечение масштабируемости и эффективности хранения данных персонализации. Он не описывает алгоритмы ранжирования.
2. Эффективность и масштабируемость: Основная цель — обеспечить возможность быстрого и экономичного по памяти отслеживания истории посещений для огромного числа пользователей. Упоминается пример использования 16 ГБ памяти для хранения 12 миллиардов записей.
3. Механизм персонализации UX: Патент четко определяет варианты использования этой информации на уровне представления: визуальное выделение посещенных результатов или их полное исключение из выдачи. Это влияет на вид SERP для конкретного пользователя.
4. Компромисс между точностью и ресурсами: Использование фильтра Блума указывает на готовность Google жертвовать абсолютной точностью ради производительности. Система допускает наличие ложноположительных срабатываний (False Positives), но гарантирует отсутствие ложноотрицательных (False Negatives).
5. Инновация в совместном использовании (Multi-User): Ключевая техника — использование комбинации UserID+ContentID в качестве входных данных. Это позволяет использовать одну структуру данных для множества пользователей.

Практика

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

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

Хотя патент не влияет на ранжирование, его понимание важно для корректной интерпретации SERP и анализа поведения пользователей.

• Использование режима «Инкогнито» для анализа SERP: Поскольку описанный механизм может визуально изменять или скрывать результаты, которые вы уже посещали, для объективного анализа поисковой выдачи и отслеживания позиций необходимо использовать чистый браузерный профиль или режим «Инкогнито». Это позволяет увидеть ранжирование без наложения слоя персонализации истории кликов.
• Учет влияния UX на поведение в SERP и CTR: Механизм может влиять на поведение пользователя в выдаче. Если результат помечен как просмотренный, это может снизить вероятность повторного клика (если пользователь ищет новое) или повысить ее (если он ищет знакомый ресурс). Это следует учитывать при анализе CTR.
• Фокус на привлекательности сниппетов для первого клика: Так как история кликов отслеживается и может влиять на представление результата при повторных запросах (например, результат может быть скрыт), критически важно добиться первого клика пользователя.

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

• Оценка позиций сайта по персонализированной выдаче: Ошибочно делать выводы о ранжировании сайта, основываясь на результатах поиска, где активирован данный механизм. Вы можете не увидеть свой сайт в топе, если система решила скрыть его как «уже посещенный», или увидеть искаженное представление SERP.
• Попытки манипулировать фильтром Блума: Это внутренний механизм хранения данных. Не существует SEO-тактик для манипулирования историей посещений пользователей в масштабах, влияющих на ранжирование.

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

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

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

Сценарий 1: Проверка позиций сайта SEO-специалистом

1. Ситуация: SEO-специалист активно исследует нишу, часто вводит одни и те же запросы и кликает на сайты конкурентов и свой сайт.
2. Действие механизма: Система отслеживает его клики через UserID и обновляет фильтр Блума.
3. Результат (Вариант Исключения): Если в настройках поиска активирована фильтрация посещенных результатов (или Google тестирует этот режим), система использует данные фильтра Блума, чтобы полностью убрать из SERP сайты, которые специалист недавно посещал.
4. Вывод для SEO: Специалист может ошибочно решить, что сайт выпал из выдачи. Для корректного анализа необходимо использовать режим «Инкогнито».

Сценарий 2: Пометка «Просмотрено» на YouTube (вероятное применение)

1. Действие пользователя: Пользователь (UserID 123) смотрит видео (ContentID ABC).
2. Обновление фильтра: Система объединяет 123+ABC, хеширует и обновляет общий фильтр Блума.
3. Повторный поиск: На следующий день пользователь ищет похожую тему. Видео ABC попадает в результаты.
4. Проверка фильтра: Система быстро проверяет 123+ABC в фильтре Блума. Фильтр возвращает положительный результат.
5. Результат (UX): Система модифицирует выдачу и показывает видео ABC с тегом «Просмотрено». Фильтр Блума позволяет выполнить эту проверку быстро и масштабно.

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