Как Google использует графы (DAG) для эффективного хранения и выбора конфигураций и вариантов данных

Описание

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

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

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

Запатентована система и метод организации обусловленных данных (conditioned data) в структуру Directed Acyclic Graph (DAG), которая реализует функциональность Skip List (Список с пропусками). Эта структура позволяет эффективно хранить различные варианты данных (например, конфигурации системы, элементы пользовательского интерфейса) и быстро выбирать нужный вариант на основе набора характеристик (features) входящего запроса.

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

Система работает в двух режимах: организация и извлечение.

• Организация: Элементы данных (data elements) и связанные с ними критерии (criteria) вставляются в DAG последовательно. При вставке система сравнивает критерии нового элемента с уже существующими (в порядке от самых новых к старым), вычисляя пересечения (intersection) и разности (set difference). Это структурирует данные иерархически.
• Извлечение: При получении запроса система определяет его характеристики (features). Затем она обходит DAG в топологическом порядке, используя логику Skip List, чтобы быстро найти элемент данных, чьи критерии соответствуют характеристикам запроса. Также проверяется «дополнительное условие» (additional condition).

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

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

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

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

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

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

Additional Condition (Дополнительное условие)

Условие, связанное с элементом данных, которое проверяется во время поиска. Оно может зависеть или не зависеть от характеристик запроса. Для успешного поиска это условие должно быть выполнено вместе с основными критериями.

Criteria (Критерии)

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

Data Element / Variant (Элемент данных / Вариант)

Единица данных, хранимая в системе. В патенте упоминаются примеры: элементы пользовательского интерфейса (анимация, видео, игра), а также данные о форматировании (CSS, JS), тексте ссылок, URL.

Directed Acyclic Graph (DAG) (Направленный ациклический граф)

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

Features (Характеристики запроса)

Набор атрибутов входящего запроса (например, IP-адрес пользователя, тип браузера, язык запроса), который используется для сопоставления с критериями элементов данных.

Intersection / Set Difference (Пересечение / Разность множеств)

Операции над множествами критериев. Используются в процессе построения DAG для определения взаимосвязей между элементами данных и оптимизации хранения.

Skip List (Список с пропусками)

Структура данных, позволяющая быстро осуществлять поиск. В данном патенте DAG эмулирует поведение Skip List для эффективного обхода и сопоставления условий.

Topological Order (Топологический порядок)

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

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

Патент содержит два основных процесса: организацию данных в DAG и извлечение данных из DAG.

Claim 1 (Независимый пункт — Извлечение): Описывает метод поиска данных в DAG.

1. Система получает запрос и определяет его характеристики (set of features).
2. Определяется «верхний список» (top list) элементов данных из DAG в топологическом порядке.
3. Для первого элемента данных в списке определяются его критерии (criteria specifying conditions) и дополнительное условие (additional condition).
4. Проверяется, соответствуют ли характеристики запроса критериям элемента.
5. Проверяется, выполнено ли дополнительное условие.
6. Если И критерии соответствуют, И дополнительное условие выполнено, этот элемент данных возвращается как результат запроса.

Claims 2 и 3 (Зависимые — Навигация): Детализируют процесс обхода графа (логика Skip List), если соответствие не найдено.

Если характеристики запроса не соответствуют критериям (Claim 2) или дополнительному условию (Claim 3):

1. Система проверяет, был ли просмотрен весь «верхний список».
2. Если НЕТ, переходит к следующему элементу в списке.
3. Если ДА, формируется «нижний список» (bottom list), включающий соседние узлы (neighboring nodes) текущего элемента. Этот «нижний список» становится новым «верхним списком», и поиск продолжается.

Claim 7 (Зависимый, описывающий Организацию): Описывает процесс построения DAG.

