REST Framework Speeds Real-Time Semantic Trajectory Joins on Distributed Streams

Streaming trajectory data has become one of the defining data-management challenges of the mobile era. Drones upload GPS coordinates alongside mission tags and environmental annotations, while social platforms and map services receive a continuous flood of geo-tagged posts enriched with captions, hashtags and sentiment. A new open-access study published in Data Science and Engineering on 11 June 2026 introduces REST, a distributed framework designed to answer a deceptively simple question at millisecond speed: which of these moving trajectories are similar to each other right now, in both where they go and what they mean?

The problem, formally called Online Semantic Trajectory Similarity Join, or OSTS-J, takes two streams of semantic trajectories, a similarity threshold and a sliding time window, and returns every trajectory pair within the current window whose distance falls below the threshold. Unlike offline joins that analyse trajectories over their full lifespan, the online setting processes only points uploaded within a recent window, discarding outdated ones as new points arrive. The authors argue this distinction matters for applications such as real-time route planning and travel itinerary suggestions, where stale results are of little use.

Measuring similarity across both domains required a purpose-built distance function. The framework adopts the shape-based Fréchet distance, a measure the authors selected because common point-based trajectory measures such as DTW, LCSS and ERP are sensitive to user-defined parameters that vary with sampling rate, and because representation-learning alternatives carry inference latencies incompatible with real-time requirements. In REST, the Euclidean term of the Fréchet distance is replaced with a spatial-semantic distance that blends normalised spatial distance and Jaccard text distance through a preference weight alpha, letting users control how much the spatial versus textual domain matters.

REST is built on Apache Flink, a parallel stream-processing framework, and organised around a two-phase KeyBy-Union mechanism guided by the principle of deferring computation until necessary. Incoming points are first routed by device identifier to sub-tasks that maintain spatial-semantic summaries through an incremental clustering method called DISC-S, an extension of an existing incremental DBSCAN technique adapted to the spatial-semantic distance. Each summary packs a minimum bounding rectangle together with merged and shared text summaries, capturing how the points of a single trajectory relate to one another within the current window.

The first KeyBy-Union phase distributes these summaries across an adaptive cell space and maintains a two-layer structure called the AIR-index, which combines a global adaptive cell index with a local IR-Tree inside each cell. A three-level pruning strategy, operating at the cell level, at non-leaf tree nodes and at leaf nodes, exploits lower bounds derived from the summaries to eliminate trajectory pairs that cannot possibly satisfy the threshold. Only surviving candidate pairs travel downstream, which simultaneously cuts computation and limits the intermediate state the system must store in memory.

The second KeyBy-Union phase refines the surviving pairs with an enhanced incremental computation method the authors call Inc++. When a new point arrives and no points have expired, the framework extends the previous Fréchet distance matrix rather than recomputing it from scratch, reducing per-update cost from quadratic in trajectory length to linear. A lazy-update rule halts calculations early once row minima exceed the threshold, and a distance matrix cache with a time-to-live setting reuses previously computed spatial-semantic distances when expiring points would otherwise force full recalculations.

Load balancing receives its own treatment. Because points of interest cluster densely in urban cores and sparsely elsewhere, fixed grid partitions leave some computing slots overloaded while others idle. The authors formalise optimal load-balancing partitioning as minimising the variance of computational cost across cells, prove the problem NP-hard by reduction from load matrix partitioning, and propose a heuristic adaptive cell partitioner. It uses a cost model estimating how many points each arrival will touch, based on keyword frequency distributions, and a machine-learning partitioning strategy trained on pre-sampled points, producing smaller cells in dense regions and larger ones elsewhere.

The experimental evaluation ran on a 28-node cluster, each node with an 8-core Intel processor, 64 GB of RAM and Flink 1.18.0, across four real-world datasets. Three of them, taxi trajectory sets from Beijing, Chengdu and Shanghai, were enriched with textual information by mapping each trajectory point to its nearest point of interest from Amap data, while a fourth derived from a real semantic trajectory dataset was augmented with additional points to raise its sampling rate. The datasets ranged from roughly 5.5 million to 15 million trajectory points.

The headline results are striking. Under default settings, REST reduced latency by 94.92 percent on the Beijing dataset and 97.24 percent on the Chengdu dataset compared with state-of-the-art baselines, while improving throughput by factors of 18.8 and 35.6 respectively. Memory usage per slot fell by 96.9 percent and 93.7 percent relative to the Ghost baseline on the Beijing and Chengdu datasets, a property the authors link to resilience against single points of failure in distributed systems. The adaptive partitioner also cut the average standard deviation of slot computation costs by up to 47.9 percent and its variance by up to 81.76 percent on the Beijing dataset.

The authors are careful to note where the framework is less dominant. On the smaller Shanghai and augmented datasets, baseline latencies were lower and REST’s advantage narrowed, an effect they attribute to points uploaded simultaneously tending to originate from the same device, which concentrates work in fewer processing slots regardless of pruning quality. Component-level measurements showed incremental clustering cost was negligible, under 0.05 percent of latency, while the main overhead split between index maintenance and refinement. The framework also relies on lower-bounding pruning that guarantees correctness only for distance measures satisfying the triangle inequality, so non-metric measures would need specific lower-bounding approximations. Within those bounds, the study presents REST as a demonstration that deferring computation, at both global and local levels, can make semantic trajectory joins practical at streaming scale.

Subject of Research: A distributed framework for real-time similarity join over streaming semantic trajectory data.

Article Title: REST: An Efficient Distributed Framework for Real-time Semantic Trajectory Join

Article References: Luo, Y., & Chen, J. (2026). REST: An Efficient Distributed Framework for Real-time Semantic Trajectory Join. Data Science and Engineering. https://doi.org/10.1007/s41019-025-00344-4

Image Credits: AI Generated

DOI: 10.1007/s41019-025-00344-4

Keywords: trajectory similarity join, semantic trajectories, stream processing, Apache Flink, distributed computing, load balancing, spatial-semantic distance, incremental computation, AIR-index, real-time data analysis, REST, Efficient