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

Описание

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

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

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

Запатентованы способ и сервер для формирования рекомендаций по парковке на основе анализа исторических данных о маршрутах. Суть изобретения заключается в использовании модифицированного алгоритма MST (Minimum Spanning Tree), в частности алгоритма Крускала, для иерархической кластеризации фактических конечных точек маршрутов. Ключевая особенность — кластеризация учитывает не только географическую близость, но и детальную структуру (Граф дорог) и Классы объектов карты, используя эвристическую функцию оценки.

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

Система собирает исторические данные о маршрутах в определенный пункт назначения и определяет фактические Конечные точки, где пользователи останавливались (парковались). Эти точки накладываются на Граф дорог, учитывающий классы объектов (типы дорог, препятствия). Затем применяется алгоритм иерархической кластеризации (модифицированный алгоритм Крускала). Он использует функцию эвристической оценки для расчета «веса» между точками, накладывая штрафы, если точки разделены препятствиями или находятся на разных иерархических уровнях дорожной сети. В результате формируются кластеры доступных парковочных зон, которые затем рекомендуются новым пользователям.

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

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

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

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

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

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

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

Алгоритм Крускала (Kruskal’s algorithm)

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

Граф дорог (Road Graph)

Графическое представление карты, где пути представлены в виде ребер и вершин (Объектов карты). Содержит информацию об иерархии и структуре дорожной сети.

Класс объекта (Object Class)

Атрибут Объекта карты, указывающий на вид структуры и/или его иерархический уровень. Примеры: «участок дороги» (автомагистраль, местная дорога, двор), «препятствие» (тупик, барьер), «официальная парковка».

Конечная точка (Endpoint)

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

Объект карты (Map Object)

Вершина на графе дорог, характеризующаяся местоположением и Классом объекта.

Прошлый маршрут (Past Route)

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

Функция эвристической оценки (Heuristic Evaluation Function)

Функция, используемая алгоритмом кластеризации для расчета взвешенного расстояния между конечными точками. Она учитывает географическое расстояние и Классы объектов, накладывая штрафы за неудобные связи (например, через препятствия или разные типы дорог).

Центроид (Centroid)

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

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

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

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

1. Получение набора Прошлых маршрутов, заканчивающихся в заданном пункте назначения.
2. Определение набора Конечных точек (фактических мест остановки) для этих маршрутов.
3. Получение Графа дорог, включающего объекты карты с их местоположением и Классами объектов.
4. Кластеризация конечных точек. Критически важно: кластеризация выполняется на основе пункта назначения, конечных точек, местоположений объектов и Классов объектов карты. Это означает, что тип дорог и наличие препятствий влияют на формирование парковочных зон.
5. Получение запроса на текущий маршрут от пользователя.
6. Определение текущего маршрута и выбор по меньшей мере одного кластера в качестве рекомендации по парковке.
7. Отправка маршрута и рекомендации пользователю.

Claim 3 (Зависимый): Уточняет механизм кластеризации.

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

Claims 5 и 6 (Зависимые): Уточняют алгоритм кластеризации.

Кластеризация выполняется с использованием функции эвристической оценки (Claim 5) и основана на алгоритме Крускала (Claim 6). Это указывает на использование модифицированного MST-алгоритма, где эвристическая функция определяет вес ребер между конечными точками.

Claim 8 (Зависимый): Уточняет определение конечных точек.

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

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

Изобретение применяется исключительно в рамках навигационных и картографических сервисов Яндекса (например, Яндекс.Навигатор, Яндекс.Карты). Оно не связано с архитектурой веб-поиска.

Механизмы, описанные в патенте, не взаимодействуют со слоями веб-поиска:

• CRAWLING / INDEXING: Не применяется. Система обрабатывает GPS-данные и граф дорог, а не веб-контент.
• QUERY PROCESSING: Применяется только к навигационным запросам (построение маршрута), а не к текстовым поисковым запросам.
• RANKING / BLENDER: Не применяется для ранжирования веб-документов. Применяется для выбора (ранжирования) наиболее подходящих парковочных кластеров для конкретного маршрута.

Процесс делится на две части:

Офлайн-обработка (Предварительные вычисления):