1. Система определяет список элементов данных.
2. Для нового элемента определяется первый набор критериев. Элемент идентифицируется как узел в DAG.
3. Определяется второй набор критериев для ранее вставленного элемента. Порядок проверки основан на актуальности (order based on recency) – от самых новых к самым старым.
4. Вычисляется пересечение (intersection) первого и второго наборов критериев.
5. Если пересечение не пустое, текущий элемент идентифицируется как соседний узел ранее вставленного элемента в DAG.

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

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

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

QUNDERSTANDING – Понимание Запросов
На этом этапе извлекаются характеристики (features) запроса и контекста пользователя (устройство, местоположение, язык), которые затем используются как входные данные для системы извлечения данных из DAG.

METASEARCH – Метапоиск и Смешивание (Уровень Представления)
Наиболее вероятное применение. Система может использоваться для выбора элементов пользовательского интерфейса (SERP Features) и их вариантов. Например, какой тип локального блока или какой формат рекламы показать в зависимости от устройства пользователя, его местоположения и т.д.

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

• (Организация): Список data elements и связанных с ними criteria.
• (Извлечение): Входящий запрос и его features; структура DAG.

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

• (Организация): Оптимизированная структура DAG.
• (Извлечение): Соответствующий data element (конфигурация или вариант данных).

На что влияет

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

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

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

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

Процесс А: Организация данных (Построение DAG)

1. Инициализация: Начинается с пустого графа (DAG) и пустого списка корневых узлов.
2. Выбор элемента и определение критериев (Набор 1): Выбирается элемент данных для вставки и определяется его набор критериев. Если набор пуст, элемент пропускается.
3. Идентификация узла: Элемент данных становится узлом в графе.
4. Сравнение с предыдущими элементами: Система перебирает ранее вставленные элементы в порядке от самых новых к самым старым (recency).
5. Определение критериев (Набор 2): Для каждого ранее вставленного элемента определяется его набор критериев.
6. Проверка пересечения: Вычисляется пересечение Набора 1 и Набора 2.
   • Если пересечение пустое: Переход к следующему ранее вставленному элементу. Если элементов больше нет, текущий элемент добавляется как корневой узел (root node).
   • Если пересечение не пустое: Переход к шагу 7.
7. Установка связи и обновление критериев: Текущий элемент идентифицируется как сосед (neighboring node) ранее вставленного элемента. Вычисляется разность множеств (set difference) между Набором 1 и Набором 2. Набор 1 заменяется этой разностью.
8. Проверка Набора 1: Если Набор 1 стал пустым, процесс вставки завершен для этого элемента. Если нет, продолжается сравнение оставшихся критериев (новый Набор 1) с другими ранее вставленными элементами (шаг 4).

Процесс Б: Извлечение данных (Обход DAG)

1. Получение запроса: Система получает запрос и определяет его характеристики (features).
2. Инициализация поиска: Определяется «верхний список» (top list) элементов данных (например, корневые узлы) в топологическом порядке.
3. Выбор элемента: Выбирается первый элемент из верхнего списка.
4. Определение условий: Определяются критерии и дополнительное условие (additional condition), связанные с этим элементом.
5. Проверка критериев: Проверяется, соответствуют ли характеристики запроса критериям элемента.
   • Если ДА: Переход к шагу 6.
   • Если НЕТ: Переход к шагу 7.
6. Проверка дополнительного условия: Проверяется, выполнено ли дополнительное условие.
   • Если ДА: Поиск успешен. Элемент возвращается как результат. Процесс завершается.
   • Если НЕТ: Переход к шагу 7.
7. Проверка списка: Определяется, остались ли непроверенные элементы в верхнем списке.
   • Если ДА: Выбирается следующий элемент в верхнем списке. Переход к шагу 4.
   • Если НЕТ: Переход к шагу 8.
8. Спуск по графу (Skip): Идентифицируется «нижний список» (bottom list), состоящий из соседних узлов текущего элемента. Нижний список становится новым верхним списком. Переход к шагу 3.

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

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

