Как Google оптимизирует хранение и скорость поиска в больших индексах с помощью субсемплирования (LSH)

Описание

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

Патент решает фундаментальную проблему эффективности в системах Information Retrieval (IR) — перегрузку при обработке часто встречающихся признаков (keys). В больших массивах данных (видео, документы) некоторые элементы встречаются очень часто (например, стандартные заставки в видео или общие слова в тексте). При индексации (например, с помощью Locality Sensitive Hashing) ссылки на эти элементы заполняют соответствующие сегменты индекса (bins). Доступ к переполненным сегментам требует значительных ресурсов (память, процессор, пропускная способность сети). Традиционное решение — игнорирование (blacklisting) таких признаков — приводит к потере информации и снижению точности поиска. Патент предлагает механизм сохранения эффективности без полной потери данных.

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

Запатентована система индексации и доступа к данным, которая динамически управляет размером сегментов индекса (bins) с помощью субсемплирования (sub-sampling). Когда количество идентификаторов (reference identifiers), ссылающихся на контент с определенным признаком (key), превышает заданный порог, система не игнорирует этот признак, а пропорционально сокращает количество сохраняемых идентификаторов, используя коэффициент субсемплирования (sub-sampling factor).

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

Система работает на этапах индексации и/или доступа к данным. Контент (например, видео) преобразуется в фингерпринты (fingerprints), которые делятся на ключи (keys). Эти ключи используются для размещения идентификаторов в индекс (Reference Index). Если соответствующий сегмент (bin) переполняется, активируется модуль субсемплирования (Sub-sampling module). Ключевым аспектом является использование «коррелированного субсемплирования» (correlated sub-sampling): решение о сохранении или удалении идентификатора принимается на основе самого идентификатора, а не сегмента. Это гарантирует, что если идентификатор сохранен в одном сегменте, он будет сохранен и в других, что критично для поиска совпадений по нескольким признакам.

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

Высокая (в контексте инфраструктуры). Эффективное управление огромными индексами является критически важной задачей для любой поисковой системы масштаба Google. Методы хеширования (LSH) и оптимизация хранения и доступа к данным остаются фундаментальными аспектами работы поиска.

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

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

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

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

Bin (Сегмент индекса, Бин)

Структура данных в Reference Index, связанная с определенным ключом (Key). Хранит Reference Identifiers, указывающие на контент, который содержит этот ключ.

Correlated Sub-sampling (Коррелированное субсемплирование)

Метод сокращения данных, при котором решение о сохранении элемента зависит от самого элемента, а не от контейнера, в котором он находится. Гарантирует согласованность субсемплирования одного и того же идентификатора в разных Bins.

Fingerprint (Фингерпринт, Цифровой отпечаток)

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

Key (Ключ, LSH Key)

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

LSH (Locality Sensitive Hashing)

Метод хеширования, при котором похожие входные элементы с высокой вероятностью попадают в один и тот же сегмент индекса (Bin).

Offset (Смещение)

Позиция сегмента контента внутри исходного файла (например, временная метка в видео или номер строки в документе).

Reference Identifier (Идентификатор ссылки)

Указатель на конкретный сегмент контента. Обычно состоит из идентификатора контента (Video ID или Document ID) и смещения (Offset).

Sampling Index (Индекс семплирования)

Значение (от 0 до K-1), присваиваемое идентификатору в процессе субсемплирования. Используется для принятия решения о сохранении или удалении идентификатора.

Sub-sampling Factor (K) (Коэффициент субсемплирования)

Коэффициент, определяющий степень сокращения данных (например, K=2 означает сохранение 50% данных).

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

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

1. Система хранит набор фингерпринтов (reference fingerprints).
2. Идентифицируются ключи (keys) в этих фингерпринтах.
3. Идентификаторы (reference identifiers) сохраняются в сегментах (bins), ассоциированных с соответствующими ключами.
4. Система сравнивает количество идентификаторов в сегменте с пороговым значением.
5. Если порог превышен, система выполняет субсемплирование идентификаторов в этом сегменте согласно коэффициенту (sub-sampling factor), выбирая подмножество для сохранения и удаляя остальные.

Claim 2 (Зависимый от 1): Детализирует механизм субсемплирования.

Субсемплирование включает отображение (mapping) идентификатора на sampling index и принятие решения о сохранении или удалении на основе этого индекса. Это ключевой механизм для реализации correlated sub-sampling, так как отображение зависит от идентификатора.

Claims 3-7 (Зависимые): Описывают конкретные функции отображения на sampling index.

