spike: Tackle the problem of generated ids

[jcpitre]

In #1 (comment) we realized that some providers would generate new ids for each version of datasets.
When we think about it, it makes sense that ids are only meaningful within the dataset itself. We are not guaranteed that they will make sense in the context of another dataset, even of the same feed.

We looked at mdb-2014. and saw that the shape_ids in shapes.txt a regenerated for each dataset. e.g. from mdb-2014-202603110034:

shape_id,shape_pt_lat,shape_pt_lon,shape_pt_sequence,shape_dist_traveled
0000abe0-5266-475b-808a-5cf929120a80,50.118257595,-5.540823891,229,

But for mdb-2014-202603090029 the "same" line is:

shape_id,shape_pt_lat,shape_pt_lon,shape_pt_sequence,shape_dist_traveled
3d88c650-6c5b-4f14-996b-e5b01b4eec33,50.118257595,-5.540823891,229,

We need to establish how prevalent this in the feeds we host.
And find a way to evaluate the diff considering these generated ids.

Here is copilot take on it:

A rough breakdown by field

Field	Stability	Reason
shape_id	🔴 Very unstable	Almost universally regenerated on export by scheduling tools
trip_id	🟠 Often unstable	HASTUS, Trapeze, and other tools generate these internally
service_id	🟠 Often unstable	Date-based generation is common (e.g. 20240115_WD)
block_id	🟠 Often unstable	Operational scheduling artifact
route_id	🟡 Moderately stable	Often matches public route numbers, but not always
fare_id	🟡 Moderately stable	Fare structures change slowly
stop_id	🟢 Usually stable	Stops are physical — agencies maintain these
agency_id	🟢 Very stable	Rarely changes

So realistically stop_id and agency_id are the only keys you can reliably trust. Everything else is potentially a surrogate.

This means for a large fraction of feeds, the diff engine's output for shapes.txt, trips.txt, and calendar.txt is likely dominated by key churn rather than real changes — which
significantly undermines the value of the tool for those files without content-based matching.

This is arguably the most important design problem for gtfs-diff-engine to solve

[davidgamez]

timebox: 2d

[emmambd]

Have @tzujenchanmbd and @skalexch been consulted on this one? I'd be curious about their takes on the Copilot generated table above.

[skalexch]

@emmambd I remember having some worries about this specific issue, mainly:
With no consistent primary key values to follow, the tool will not be useful for those feeds that change ids frequently. It will show a mix of removed and added rows that might essentially be just modified values. From my experience, route_ids can be unstable, and they are the worst to handle if they change. We might want to limit the display of changing shape_ids. We could mention the id that changed if the changes in coordinates are minimum.

For routes, we might explore avenues where the route id changes but the route long name is the same. But that's a v2 of the Diff tracker.

[emmambd]

As discussed earlier with @skalexch, I think the goal will be to provide pilot test users with a set of heuristics that work for them, even if it might not address other edge cases or cases outside their needs. For this reason, I think testing out relying on route_long_name for example, makes sense, rather than producing a diff report that they can't use easily to monitor route changes.

[ianktc]

For something like shapes, perhaps the best way to detect diffs is actually to actually compare the geojson of the generated shapes... but its most likely too costly... Is it something to put behind a membership?

[emmambd]

@ianktc I don't know if it's high value enough, but interesting consideration!

[jcpitre]

What we are doing:

• Establish how prevalent generated ids are in the feeds we have
• Add a way to determine if a given dataset has generated ids so we can just not process it. See Add a heuristic that tells if the standard diff is possible #5

One thing is sure, we will not be able to stay generic in the processing, meaning that all files and all fields will not be treated equally.
For example, for shapes, the files that is most likely to have generated ids according to AI, we can do what @ianktc is suggesting. We treat each shape as a polyline and use geometric proximity algorithms to determine the correspondence between a shape in the base dataset and a shape in the new dataset.
I know that this is not a priority. But we already tried the algorithm with success.

[cka-y]

🚦 MVP diff heuristic: skip files with unstable IDs

Full results: interactive report · raw JSON

We ran a primary key stability analysis across 2,502 feeds (all 29 GTFS file types, two consecutive versions per feed). The goal was to answer: for which files does diffing actually produce meaningful output?

---

The proposed heuristic

Per file: if the Jaccard similarity between the two versions of a file is below 0.5, skip the row-level diff for that file and emit status: id-unstable instead. All other files in the same feed are diffed normally.

This is a per-file decision, not a per-feed one. If calendar_dates.txt has a Jaccard of 0.3 but stops.txt has a Jaccard of 0.99 in the same feed, we skip calendar_dates.txt and still produce a full diff for stops.txt. The consequence of not having this heuristic is a diff output full of phantom deletes and inserts that look like real changes but are just an artifact of the provider regenerating their IDs.

---

What is Jaccard similarity and why use it?

Jaccard similarity answers: "out of every ID we've seen across both versions, what fraction appear in both?"

Jaccard = (IDs in both versions) / (all unique IDs across both versions)

Concrete GTFS example: if version A has service IDs {MON, TUE, WED} and version B has {TUE, WED, THU}, Jaccard = 2/4 = 0.50. If a provider regenerates all IDs and version B has {SVC_1, SVC_2, SVC_3}, Jaccard = 0/6 = 0.0 even if the actual schedule is identical.

Why Jaccard and not something simpler? The obvious alternative is the overlap ratio (shared IDs / previous IDs), but it only looks in one direction. If a provider keeps all their old stop IDs and adds 10,000 new ones, overlap = 100% but Jaccard is low, correctly flagging that most of the new file is unrecognisable. Jaccard penalises both "old IDs disappeared" and "new IDs appeared", which is exactly what matters for deciding whether a diff is trustworthy. It is also symmetric, bounded between 0 and 1, and cheap to compute on large sets. See the this explanation on set similarity for more background.

Why 0.5 as the threshold? Below 0.5, more IDs are unique to one version than are shared. The diff output would be majority noise. Above 0.5, there are enough stable anchors that row-level comparison is meaningful. This is the natural midpoint of the [0, 1] range and is the same boundary used in document deduplication and clustering literature to separate "same thing" from "different things".

---

What the data shows

File	Feeds	Median Jaccard	Feeds where heuristic fires
calendar_dates.txt	2,256	0.60	~900 (~40%)
stop_times.txt	2,368	1.00	~400 (tail only)
trips.txt	2,413	1.00	~430 (tail only)
shapes.txt	2,118	1.00	~210 (tail only)
All other 25 files	varies	1.00	fewer than 85 each

calendar_dates.txt is the main offender: its median Jaccard across all feeds is already 0.60, meaning the typical feed is close to the threshold, and a large chunk of feeds fall well below it. For every other file type, the median is a perfect 1.0, which means the heuristic only fires for outlier feeds, not as a general rule.

For the 25 stable file types, this heuristic changes nothing in practice.

---

What the output could look like when the heuristic fires

{
  "file": "calendar_dates.txt",
  "status": "id-unstable",
  "jaccard": 0.21,
  "ids_added": 9840,
  "ids_removed": 9731,
  "detail": "ID turnover too high for a meaningful row-level diff. Treat as full replacement."
}

The add/remove counts are still surfaced (useful for monitoring feed size changes) but we do not produce a row-level diff that would be misleading.