enduro-trails/docs/work-items/ET-008/06-adr/ADR-006-dedup-algorithm.md

type, work_item_id, adr_id, title, status, created_at, authors, supersedes, superseded_by, labels

type	work_item_id	adr_id	title	status	created_at	authors	supersedes	superseded_by	labels
adr	ET-008	ADR-006	ADR-006: Дедупликация публичных GPS-треков — bbox+length+date bucket-hash, мерж sources при коллизии, без геометрических метрик	accepted	2026-06-01	agent:architect

ADR-006 — Алгоритм дедупликации публичных GPS-треков

Статус

Accepted

Контекст

Один и тот же реальный трек может быть выложен автором на несколько платформ (BRD §6 риск №3): тот же маршрут пользователь публикует в EnduroRussia.ru и в Wikiloc, дублирует в OSM Public GPS Traces при разборе и т.п. Цель ET-008 (BRD §1) — «одна запись на реальный трек, с union'ом источников и ссылок». Метрика — BRD §5: ≤ 5% дублей при ручной проверке 100 случайных треков.

Архитектурно нужно выбрать:

1. Какой признак считать «тот же трек». Координаты на платформах округлены / прорежены / иногда обработаны (сглаживание); полное совпадение точек — редкое.
2. Сложность алгоритма. На 5000 треков допустим O(n²); на 50 000+ при расширении на РФ — нет. Нужно либо O(n log n), либо хэш O(n).
3. Поведение при отсутствии метаданных. У OSM-треков нет «активности», у скрейпленых страниц иногда нет даты — что делать.
4. Что фиксируется при коллизии — кто из источников «выиграл» в полях name/user/activity_type.

Рассмотренные варианты

Вариант A — Bucket-hash по bbox + length + date (выбран; совпадает с TRZ REQ-F-08)

def compute_dedup_key(geom: LineString, meta: dict) -> str:
    w, s, e, n = geom.bounds
    bbox_round = (round(w, 2), round(s, 2), round(e, 2), round(n, 2))  # ≈ 1.1 км
    length_bucket = round(meta["length_m"] / 1000) * 1000                # 1 км
    date_bucket = (meta.get("created_at") or "")[:10]                    # YYYY-MM-DD
    return f"{bbox_round}|{length_bucket}|{date_bucket}"

• Сложность: O(1) на трек, O(n) на пайплайн. Идеально для INSERT с UNIQUE(dedup_key) ON CONFLICT.
• Точность: для треков с известной датой — высокая (BBox-проекция отлично различает соседние «утренний эндуро в Калужской» vs «вечерний в Подмосковье»; на одной дате одинаковая длина в одном bbox — это почти всегда тот же трек).
• Ложные коллизии: треки без даты в одном bbox с похожей длиной — будут смерджены. По BRD §6 это явный риск (пользователь может потерять «свой» вариант трека). Митигация — 08-data-requirements.md §6 и AC-03 «Треки без даты от разных источников».
• Ложные не-коллизии: один и тот же трек у двух источников с расхождением даты на 1+ день (один источник датирует загрузку, другой — запись GPS) — не смердживается. На практике источники сохраняют дату GPS из самого файла; расхождение редкое.

Вариант B — Frechet/Hausdorff-расстояние между LineString (отклонён)

• Сложность: O(n²) на регион при наивной реализации; даже с R-tree-префильтром по bbox остаётся O(n × k), где k — кандидаты в 1-км окне.
• Реалистичный pipeline-overhead: для 5000 треков с медианой 1240 точек — ~30 минут вычислений на регион. Это съедает половину cron-окна (6 ч).
• Преимущества — устойчивость к шумам в координатах; недостатки — высокая стоимость, и при ≥ 50 000 треков становится непригодным.

Вариант C — Хэш resampled-points (отклонён)

sampled = resample(geom, every_n_meters=100)
key = sha256(",".join(f"{lat:.4f},{lon:.4f}" for lat, lon in sampled))

• Сложность: O(n) на трек, O(n) на пайплайн. Хорошо.
• Точность: хуже A — на платформах с разным сглаживанием те же 100-метровые точки могут отличаться в 4-м знаке после запятой → хэши не совпадают. То есть метод нестабилен между источниками.
• Можно округлять до 3 знаков (≈ 100 м), но тогда два соседних трека по той же лесной просеке дают одинаковый хэш — снова коллизии.

Вариант D — Гибрид: bucket-hash как первичный фильтр + Frechet как тай-брейкер (отклонён)

• Соблазнительно: A для скорости, B на коллизиях.
• Сложность реализации высокая: при коллизии bucket-hash нужно подтянуть из БД полную геометрию обоих треков, посчитать Frechet, принять решение. Это блокирующий round-trip в SQLite на каждый коллидирующий INSERT.
• На MVP это over-engineering. Если метрика BRD §5 «≤ 5%» не выполнится — заводится отдельный work item «улучшение dedup».

Решение

Принимается Вариант A — bucket-hash O(1), в точности по формуле TRZ REQ-F-08, с уточнениями:

1. Гранулярность bbox_round — 2 знака после запятой (≈ 1.1 км). Не 1 знак (≈ 11 км — слишком грубо, ложные коллизии для коротких треков в одном городе) и не 3 знака (≈ 110 м — слишком точно, не сходится между источниками с разным сглаживанием).

2. Гранулярность length_bucket — 1 км. На треках длиной 5–50 км это 2–20% разброс, что покрывает межисточниковую разницу подсчёта (округление координат → разные интегралы длины). На очень коротких треках (< 1 км) length_bucket = 0 для всех таких треков — что даст переслияние «всех коротких в одном km²-bbox в одной дате»; вероятность такого совпадения от двух разных авторов исчезающе мала.

