Как Яндекс использует иерархические деревья данных для быстрого поиска и фильтрации в вертикальных сервисах (например, Auto.ru)

Описание

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

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

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

Запатентован метод генерации иерархической структуры данных (дерева) для хранения и поиска элементов, обладающих набором дескрипторов (атрибутов). Суть изобретения в организации данных таким образом, что каждый уровень иерархии соответствует определенному типу данных (например, Марка автомобиля), а узлы на этом уровне содержат конкретные значения (например, Audi, BMW). Ключевой особенностью является хранение «Statistical Snapshot» (Статистического среза) в листьях дерева, содержащего агрегированные данные (например, минимальную и максимальную цену, количество объявлений) для соответствующей ветви.

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

Система индексирует данные (например, объявления о продаже авто), строя иерархическое дерево. При добавлении объявления система проходит по дереву (Марка -> Модель -> Год). Если нужной ветви нет, она создается. Когда система достигает конца ветви (листа), она обновляет хранящийся там Statistical Snapshot: увеличивает счетчик и при необходимости корректирует диапазон цен. При поиске система быстро находит нужную ветвь по фильтрам запроса и мгновенно извлекает статистику из листа. Это позволяет быстро применять фильтры (например, по цене) и показывать агрегированные данные, не перебирая все объявления по отдельности.

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

Высокая (для инфраструктуры вертикального поиска). Методы организации данных для фасетной навигации и быстрого применения фильтров критически важны для работы классифайдов и крупных e-commerce площадок. Описанные принципы построения иерархий и прекалькуляции агрегатов являются фундаментальными для подобных систем.

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

Влияние на SEO низкое (3/10) для общего веб-поиска. Патент описывает внутренние инфраструктурные процессы Яндекса для организации вертикального поиска (в патенте упоминается Yandex.Auto), а не алгоритмы ранжирования по релевантности или качеству. Однако он имеет значение для оптимизации листингов внутри этих вертикальных сервисов. Патент подчеркивает важность предоставления точных, полных и нормализованных структурированных данных (атрибутов), чтобы обеспечить корректную категоризацию объявления в иерархии и его видимость при использовании фильтров.

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

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

Data Element (Элемент данных)

Единица информации, подлежащая поиску (например, одно объявление о продаже автомобиля).

Data Type (Тип данных)

Категория или тип атрибута элемента данных (например, «Марка автомобиля», «Модель автомобиля», «Год выпуска», «Цена»).

Descriptor (Дескриптор)

Конкретное значение атрибута определенного типа данных (например, «Audi», «A4», «2008», «15000»).

Hierarchical Data Structure (Иерархическая структура данных)

Древовидная структура (Data Tree), используемая для организации данных. Имеет несколько уровней (Levels), каждый из которых ассоциирован с определенным типом данных.

Index Tree Manager (Менеджер дерева индексов)

Компонент системы, отвечающий за генерацию и обновление иерархической структуры данных на основе индекса.

Leaf Node (Лист / Конечный узел)

Узел на самом нижнем уровне иерархии, не имеющий дочерних узлов. В контексте патента хранит Statistical Snapshot.

Node (Узел)

Элемент иерархической структуры (Root, Parent, Child, Leaf), хранящий дескриптор и связи с другими узлами.

Sequential Data Structure (Последовательная структура данных)

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

Statistical Snapshot (Статистический срез)

Агрегированная информация об элементах данных, принадлежащих к определенной ветви дерева. Хранится в Leaf Node. Обычно включает количество элементов (Count), минимальное (Min Value) и максимальное (Max Value) значения определенного дескриптора (например, цены).

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

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

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

1. Идентификация элементов данных, имеющих набор дескрипторов. Каждый дескриптор в наборе принадлежит к уникальному типу данных.
2. Определение иерархической структуры с уровнями (например, первый и второй уровень).
3. Размещение родительского узла на первом уровне для хранения первого дескриптора (определенного первого типа данных).
4. Размещение дочерних узлов на втором уровне, зависимых от родительского. Каждый дочерний узел хранит второй дескриптор (определенного второго типа данных, отличного от первого).

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

Claims 10, 12, 13 (Зависимые пункты): Описывают механизм статистических срезов, который является ключевым для эффективности системы.

1. При индексации элемента данных система идентифицирует конечный узел (Leaf Node), связанный с соответствующими дескрипторами элемента (Claim 10).
2. Система обновляет Leaf Node, сохраняя в нем Statistical Snapshot (Claim 12).
3. Statistical Snapshot включает: (i) количество элементов данных, связанных с этим Leaf Node, (ii) индикацию минимального значения (Min Value) дескриптора, и (iii) индикацию максимального значения (Max Value) дескриптора (Claim 13).

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

Claims 16, 17, 18 (Зависимые пункты): Описывают логику обновления статистики.

1. При добавлении нового элемента система обновляет счетчик (Count).
2. Система определяет, нужно ли обновить Min Value и Max Value на основе значения дескриптора нового элемента.
3. Проверка выполняется путем сравнения нового значения с текущим диапазоном (Min/Max).
4. Если новое значение выходит за пределы диапазона (меньше минимума или больше максимума), соответствующее значение (Min или Max) обновляется.

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

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

