Certified Fréchet Search with Coarse-to-Fine Couplings

Learned trajectory embeddings make nearest-neighbor search fast: each GPS track becomes one vector, and a vector index returns similar tracks in microseconds. These embeddings are also wrong often enough to matter. On standard taxi datasets they miss roughly 30% of the true 50 nearest neighbors. Exact algorithms for the Fréchet distance have the opposite profile. The Fréchet distance is the shortest "leash" that lets a person and a dog walk two curves forward without backtracking, and exact algorithms for it are correct but cost quadratic time per pair. This proposal joins the two. The embedding never answers the query by itself. Its job is to cheaply nominate candidates whose distance we can then bound from above. A coarse-to-fine alignment module, borrowed from optical-flow estimation, turns each candidate into a certified upper bound. That bound sets a tight search threshold. A cheap indexable lower bound and an exact Fréchet decider then finish the search with a guarantee.

In two sentences: any forward-only matching between two curves gives a valid upper bound on their Fréchet distance. A pyramid network can produce such matchings cheaply from per-trajectory features cached offline. Feeding those bounds as thresholds into an exact decider should give exact or certified-approximate kNN search at close to embedding speed. What is new is the role hierarchical motion estimation plays. It is a pairwise certificate generator inside a provably correct search, not part of the embedding.

Why the obvious combination is the wrong one

The tempting idea is "PWC-Net for trajectory embeddings." The proposal does not pursue it, because warping is a pairwise operation. PWC-Net and LiteFlowNet work as follows:

  • They downsample features into a pyramid.
  • They warp the second image toward the first using the coarser motion estimate.
  • They search only a small local window for a residual correction.

The warp needs both inputs. An embedding that depends on the comparison partner can no longer be precomputed and indexed. That destroys the constant-time property.

The existing trajectory models that sit closest to this intersection all stay inside the single-vector regime:

  • Revisiting CNNs for Trajectory Similarity Learning (ConvTraj) shows that local 1D/2D convolutions match or beat Transformers. Trajectory similarity is mostly local alignment, so this result motivates our local-window design. Its fixed pooling cannot handle large index offsets.
  • SIMformer shows that the Chebyshev (ℓ∞, maximum per-coordinate difference) distance suits Fréchet distance, because both are worst-case quantities. We reuse that target. Its full self-attention, however, is quadratic in curve length.
  • HiT-JEPA builds a point/segment/route hierarchy, but it only uses top-down attention weighting.

None of the three can say whether a returned neighbor is actually correct. That limitation is what Trajectory Similarity Measurement: An Efficiency Perspective quantifies with its Hit Ratio@50 below 0.7.

The other camp is exact algorithm engineering. Walking the Dog Fast in Practice answers "is the distance at most δ?" exactly. It does this by divide-and-conquer over the free-space diagram, a grid recording which point pairs lie within δ, combined with greedy filters. It reports up to 30x faster near-neighbor queries. Its cost is acutely sensitive to how good δ is, and that is exactly what a learned stage can supply.

Core Claim

Let $A=(a_1,\dots,a_n)$ and $B=(b_1,\dots,b_m)$ be curves. Let $C$ be any coupling: a sequence of index pairs from $(1,1)$ to $(n,m)$ that never decreases in either index. Then two inequalities hold:

$$\max\big(\|a_1-b_1\|,\ \|a_n-b_m\|\big)\ \le\ d_F(A,B)\ \le\ \max_{(i,j)\in C}\|a_i-b_j\|.$$

The right side holds for the discrete Fréchet distance by definition. It also holds for the continuous Fréchet distance, which never exceeds the discrete one. The left side holds because every coupling must match the two start points and the two end points.

The lower bound is a max of two Euclidean norms on a fixed 4D endpoint vector. It is therefore indexable for range queries.