• Использование модульной арифметики (Offset % K). (Claim 3)
• Использование хеш-функции от смещения (hash(Offset) % K). Это позволяет избежать корреляции с периодичностью данных. (Claim 4, 5)
• Использование хеш-функции от идентификатора видео и смещения (hash(VideoID, Offset) % K). (Claim 6)
• Использование смещенного офсета ((Offset + C) % K). Упоминается, что это может использоваться для гарантированного удаления начальных сегментов (Offset=0). (Claim 7)

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

Сначала проверяется, не превышает ли количество идентификаторов от одного видео (Video A) порог 1. Если да, идентификаторы Video A субсемплируются. Затем проверяется общее количество идентификаторов в сегменте. Если оно превышает порог 2, весь сегмент субсемплируется. Это позволяет управлять ситуациями, когда один источник доминирует в сегменте.

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

1. Система получает входной ключ (input key).
2. Идентифицируется соответствующий сегмент (bin) в индексе.
3. Извлекается набор идентификаторов из сегмента.
4. Количество извлеченных идентификаторов сравнивается с порогом.
5. Если порог превышен, система субсемплирует *извлеченный набор* идентификаторов.

Это показывает, что субсемплирование может происходить как на этапе индексации (Claim 1), так и на этапе доступа к данным (Claim 22).

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

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

INDEXING – Индексирование и извлечение признаков
Основной этап применения. При построении индекса (Reference Index) система анализирует фингерпринты и распределяет идентификаторы по сегментам. Indexing Module и Sub-sampling Module работают здесь для создания эффективного и компактного индекса. Если применяется Claim 1, индекс сразу строится субсемплированным.

RANKING – Ранжирование (L1 Retrieval / Отбор кандидатов)
На этом этапе система выполняет быстрый поиск в индексе для отбора кандидатов. Index Lookup Module обращается к индексу. Эффективность этого этапа напрямую зависит от оптимизаций, описанных в патенте. Если индекс перегружен, скорость L1 падает. Если применяется Claim 22, субсемплирование происходит в момент доступа к данным.

Входные данные (Индексация):

• Набор фингерпринтов (Reference Fingerprints).
• Пороговые значения для размера сегментов (Thresholds).

Выходные данные (Индексация):

• Субсемплированный индекс (Reference Index).

На что влияет

• Типы контента: Патент сфокусирован на видео, но явно указывает, что технология применима к аудио, изображениям, документам и веб-индексам.
• Конкретные элементы контента: Наибольшее влияние оказывается на обработку часто встречающихся, неуникальных элементов: boilerplate текст (шаблонные блоки), стандартные футеры, навигационные меню, общие фразы или часто используемые изображения/иконографика.
• Специфические запросы: Влияет на эффективность обработки запросов, которые затрагивают общие термины или признаки.

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

• Триггеры активации: Количество Reference Identifiers в определенном Bin превышает установленный порог (predefined threshold number).
• Пороговые значения: Упоминается возможность установки порогов (например, 100 идентификаторов на сегмент) на основе ограничений памяти, процессорной мощности или пропускной способности сети.
• Временные рамки: Применяется либо во время построения индекса (Indexing time), либо во время доступа к индексу (Retrieval time).

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

Процесс А: Индексация с коррелированным субсемплированием (Correlated Sub-sampling)

1. Получение данных: Система получает набор фингерпринтов для индексации.
2. Идентификация ключей: Фингерпринты разделяются на ключи (Keys).
3. Наполнение сегментов: Идентификаторы (Reference Identifiers) помещаются в соответствующие сегменты (Bins) индекса.
4. Проверка порогов: Для каждого сегмента проверяется, превышает ли количество идентификаторов заданный порог.
5. Определение коэффициента (K): Если порог превышен, определяется необходимый коэффициент субсемплирования (K). Патент описывает возможность инкрементального подхода (например, K=3, затем K=9, если порог все еще превышен).
6. Отображение на Sampling Index (Корреляция): Каждый идентификатор в сегменте отображается на Sampling Index (от 0 до K-1). Функция отображения зависит только от идентификатора (например, hash(Identifier) % K или Offset % K).
7. Субсемплирование: Идентификаторы, чей Sampling Index равен определенному значению (например, 0), сохраняются в сегменте. Остальные удаляются.

Процесс Б: Двухуровневое субсемплирование (Per-Video/Per-Source)

1. Анализ распределения источников: В переполненном сегменте анализируется, сколько идентификаторов пришло от каждого источника (например, от одного видео).
2. Субсемплирование доминантов: Если один источник превышает индивидуальный порог, его идентификаторы субсемплируются первыми.
3. Общее субсемплирование: Если после шага 2 общий размер сегмента все еще превышает общий порог, применяется общее субсемплирование (Процесс А, шаги 5-7) ко всем оставшимся идентификаторам (или только к тем, которые еще не были субсемплированы).

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

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

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