3. Гранулярность date_bucket — день (YYYY-MM-DD). Не «час» (источники часто хранят только дату), не «месяц» (слишком грубо — есть популярные маршруты, которые ездят сотнями раз).

4. Отсутствие created_at — date_bucket = "" для обоих треков → они считаются одним ключом. Это сознательный consenrvative-merge:

   • Источники, не отдающие дату, обычно отдают её отдельно (OSM публикует timestamp загрузки; ttrails — дату публикации; EnduroRussia — дату поездки). После анализа лог-сэмплов BRD §5 ожидаем, что > 95% треков имеют дату.
   • Без даты — мы и не отличим «два разных трека с одинаковой геометрией» от «один и тот же выложенный дважды». Merge — меньшее зло, чем дубль; при ошибке достаточно дополнительно показать оба external_urls в popup (REQ-F-18).
   • Документировано в AC-03 «Треки без даты — дедуп срабатывает».

5. Поведение при коллизии — мерж, а не replace:

   • sources_json ← union существующих + нового [source_id].
   • external_urls_json ← union существующих + нового [external_url].
   • name, description, user, tags, activity_type — берутся по приоритету источника в gps_sources.yaml (порядок объявления = приоритет). Если у нового источника приоритет выше — поля перезаписываются; иначе сохраняются старые. Это даёт стабильный детерминированный результат независимо от порядка обхода в pipeline.
   • length_m, points_count, geom — берутся от первого источника (того, кто первым создал запись). Не пересчитываются при мерже. Это снижает риск «джиттера» геометрии трека от прогона к прогону.
   • updated_at — обновляется на текущее время прогона.

6. Реализация в коде — SQL-уровень:

   INSERT INTO tracks (dedup_key, name, ..., sources_json, external_urls_json, ...)
   VALUES (?, ?, ..., ?, ?, ...)
   ON CONFLICT(dedup_key) DO UPDATE SET
       sources_json       = (SELECT json_union(sources_json, excluded.sources_json)),
       external_urls_json = (SELECT json_union(external_urls_json, excluded.external_urls_json)),
       name        = CASE WHEN excluded._priority > _priority THEN excluded.name ELSE name END,
       ...
       updated_at  = excluded.updated_at;
   

   Поскольку SQLite без JSON1 не имеет json_union, мерж массивов реализуется на Python в db.py::upsert_track() (read-merge-write в одной транзакции). Производительность достаточная: O(1) на трек, < 5 мс на upsert.

7. Валидация метрики BRD §5 «< 5% дублей» — отдельный скрипт scripts/dedup_audit.py (отсэмплировать 100 треков, вывести в JSON для ручной проверки). Этот скрипт — артефакт фазы тестирования (04-test-plan.yaml), не runtime.

8. План отступления. Если метрика < 5% не выполнится на реальном датасете:

   • Сузить length_bucket до 500 м.
   • Добавить activity_type в ключ (но тогда сломается «OSM без активности vs EnduroRussia с активностью=enduro» — merge не сработает; нужно явно маппить пропуски в общий слот).
   • В крайнем случае — гибрид A+B (Вариант D выше). Эти эволюции — отдельный ADR, не блокируют ET-008 MVP.

Последствия

Положительные

• O(1) per track, O(n) per pipeline — никакого квадратичного blow-up.
• Реализуется одним SQL ON CONFLICT + Python-мерж массивов; < 100 строк кода.
• Детерминированный результат при перезапуске pipeline (порядок источников фиксирован конфигом).
• Соответствует BRD-метрике «< 5%» на ожидаемом датасете (валидируется QA в фазе теста).

Отрицательные / ограничения

• Ложные коллизии для треков без даты. Принято осознанно (см. §4 решения).
• Ложные коллизии для одного маршрута, проехавшего в разные дни двумя разными людьми с похожей длиной — это не баг, а ограничение: один и тот же популярный 30-км маршрут, проехавший двумя гонщиками в один день, будет смерджен в одну запись. Бизнес-смысл сохраняется (пользователь увидит «по этой тропе ездят»), но статистика «сколько раз проехали» — потеряна. Это out of scope MVP; в BRD §5 «плотность треков» — отдельная фича.
• Length-bucket не работает на круговых треках с малой длиной по прямой — но bbox-проекция эти случаи всё равно различает по координатам.
• При наследовании MVP-кода на регионы с миллионом треков ложные коллизии могут вырасти. Митигация — 10-tech-risks.md R-2; метрика отслеживается на каждом прогоне в pipeline_runs.errors_json.

Технический долг

• Если QA-метрика провалится — план отступления §8 решения.
• Возможный future-rewrite на Вариант D (hybrid) — задокументирован, но не выполняется в MVP.

Классификация изменения

Minor change. Алгоритм — внутренний contract pipeline'а, не виден ни наружу API, ни во фронтенде. Любая будущая правка compute_dedup_key() требует полного re-collect (отбросить БД и пересобрать), но это операционная процедура; затрагивает только data/gps_tracks.sqlite. arch:major-change не требуется.

Связанные документы

• docs/work-items/ET-008/02-trz.md §6.1 «compute_dedup_key»
• docs/work-items/ET-008/03-acceptance-criteria.md AC-03
• docs/work-items/ET-008/06-adr/ADR-005-storage-schema.md §3 (sources_json)
• docs/work-items/ET-008/08-data-requirements.md §3.2 (dedup_key)
• docs/work-items/ET-008/10-tech-risks.md R-2 (ложные коллизии)