Our claim is about the upper bound. A coarse-to-fine network with a small local search window produces couplings whose bound is close to the true distance. It does so at a cost linear in curve length, and it reads per-trajectory features computed offline. Using the $k$-th smallest bound among embedding-retrieved candidates as the threshold $\tau$ shrinks the set that must reach the exact decider. That set is the trajectories whose lower bound is at most $\tau$. The result is exact kNN that should be several times faster than the exact decider's own near-neighbor search.

This design makes a known weakness of pyramids harmless. Error propagation across scales is the standard failure of coarse-to-fine motion estimation. Here a bad coarse match only loosens a bound and costs time. It can never produce a wrong answer.

The hierarchy also solves a receptive-field problem that is specific to trajectories. Two GPS traces of the same route sampled at different rates have corresponding points hundreds of indices apart. That is the 1D analogue of a large optical-flow displacement. A pyramid reduces that offset to a few indices at the coarsest level, so a radius-$r$ local window suffices at every level. Global context comes from the hierarchy rather than from quadratic attention or the multi-pass sweeps of CCNet.

Research Program

Offline encoding. Each database trajectory is encoded once by a 1D convolutional pyramid. Strided residual convolutions, in the style of ConvTraj, produce feature sequences at lengths $n, n/2, \dots, n/2^L$. Two outputs are stored:

  • a pooled ℓ∞ embedding, trained with SIMformer-style pairwise regression to Fréchet distance;
  • the features of the two or three coarsest levels.

We will report the storage cost of these cached features explicitly. It is the price paid for avoiding the per-pair "encoding tax" identified in the efficiency study.

The coupling module. At query time the module runs on cached features.

  • At the coarsest level it computes a full correlation between the two short sequences. This is cheap at length $n/2^L$. A soft forward-only alignment reads an index-offset field off that correlation.
  • At each finer level it upsamples the offset field and warps $B$'s features along the index axis by linear interpolation.
  • It builds a partial cost volume, the correlations within radius $r$, as PWC-Net does. A small 1D network then predicts residual offsets.
  • A running maximum forces monotonicity. Rounding yields a valid coupling on the raw coordinates.

Training uses two objectives. The first imitates the optimal coupling recovered by dynamic programming. The second minimizes a smooth-max of matched-pair distances, which directly tightens the bound. Two adaptive refinements are tested. One widens $r$ only near the matched pair that attains the maximum. The other refines only candidates whose bound is near $\tau$.

The search pipeline. A query proceeds in four steps:

  1. Encode the query once.
  2. Retrieve the top-$K$ candidates under ℓ∞ from a vector index.
  3. Compute coupling bounds for those candidates and set $\tau$.
  4. Range-query the endpoint index for every trajectory with lower bound at most $\tau$, and pass those through the exact decider's filters and decider at threshold $\tau$, lowering $\tau$ as better bounds appear.

Stopping after step 3 gives an approximate mode. In that mode every returned result carries a certified upper bound and a gap to the lower bound.

Baselines

Naive exact reference. A linear scan applying the Walking the Dog Fast in Practice decider to every database curve. This anchors correctness and the worst-case cost.

Strongest exact competitor. The same paper's near-neighbor search, which it reports improves query times by up to 30x on GeoLife (17,000 trajectories). It is the strongest competitor because it is exact, engineered, and already uses greedy upper bounds and triangle-inequality filters. We run the authors' algorithm on the same CPU/GPU budget with its default and best-tuned filter settings. Beating it means two things: identical exact answers, and lower median and 95th-percentile query latency, both measured including query encoding, on GISCUP 2017 and GeoLife.

Strongest approximate competitor. SIMformer, whose reported figure is a hit rate above 50% in 1M-trajectory tests. Alongside it we run ConvTraj and HiT-JEPA. For Fréchet hit ratios of these two, no reported result found on Lacuna. HiT-JEPA reports only a relative gain of up to 12.6% over T-JEPA. We also add an "embedding + exact rerank of top-$K$" variant of SIMformer. All learned models are retrained on the same training split, with the same Fréchet ground truth and the same hyperparameter search budget. Beating them means higher recall@k at matched latency in approximate mode, plus certified gaps they cannot provide.

