Five results: I spent time proving splines don’t help trajectory databases

Description and use

Cubic B‑splines do not beat polylines for GPS trajectory storage or similarity search, but certified Fréchet distance bounds enable exact range queries with zero misses and false positives, achieving 20 ms median latency and 2× smaller disk footprint.

Problem

Determining whether cubic B‑splines provide a more compact, accurate, and searchable representation of GPS trajectory data compared to traditional polyline simplification methods.

Outcome

Splines do not outperform polylines for trajectory storage or similarity search under realistic conditions. However, certified Fréchet distance bounds for both representations enable exact range queries with zero misses and false positives, achieving 20 ms median latency and 2× smaller disk usage compared to exact competitors.

Workflow

• 1. Collect 200 GeoLife tracks and split into 585 trips at gaps >30 s or impossible speeds.
• 2. Fit cubic B‑splines to each trip using least‑squares on x(t), y(t) without tethering to polyline control points.
• 3. Verify spline accuracy on a dense grid; enforce error tolerance at every point, not just sample points.
• 4. Compare compactness and recall@10 for Fréchet search against DP and DP+SED (time‑aware DP).
• 5. Build an oracle by fitting splines directly to the true (noise‑free) curve to separate representation quality from fitting quality.
• 6. Implement certified Fréchet distance bounds: compute control‑point convex‑hull capsules and derive upper bounds for each spline segment.
• 7. Perform large‑scale evaluation: 585 tracks, 1 000 queries, 6 million query‑candidate pairs; measure misses, false positives, and query latency.
• 8. Analyze trade‑offs: storage vs. candidate pruning ratio; quantify cost of dropping guarantees.
• 9. Document measurement bugs and fixes to ensure reproducibility.
• 10. Publish code, reports, and DOI for transparency.

Evidence

Zero misses and zero false positives against full brute force on the source data.

Certified Fréchet distance obeys the triangle inequality, enabling range queries without reading originals.

The price of dropping the guarantee, measured: approximate search loses 0.03% to 3.03% of correct answers and returns up to 2.04% false positives.