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

# 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)

```python
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 (отклонён)

```python
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-уровень:

   ```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 (ложные коллизии)