Hashing. FRESH is included as the non-learned approximate reference, tuned to its best recall/latency setting.

Ablations. Three ablations isolate the key ingredient:

  • Replace the learned coupling with the greedy coupling bound already used inside the exact decider's filters.
  • Replace it with a classical multiresolution coupling: exact dynamic programming on Douglas-Peucker-simplified or downsampled curves, then banded refinement.
  • Remove the embedding and seed $\tau$ from the endpoint-lower-bound order alone.

Why not just…?

Why not just run the exact decider's near-neighbor search? It is exact and fast, and it is the main threat. Its weakness is the threshold. Until a good δ is found, many curves survive filtering, and the 100x speedup over the GIS Cup winner reported in that paper is an "up to" figure on real curves, not a worst-case guarantee. The decisive measurement is the number of decider calls and the wall-clock time per query with and without our seeded $\tau$. If the decider's own greedy bounds already find near-optimal thresholds, the ablation that seeds $\tau$ from greedy couplings will show it, and the gain will vanish.

Why not just simplify curves and run classical dynamic programming coarse-to-fine? This is the alternative most likely to match our learned module. Dynamic programming at length $n/2^L$ is cheap, and simplification error is bounded through the triangle inequality, although Fréchet Edit Distance cautions that naive simplification can discard decisive turning points. We therefore treat the coupling module as swappable and report bound-gap distributions and per-candidate latency for both. If classical couplings are as tight and as fast, we adopt them. The certified retrieve-then-decide pipeline remains the contribution. The learned module must earn its place on stress cases: mismatched sampling rates, GPS noise, and long curves where coarse dynamic programming in pure Python is not GPU-batched.

Why not just use better embeddings with a larger reranking set? Reranking cannot recover a true neighbor that the embedding never retrieved. The efficiency study reports Hit Ratio@50 below 0.7, so misses are common. Our pipeline catches them through the lower-bound range query. We will report how many final exact neighbors came from outside the top-$K$ as the direct evidence.

Why not use hashing such as FRESH? FRESH still relies on cascaded exact verification without a learned threshold. The file's evidence, from SIMformer and from the hashing papers themselves, is that sketch precision degrades with noise and varying sampling. We include FRESH on identical data, so this is settled empirically rather than assumed.

Proposed Experiments

Ground truth is the exact continuous Fréchet distance. The datasets serve four purposes:

  • GISCUP 2017 (20,199 curves of 9–767 vertices) for exact-search experiments.
  • GeoLife for direct comparison with the exact decider's near-neighbor numbers.
  • Porto (1.6M trajectories), on a subset where exact verification is affordable, for scaling.
  • AIS and T-Drive for free-space and irregular sampling.

The first decisive check is tightness. We plot the ratio of coupling bound to true distance for learned, greedy, and classical couplings. This is broken down by curve length and by a sampling-mismatch stress test in which one curve of each pair is resampled at two to four times the density. That resampling creates large index offsets. A single-level local-window variant of our network should fail on these pairs while the pyramid should not, which is the receptive-field claim.

The second check counts how many trajectories pass the lower-bound filter at threshold $\tau$, and how many decider calls follow, against the exact near-neighbor baseline.

The third check is end-to-end exact kNN latency for $k\in\{1,10,50\}$ as database size grows. Query encoding and cached-feature I/O are included, so the encoding tax is counted honestly.

The fourth check is the recall–latency curve in approximate mode against SIMformer, ConvTraj, HiT-JEPA and FRESH, with the fraction of results whose certified gap is below 1%, 5% and 10%.

The proposal fails if the seeded threshold does not reduce decider work relative to the exact baseline's own greedy bounds. It is narrowed to a non-learned pipeline if classical multiresolution couplings match the learned ones on the stress test.