1. Получение поискового запроса с параметром (определенного типа данных).
2. Распознавание ветви в иерархической структуре, где узел содержит дескриптор, соответствующий параметру запроса.
3. Доступ к Leaf Node, ассоциированному с этой ветвью.
4. Извлечение данных из Leaf Node.

Claim 27 (Зависимый пункт): Описывает агрегацию результатов поиска.

Если поиск затрагивает несколько ветвей (и, соответственно, несколько Leaf Nodes, например, первый и второй), система определяет общую статистику: общее количество элементов, общий минимум и общий максимум среди всех элементов в этих Leaf Nodes.

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

Изобретение применяется в инфраструктуре вертикальных поисковых сервисов Яндекса (например, Yandex.Auto, упоминаемый в патенте), где требуется эффективная обработка структурированных данных и фасетная навигация.

INDEXING – Индексирование и извлечение признаков
Основное применение патента происходит на этом этапе. Компонент Index Tree Manager получает данные из хранилища индексов (Index Storage) и генерирует Hierarchical Data Structure (дерево индексов), сохраняя его в Index Tree Storage. Процесс запускается периодически или при обновлении данных.

На вход поступают индексированные элементы данных (объявления) с нормализованными дескрипторами. На выходе получается иерархическая структура с прекалькулированными Statistical Snapshots.

RANKING – Ранжирование (Этап Retrieval/Filtering)
На этапе выполнения запроса компонент Searcher использует эту структуру для быстрого поиска и фильтрации. Вместо ранжирования по релевантности, эта система обеспечивает быстрое извлечение элементов, точно соответствующих заданным структурированным фильтрам, и получение агрегированной статистики по ним.

На что влияет

• Типы контента и ниши: Влияет исключительно на сервисы, оперирующие большими объемами структурированных данных: классифайды, вертикальный поиск (авто, недвижимость, товары с четкими характеристиками). Не влияет на поиск по неструктурированному контенту (статьи, новости).
• Специфические запросы: Влияет на запросы, подразумевающие фильтрацию по атрибутам (например, «Audi A6 2007 цена до 20000»).

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

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

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

Процесс А: Построение и обновление иерархической структуры

1. Инициализация структуры: Определяется количество уровней иерархии и соответствие каждого уровня определенному типу данных (например, Уровень 1=Марка, Уровень 2=Модель, Уровень 3=Год). Порядок уровней может быть предопределен или выбран динамически.
2. Получение элемента данных: Система получает новый элемент для индексации (например, объявление с набором дескрипторов: Audi, A4, 2008, Цена 17000).
3. Иерархический обход и создание узлов:
   1. Начиная с корневого узла (Root), система переходит на первый уровень (Марка).
   2. Проверяется, существует ли узел для дескриптора «Audi». Если нет, он создается.
   3. Система переходит к этому узлу и повторяет процесс для следующего уровня (Модель, «A4») и далее (Год, «2008»).
4. Доступ к конечному узлу (Leaf Node): После прохождения всех уровней иерархии система достигает Leaf Node, соответствующего данной комбинации дескрипторов. Если его нет, он создается.
5. Обновление Statistical Snapshot:
   1. Счетчик (Count) элементов в Leaf Node увеличивается на 1.
   2. Значение цены нового элемента (17000) сравнивается с текущими минимальным (Min Price) и максимальным (Max Price) значениями в Leaf Node.
   3. Если новая цена меньше минимума или больше максимума, соответствующее значение в Statistical Snapshot обновляется.

Процесс Б: Поиск и агрегация

1. Получение и парсинг запроса: Система получает запрос (например, «Audi A4 2008»).
2. Иерархический обход: Система проходит по дереву, ища узлы, соответствующие дескрипторам запроса (Audi -> A4 -> 2008).
3. Идентификация ветвей: Если в запросе пропущены дескрипторы (например, запрос «Audi 2008»), система идентифицирует все подходящие ветви (Audi -> A4 -> 2008; Audi -> A6 -> 2008 и т.д.).
4. Извлечение статистики: Система получает доступ к Leaf Nodes идентифицированных ветвей и извлекает Statistical Snapshots.
5. Агрегация (если требуется): Если было найдено несколько Leaf Nodes, система агрегирует статистику: суммирует счетчики, находит общий минимум и общий максимум цен.
6. Применение дополнительных фильтров: Если в запросе есть фильтр по цене, система использует извлеченные Min/Max значения для быстрой проверки, удовлетворяют ли найденные элементы условию, без необходимости проверки каждого элемента.

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

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

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

• Структурные / Контентные факторы: Система использует дескрипторы (Descriptors) элементов данных. В приведенном примере это: Марка автомобиля, Модель автомобиля, Год выпуска, Цена продажи, Цвет. Эти данные поступают из партнерских фидов (Partner Feeds).
• Технические факторы: Система полагается на предварительную обработку данных, включая парсинг фидов, унификацию (нормализацию) дескрипторов и валидацию.

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

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