• Анализ исторических логов маршрутов и определение фактических конечных точек (парковок).
• Сопоставление конечных точек с графом дорог и классами объектов.
• Выполнение иерархической кластеризации (модифицированный алгоритм Крускала) для популярных пунктов назначения.
• Сохранение готовых кластеров в базе данных.

Онлайн-обработка (В реальном времени):

• Получение запроса на маршрут от пользователя и построение маршрута.
• Извлечение пре-калькулированных кластеров для пункта назначения.
• Выбор наиболее подходящих кластеров на основе маршрута, размера кластера, центроида и предпочтений пользователя.
• Отображение рекомендаций.

На что влияет

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

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

• Условия активации офлайн-процесса: Активируется для пунктов назначения, по которым накоплено достаточное количество прошлых маршрутов. В патенте упоминается возможность установки порога (например, 2000 маршрутов).
• Условия активации онлайн-процесса: Когда пользователь строит маршрут в пункт назначения, для которого существуют пре-калькулированные парковочные кластеры, или запрашивает информацию о парковках рядом с POI.
• Пороги идентификации парковки: Для идентификации конечной точки используются пороги времени (например, остановка более 4 минут) и расстояния (например, в пределах 500 метров от пункта назначения).

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

Фаза 1: Офлайн-обработка и кластеризация (Способ 600)

1. Сбор данных: Получение набора прошлых маршрутов в заданный пункт назначения из базы данных.
2. Определение конечных точек: Анализ маршрутов для определения фактических мест остановки (парковок). Фильтрация точек по времени остановки и расстоянию до пункта назначения.
3. Получение графа дорог: Загрузка графа дорог для соответствующей зоны, включая объекты карты, их местоположение и классы (иерархию).
4. Сопоставление: Привязка каждой конечной точки к ближайшему объекту карты и его классу.
5. Иерархическая кластеризация (Модифицированный алгоритм Крускала):
   1. Инициализация: Каждая конечная точка рассматривается как отдельный кластер.
   2. Расчет весов: Вычисление взвешенного расстояния между парами точек/кластеров с использованием функции эвристической оценки. Функция учитывает расстояние и классы объектов, накладывая штрафы за пересечение препятствий или разных типов дорог.
   3. Итеративное слияние: Соединение двух точек/кластеров с минимальным взвешенным расстоянием.
   4. Остановка: Процесс продолжается до достижения оптимальной функции оценки или заданного количества кластеров.
6. Сохранение результатов: Расчет центроидов и размеров для полученных кластеров и сохранение их в базе данных в привязке к пункту назначения.

Фаза 2: Онлайн-рекомендация (Способ 700)

1. Получение запроса: Получение запроса на построение маршрута от пользователя.
2. Определение маршрута и рекомендаций: Построение текущего маршрута и извлечение сохраненных кластеров для пункта назначения. Выбор одного или нескольких кластеров на основе их центроида, размера и соответствия текущему маршруту.
3. Отправка данных: Отправка маршрута и рекомендаций по парковке на устройство пользователя.

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

Система использует данные, связанные с навигацией и физическим миром. Традиционные факторы SEO (контентные, ссылочные, технические факторы сайта) не используются.

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

• Поведенческие факторы (Навигационные):
  • Набор прошлых маршрутов пользователей (траектории, GPS-данные).
  • Фактические конечные точки маршрутов.
  • Отметки времени и продолжительность остановки в конечной точке.
  • Данные о поведении в приложении (например, закрытие приложения как индикатор завершения маршрута).
• Географические и Инфраструктурные факторы (Граф дорог):
  • Структура дорожной сети.
  • Местоположение объектов (координаты).
  • Классы объектов (иерархия):
    • «Участок дороги» (скоростная автострада, автомагистраль, дорога районного значения, местная дорога, двор).
    • «Препятствие» (стройка, тупик, барьер, знак «въезд запрещен», частная дорога).
    • «Официальная парковка» (цена, размер).
• Временные факторы: Период времени для анализа прошлых маршрутов (например, будни с 8:00 до 17:00).

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

