When a vehicle is tracked live, the only part of its path that matters for most decisions is the part that just happened: the turn it just took, the detour it just started. Modern trajectory encoders are neural networks that compress a GPS path into a single vector so that similar paths can be found quickly. They are trained on completed trips and read the path from start to end. In text retrieval, encoders of this kind are known to suffer from lead bias: the vector is dominated by the opening of the input, and evidence placed later is underweighted. In a live stream, the newest pings sit at the end of the sequence, which is exactly where a lead-biased model looks least. We propose to measure this failure for trajectories and to test a cheap alternative that has no notion of position. That alternative represents a live trajectory as a weighted sum over the road segments and directed turns it has used. Each weight comes from how structurally central that segment is in a continuously updated graph of fleet-wide movement. The representation updates in constant time per ping and cannot favour the start of a trip, because it never sees positions.
This matters because streaming systems work under deadlines that rule out the usual text-retrieval fix for lead bias, which is to re-score candidates with a heavy model that reads the query and the candidate jointly. Online anomalous-subtrajectory detection targets under 0.1 ms per incoming point (Online Anomalous Subtrajectory Detection on Road Networks with Deep Reinforcement Learning). Routing that depends on retrieved history needs sub-100 ms answers (Value Creation from Massive Data in Transportation ? The Case of Vehicle Routing).
Core Claim
We make two claims, and each can fail independently. The first is diagnostic. Trajectory encoders trained on whole trips will retrieve a trajectory much less reliably when the matching evidence lies in its middle or end than when it lies at its start. They will also be fooled by distractors that merely share the target's origin. These are the same two failure patterns documented for text: An Empirical Study of Position Bias in Modern Information Retrieval reports a 15.6% average drop for dense and late-interaction retrievers when evidence moves later, and a Position Sensitivity Index (PSI, a normalized measure of how much retrieval quality varies across evidence positions) of 0.499 for jina-colbert-v2. Collapse of Dense Retrievers shows that dense retrievers prefer early-keyword foils over true evidence more than 90% of the time.
The second claim concerns the method. A position-free, additive representation weighted by streaming graph degeneracy will close most of that gap at a small fraction of the per-ping cost. Graph degeneracy is a measure of how deeply a node sits inside densely interconnected parts of the graph. On the same data, this representation should also beat simpler position-free weightings, namely uniform weights, frequency-based weights, and PageRank-style prestige. The second comparison is where the proposal could turn out to be unnecessary, and the experiments are designed to settle it.
Concretely, let $S_t(\tau)$ be the multiset of map-matched road segments and directed segment-to-segment transitions that trajectory $\tau$ has produced up to time $t$. Let $e_s$ be a fixed embedding for each segment or transition, and let $c_t(s)$ be its core number in the fleet transition graph over the last time window. The representation is
$$v_t(\tau) = \sum_{s \in S_t(\tau)} g\big(c_t(s)\big)\, e_s ,$$
where $g$ maps core numbers to weights. A new ping adds at most one segment term and one transition term, so an update costs $O(d)$ in the embedding dimension $d$, whatever the trajectory's length. The transition terms keep local direction, including one-way streets and turn order, without encoding absolute position. This is our answer to the objection that graph centrality ignores chronology.
Research Program
The first component is a trajectory analogue of the positional retrieval benchmarks, which we call Traj-PosQ. It follows the design of SQUAD-POSQ and FINEWEB-POSQ in An Empirical Study of Position Bias in Modern Information Retrieval. From Porto and Chengdu trips we draw a short query sub-trajectory from one of six positional buckets of a target trip. We then ask each encoder to retrieve the target from a large database. Reporting Recall@k per bucket and the PSI gives a direct cross-domain comparison with the text numbers.
The benchmark also carries a foil test built in the style of ColDeR (Collapse of Dense Retrievers). Each target is paired with a foil trip that shares the target's first third but never traverses the query's segments. We measure how often the foil outranks the target. A streaming variant then replays trips ping by ping and scores retrieval against the growing prefix. The quantity of interest there is how quickly the correct neighbours appear after the vehicle diverges from a common route.
The second component is the representation itself. For segment embeddings we reuse structure-only embeddings. The primary choice is a node2vec-style embedding of the road graph, as in the Efflex-L backbone of Efflex. We also test the road-segment modality encoder of OmniTraj as an alternative, so that differences reflect weighting rather than embedding quality.
The fleet transition graph is directed, with a node per segment and edges weighted by transition counts within a sliding time window. It is maintained with localized updates. The degeneracy machinery comes directly from Degeneracy-Based Real-Time Sub-Event Detection in Twitter Stream, which maintained a sliding-window graph over tweets and used core numbers of the top words as its signal. On the 2014 World Cup stream it reached a micro-F1 of 0.68 against 0.54 for frequency counting. That gap is the empirical reason to expect degeneracy to carry information beyond frequency. The use of $k$-cores to extract the thematic nucleus of a document follows GoWvis.
Both of these prior systems work on word co-occurrence and never face road topology or directed kinematics. Both also treat high-core nodes as salient. For retrieval we do not assume that the central segments are the discriminative ones. Arterials may sit in the dense core and be shared by everyone, which would make them uninformative for telling trips apart. We therefore treat the direction and shape of $g$, whether it increases or decreases with core number, as something to fit on a validation split. It is chosen from a small monotone family, so the weighting stays essentially unsupervised.
The third component is analysis. We will characterize which segments receive high weight: intersections, detours, neighbourhood exits. We will also test whether weights computed on the live window help more than weights from a static historical graph. If they do, it would indicate that current traffic structure, not just map structure, determines what is distinctive.
Baselines
The naive reference point is the same additive representation with uniform weights, that is, a plain bag of segments and transitions. It is position-free and just as fast, so any gain from degeneracy weighting must be measured against it rather than against neural encoders. A second naive point is exact Hausdorff or Fréchet distance computed on the query. It is position-robust by construction but scales quadratically (Spatio-Temporal Trajectory Similarity Measures). We use it as an accuracy ceiling and as the stand-in for a heavy rescoring stage, since the file describes no trajectory cross-encoder.
The strongest existing encoders are OmniTraj and Efflex. OmniTraj encodes GPS points, geometry, road segments and regions into one contrastive space and reports an MRR of 0.909 on Chengdu, against 0.846 for TrajCL. Efflex reports Recall@50 of 99.84% under Hausdorff distance on Porto for Efflex-L. It also reports that Efflex-B, the lightweight graph-convolution variant, stays within 1–3% of that accuracy while extracting embeddings up to 36 times faster. Efflex-B is the most relevant competitor on latency.
We will run released or reimplemented versions on identical train and database splits. For each streaming query, every system re-encodes the full current prefix. Each system receives the same hyperparameter search budget and the same hardware. Beating these baselines means two things. On the middle and end buckets of Traj-PosQ, our method must match or exceed their Recall@50 while keeping PSI below theirs. It must also stay within a few points of them on the standard full-trajectory benchmarks where they report the numbers above, all at lower per-ping cost. Traj-PosQ numbers do not yet exist for any of these models; no reported result found on Lacuna for position-bucketed trajectory retrieval.
The key ablations isolate the weighting. Degeneracy weights will be compared against inverse-frequency weights, which are IDF-like and count how many trips use a segment. They will also be compared against degree weights, PageRank weights in the style of LexRank, and uniform weights. Further ablations compare live-window graphs with static graphs, and runs with and without the directed transition terms. The argument in Graph Centrality for Unsupervised Content Selection and GoWvis is that prestige measures are misled by hub nodes. The degree and PageRank ablations test whether that argument carries over to roads.
Why not just…?
Why not just train the encoder with random sub-trajectory crops so it stops favouring the start? This is the most serious threat to the diagnostic claim. Crop-based contrastive augmentation may well remove most of the positional gap. We will train OmniTraj-style and Efflex-B encoders with aggressive random cropping and report their Traj-PosQ curves. If augmentation flattens PSI, we will say that lead bias in trajectories is cheaply fixable at training time. Even then, an augmented encoder still has to re-encode the growing prefix on every ping. The comparison that remains is therefore latency at matched accuracy, and the proposal would stand or fall on that.
Why not just use an unweighted or inverse-frequency bag of segments, like BM25 over road IDs? The research file argues that exact matching fails because of GPS noise. That argument weakens once pings are map-matched to discrete segments with real-time matchers such as Map Matching and Lane Detection Based on Markovian Behavior, GIS, and IMU Data. This alternative is therefore a genuine competitor, and it shares our speed and position-freedom. The only evidence that degeneracy should do better is indirect: core numbers beat frequency 0.68 to 0.54 on text streams (Degeneracy-Based Real-Time Sub-Event Detection). If the inverse-frequency ablation matches degeneracy weighting on Traj-PosQ, the contribution shrinks to the diagnostic plus the observation that position-free additive codes suffice. We would report that plainly.
Why not just rescore the top candidates with an exact geometric distance? Joint rescoring is how text retrieval escapes lead bias; cross-encoders reach PSI below 0.03 in An Empirical Study of Position Bias. Rescoring cannot recover a target that the first stage never retrieved, however. The foil test measures exactly how often lead-biased first stages drop the target, mirroring the more-than-90% foil preference in Collapse of Dense Retrievers. We will run neural-first-stage plus exact-rescoring pipelines and report both recall and per-ping latency against the 0.1 ms target.
Why not just downsample or evaluate fixed recent windows? A window over only the last few minutes removes lead bias by discarding the lead. It also discards the context that distinguishes, say, two trips that share a recent arterial. We include last-$w$-minutes encodings and uniform decimation as baselines in the streaming variant.
Proposed Experiments
The main experiments use Porto and Chengdu for Traj-PosQ and the streaming replay. Xi'an serves as a zero-shot transfer test, since OmniTraj reports strong transfer there without a number in the file. AIS vessel data tests whether the idea survives without a road network, using grid cells as nodes.
Three results would be decisive. First, per-bucket Recall@50 and PSI for the strongest encoders, including crop-augmented versions: does trajectory lead bias exist and persist? Second, the head-to-head of degeneracy weights against inverse-frequency weights on the middle and end buckets and on foil rate: does centrality add anything beyond counting? Third, median and tail per-ping update latency against Efflex-B re-encoding at matched Recall@50: is the position-free representation fast enough to matter?
Each of these can falsify one claim without falsifying the others. That is why the program stays informative even under the weakest outcome, in which neural encoders show little bias or frequency weighting suffices.
References
- Online Anomalous Subtrajectory Detection on Road Networks with Deep Reinforcement Learning
- Value Creation from Massive Data in Transportation ? The Case of Vehicle Routing
- An Empirical Study of Position Bias in Modern Information Retrieval
- Collapse of Dense Retrievers: Short, Early, and Literal Biases Outranking Factual Evidence
- Efflex: Efficient and Flexible Pipeline for Spatio-Temporal Trajectory Graph Modeling and Representation Learning
- Learning Generalized and Flexible Trajectory Models from Omni-Semantic Supervision
- Degeneracy-Based Real-Time Sub-Event Detection in Twitter Stream
- GoWvis: A Web Application for Graph-of-Words-based Text Visualization and Summarization
- Spatio-Temporal Trajectory Similarity Measures: A Comprehensive Survey and Quantitative Study
- LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
- Automatic Generation of Personalized Annotation Tags for Twitter Users
- Map Matching and Lane Detection Based on Markovian Behavior, GIS, and IMU Data