Система не вычисляет метрики релевантности или качества. Вместо этого она вычисляет и хранит агрегированные статистические показатели в рамках Statistical Snapshot:

• Count (Количество): Общее число элементов данных, принадлежащих к определенной ветви иерархии. Рассчитывается инкрементально при добавлении элементов.
• Minimum Value (Минимальное значение): Минимальное значение определенного дескриптора (например, цены) среди всех элементов ветви.
• Maximum Value (Максимальное значение): Максимальное значение определенного дескриптора среди всех элементов ветви.

Расчет Min/Max производится путем простого сравнения значения нового элемента с текущими сохраненными значениями в момент индексации.

Выводы

1. Инфраструктура для вертикального поиска: Патент описывает специализированную инфраструктуру, предназначенную для вертикальных сервисов (классифайдов), а не для общего веб-поиска. Он решает задачи хранения, быстрого поиска и фильтрации структурированных данных.
2. Прекалькуляция статистики (Statistical Snapshot): Ключевая особенность изобретения — хранение агрегированной статистики (Count, Min/Max Price) непосредственно в конечных узлах (листьях) иерархической структуры. Это позволяет мгновенно получать сводные данные и применять фильтры (например, по диапазону цен), не обращаясь к отдельным документам.
3. Эффективность за счет иерархии: Организация данных в виде дерева, где каждый уровень соответствует определенному типу атрибута (Марка, Модель, Год), обеспечивает быстрый доступ к нужным сегментам данных при использовании фасетной навигации.
4. Оптимизация хранения (Sequential Data Structure): Патент также описывает способ физической реализации этого дерева в виде компактной последовательной структуры данных в памяти (используя смещения и ссылки вместо объектов), что дополнительно ускоряет обработку запросов.
5. Отсутствие факторов ранжирования: В патенте не рассматриваются факторы релевантности, качества, поведенческие сигналы или ссылочный вес. Система предназначена для точного извлечения (Retrieval) и фильтрации, а не для ранжирования (Ranking) по качеству.

Практика

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

Хотя патент является инфраструктурным, он дает важные инсайты для SEO-специалистов, работающих с вертикальными сервисами Яндекса (Auto.ru, Недвижимость, Маркет) или крупными классифайдами.

• Обеспечение полноты структурированных данных: Предоставляйте максимально полный набор атрибутов (дескрипторов) для каждого элемента данных (объявления, товара). Это гарантирует, что элемент будет включен во все релевантные ветви иерархической структуры и будет видим при использовании соответствующих фильтров.
• Точность и нормализация данных в фидах: Данные должны быть точными и консистентными. Поскольку система строит иерархию на основе точных значений дескрипторов, ошибки или разночтения (например, «БМВ» вместо «BMW») могут привести к созданию неправильных ветвей или исключению элемента из нужной категории (несмотря на то, что в патенте упоминается процесс унификации на этапе индексации, качество исходных данных критично).
• Актуальность цен и наличия: Statistical Snapshot (диапазоны цен и количество) обновляется на основе данных из фидов. Предоставление неактуальных цен или статусов напрямую влияет на то, как система отображает агрегированную статистику и применяет фильтры по цене.

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

• Пропуск ключевых атрибутов: Отсутствие важных дескрипторов (например, года выпуска или модели) не позволит системе корректно разместить элемент в иерархии, что drastically снизит его видимость при использовании фильтров.
• Указание некорректных или «виртуальных» цен: Попытки манипулировать ценами (например, указывать заведомо низкую цену для привлечения внимания) могут исказить Statistical Snapshot и привести к плохому пользовательскому опыту при фильтрации.
• Дублирование контента: Хотя в описании системы упоминается функция кластеризации и удаления дубликатов, массовое дублирование объявлений создает избыточную нагрузку на индексатор и может привести к проблемам с индексацией.

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

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

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

Сценарий: Оптимизация фида для Yandex.Auto

1. Задача: Убедиться, что объявление о продаже «Audi A4 2008 года за 17000» корректно индексируется и отображается в фильтрах.
2. Действие: В XML-фиде необходимо четко указать все дескрипторы в нормализованном виде: Make=Audi, Model=A4, Year=2008, Price=17000.
3. Как работает система (согласно патенту):
   1. Индексатор размещает объявление в ветке Audi -> A4 -> 2008.
   2. Система обновляет Statistical Snapshot в листе этой ветки. Если это первое объявление, Count=1, Min=17000, Max=17000.
   3. Если добавляется второе объявление той же модели за 15000, статистика обновится: Count=2, Min=15000, Max=17000.
4. Результат: Когда пользователь ищет «Audi A4 2008» и устанавливает фильтр цены «от 16000», система мгновенно проверяет Statistical Snapshot (Max=17000). Так как диапазон пересекается, система покажет результаты из этой ветки. Если бы атрибуты были указаны неверно, объявление не попало бы в нужную ветку и не было бы найдено.

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