• Взвешенное расстояние (Weighted Distance): Ключевая метрика для кластеризации. Рассчитывается с помощью функции эвристической оценки. Она базируется на географическом расстоянии, но модифицирована (оштрафована) с учетом классов объектов и иерархии дорожного графа, чтобы отражать реальное удобство доступа.
• Размер кластера (Cluster Size): Метрика, указывающая на площадь зоны парковки или количество конечных точек в кластере. Используется при рекомендации (больше размер — выше вероятность найти место).
• Центроид кластера (Cluster Centroid): Географический центр кластера. Используется для определения релевантности кластера направлению движения пользователя.
• Пороговые значения:
  • Порог времени остановки (например, 4 минуты) для идентификации конечной точки.
  • Порог расстояния до пункта назначения (например, 500 метров).
  • Порог количества прошлых маршрутов для запуска анализа для POI.
• Алгоритмы: Используется алгоритмический подход на основе графов — модифицированный алгоритм Крускала (MST) для иерархической кластеризации.

Выводы

1. Патент не относится к Веб-поиску: Это изобретение полностью сосредоточено на улучшении навигационных сервисов Яндекса (Карты, Навигатор) и не описывает механизмы ранжирования сайтов в поисковой выдаче.
2. Использование исторических данных для поиска парковок: Яндекс активно использует агрегированные данные о том, где пользователи фактически завершают свои маршруты, для выявления как официальных, так и неофициальных («народных») парковочных мест.
3. Иерархическая кластеризация на основе графа дорог: Ключевая инновация — применение модифицированного алгоритма MST (Крускала) для кластеризации. Этот алгоритм учитывает реальную инфраструктуру (иерархию дорог, препятствия), а не только географическую близость.
4. Эвристическая оценка удобства: Система использует функцию эвристической оценки для штрафования кластеров, которые географически близки, но разделены неудобными препятствиями (например, оживленной дорогой), что повышает практическую релевантность рекомендаций.
5. Офлайн-вычисления: Процесс кластеризации выполняется офлайн для популярных POI, что позволяет быстро предоставлять рекомендации в реальном времени.

Практика

Патент является инфраструктурным и описывает технологию навигации. Он не дает практических выводов для SEO-продвижения сайтов в веб-поиске.

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

Для специалистов по Local SEO и управлению репутацией (ORM) можно сделать косвенные выводы:

• Обеспечение физической доступности: Система Яндекса стремится облегчить пользователю доступ к пункту назначения. Если физический доступ к вашему бизнесу затруднен (плохая парковка, непонятный въезд), это может негативно сказаться на посещаемости и общем пользовательском опыте, даже если вы находитесь высоко в локальной выдаче.
• Актуализация данных на Картах: Убедитесь, что информация о вашей организации, включая официальные парковочные места, въезды и возможные препятствия (шлагбаумы, ремонтные работы), актуальна в Яндекс.Бизнес и на Народной Карте. Это помогает системе корректно строить граф дорог и формировать кластеры вокруг вашей локации.
• Стимулирование использования навигации: Чем больше пользователей строят маршруты до вашей точки и успешно паркуются, тем больше данных получает Яндекс для анализа доступности вашей локации.

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

Не применимо к Web SEO. В контексте Local SEO не следует предоставлять ложную информацию о наличии доступной парковки, так как это приведет к негативному пользовательскому опыту.

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

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

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

Практических примеров для применения в работе по SEO продвижению сайтов нет.

Пример работы технологии в Яндекс.Навигаторе:

1. Сценарий: Пользователь едет в популярный бизнес-центр (БЦ).
2. Офлайн-анализ (Яндекс): Система проанализировала тысячи прошлых поездок в этот БЦ. Она выявила, что многие пользователи паркуются не на официальной парковке БЦ, а на прилегающей улице и во дворе соседнего дома.
3. Кластеризация: Алгоритм Крускала с эвристической функцией сгруппировал парковки на улице в Кластер А, а парковки во дворе в Кластер Б. Он не объединил их, так как въезд во двор осуществляется через арку (учтено в графе дорог), а улица имеет одностороннее движение.
4. Онлайн-рекомендация: Когда новый пользователь приближается к БЦ, Навигатор предлагает ему маршрут и показывает Кластер А и Кластер Б как варианты парковки, в зависимости от того, с какой стороны он подъезжает.

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