• Контентные/Структурные факторы (Производные): Используются значения Fingerprints, которые являются производными от характеристик контента (визуальных, аудио или текстуальных/структурных). Из них формируются Keys.
• Системные идентификаторы:
  • Video Identifier (или Document ID): Идентификатор источника контента.
  • Offset: Позиция сегмента внутри источника.

  Эти данные составляют Reference Identifier и используются в функциях отображения для субсемплирования.

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

• Bin Size: Количество Reference Identifiers в сегменте.
• Thresholds: Предопределенные максимальные размеры сегментов (общие и для отдельных источников).
• Sub-sampling factor (K): Коэффициент сокращения данных. Определяется динамически или задан заранее.
• Sampling Index (I_s): Метрика для коррелированного субсемплирования. Рассчитывается с использованием различных функций, например:
  • I_s = Offset % K
  • I_s = hash(Offset) % K
  • I_s = hash(VideoID, Offset) % K
• Методы вычислений: Хеширование (Hashing functions) и модульная арифметика (Modulo operator).

Выводы

1. Инфраструктура и эффективность, а не качество: Патент решает исключительно инфраструктурные задачи — повышение скорости доступа к данным и снижение затрат на хранение и обработку индекса. Он не имеет отношения к оценке качества, релевантности или E-E-A-T.
2. Субсемплирование предпочтительнее игнорирования: Google предпочитает сохранять часть информации о часто встречающихся признаках, а не полностью их игнорировать (как при использовании традиционных стоп-слов или blacklisting). Это означает, что даже общие элементы контента (boilerplate) участвуют в процессе поиска совпадений, хотя и с меньшей частотой.
3. Критичность коррелированного субсемплирования: Использование Correlated Sub-sampling является ядром изобретения. Оно позволяет сократить объем данных (в K раз), но при этом снижает вероятность найти совпадение по двум признакам только в K раз, а не в K² (как при независимом семплировании). Это обеспечивает баланс между эффективностью и точностью поиска.
4. Обработка повторяющегося контента: Система эффективно обрабатывает как контент, повторяющийся на разных сайтах, так и контент, многократно повторяющийся внутри одного источника (например, длинный статичный кадр в видео или повторяющийся блок текста на страницах сайта), за счет двухуровневого субсемплирования.
5. Отсутствие прямых SEO-действий: SEO-специалисты не могут напрямую влиять на параметры LSH, размер сегментов индекса или коэффициенты субсемплирования Google.

Практика

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

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

• Фокус на уникальности и различимости: Хотя это общая рекомендация, патент подчеркивает ее важность на инфраструктурном уровне. Контент, обладающий уникальными признаками или уникальными комбинациями признаков, с меньшей вероятностью попадет в переполненные сегменты индекса (bins) и не подвергнется субсемплированию. Это делает его более «видимым» для алгоритмов поиска совпадений.
• Осмысленное использование boilerplate: Понимайте, что стандартные блоки текста (меню, футеры, дисклеймеры), хотя и не игнорируются полностью благодаря этому механизму, могут быть значительно субсемплированы в индексе. Основная ценность страницы должна формироваться уникальным контентом.

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

• Генерация массивов низкокачественного контента: Создание большого количества страниц, состоящих преимущественно из шаблонных, часто повторяющихся элементов без уникальной ценности. Хотя такой контент может быть проиндексирован, его признаки, скорее всего, будут сильно субсемплированы, что снизит его влияние на поиск.

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

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

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

Пример иллюстрирует механизм работы патента, а не тактику SEO.

Сценарий: Индексация шаблонного блока (Boilerplate)

1. Ситуация: 100,000 разных веб-страниц используют один и тот же стандартный блок текста (например, юридический дисклеймер).
2. Индексация: Система извлекает признаки из этого блока и генерирует ключ (Key_BP). Все 100,000 страниц ссылаются на этот ключ.
3. Переполнение сегмента: Сегмент индекса (Bin) для Key_BP переполняется (допустим, порог = 1000).
4. Активация механизма: Система определяет необходимость субсемплирования с коэффициентом K=100.
5. Коррелированное субсемплирование: Каждый идентификатор страницы (Document ID + Offset) хешируется и проверяется (hash(ID) % 100).
6. Результат: В индексе сохраняется только около 1000 ссылок (те, для которых результат проверки равен 0). Остальные 99,000 ссылок удаляются из этого конкретного сегмента.
7. Значение: Система не игнорирует этот блок текста полностью (он не стал стоп-словом), но радикально снизила затраты на его хранение и обработку.

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