Патент абстрактен и не перечисляет конкретные SEO-факторы (контентные, ссылочные, поведенческие и т.д.). Он оперирует следующими типами данных:

• Характеристики запроса (Features): Атрибуты входящего запроса. В патенте упоминаются примеры: страна происхождения на основе IP-адреса, тип браузера, язык отображения, статус входа пользователя в систему, возрастная группа, происхождение домена.
• Критерии данных (Criteria): Условия, привязанные к каждому элементу данных, которые должны быть выполнены для его выбора.
• Элементы данных (Data Elements): Сами данные, хранящиеся в DAG. Примеры: элементы UI (анимация, видео, игра), текст ссылок, URL, CSS, JavaScript.

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

Система не вычисляет метрики или оценки (Scores) в традиционном понимании ранжирования. Вместо этого она использует операции теории множеств и булеву логику:

• Сопоставление (Matching): Булева проверка соответствия характеристик запроса критериям элемента данных.
• Intersection (Пересечение): Используется при построении графа для идентификации общих критериев между двумя элементами.
• Set Difference (Разность множеств): Используется при построении графа для определения критериев, которые остались у элемента после учета общих критериев с родительским узлом.
• Order of Insertion (Порядок вставки): Используется при построении DAG; более поздние вставки имеют приоритет над более ранними при перекрытии критериев.

Выводы

1. Инфраструктурный фокус: Патент посвящен исключительно оптимизации хранения и извлечения данных внутри систем Google. Он решает проблему эффективного управления сложными конфигурациями и вариантами.
2. Эффективность обработки пересекающихся условий: Использование DAG в сочетании с Skip List позволяет системе эффективно обрабатывать данные с сильно пересекающимися и многомерными критериями без потери производительности, свойственной традиционным методам (например, хэш-таблицам).
3. Приоритет по новизне: Механизм построения DAG учитывает порядок вставки. Новые конфигурации могут переопределять старые, если их критерии пересекаются, что упрощает обновление системы.
4. Гибкость через «Дополнительные условия»: Механизм Additional Condition предоставляет дополнительный слой гибкости при поиске, позволяя выполнять проверки, которые могут выходить за рамки стандартного сопоставления характеристик и критериев.
5. Отсутствие прямой связи с SEO: Патент не дает никаких прямых указаний для SEO-специалистов по оптимизации сайтов. Он не раскрывает факторы ранжирования и не описывает алгоритмы оценки качества контента.

Практика

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

Патент описывает внутренние процессы Google без прямых рекомендаций для SEO. Он является инфраструктурным и не дает практических выводов для SEO-оптимизации внешних веб-сайтов. Невозможно оптимизировать сайт под структуру данных DAG/Skip List, описанную в патенте.

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

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

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

Стратегическое значение патента для SEO минимально. Он служит напоминанием о том, что системы Google чрезвычайно сложны и используют передовые методы информатики для управления этой сложностью. Это подчеркивает способность Google применять очень детализированные и контекстно-зависимые правила (будь то в ранжировании или в отображении SERP), но не раскрывает сами эти правила.

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

Практических примеров применения для SEO нет. Однако можно привести пример того, как Google может использовать эту технологию внутри компании.

Сценарий: Выбор варианта UI-элемента (например, Google Doodle)

1. Задача: Определить, какой логотип показать на главной странице.
2. Элементы данных в DAG:
   • Вариант A: Праздничный Doodle (Критерии: Страна=США, Дата=04.07).
   • Вариант B: Стандартный логотип (Критерии: Универсальные).
3. Запрос пользователя: Характеристики (Features) запроса: Страна=США, Дата=04.07, Устройство=Десктоп.
4. Процесс поиска: Система быстро обходит DAG. Она находит Вариант A, так как его критерии полностью совпадают с характеристиками запроса.
5. Результат: Пользователю отображается Вариант A (Doodle). Описанный в патенте механизм обеспечивает быстрое и эффективное выполнение этого выбора.

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