Beyond Locations: A Motion Range-Aware Similarity Join

With the proliferation of GPS-enabled devices such as smartphones, the querying of moving objects has attracted substantial attention, with studies covering joins, range and kNN queries, similarity queries, etc. Challenges arise due to variable sampling frequencies, potential inaccuracies in location samples, and the unavailability of locations between samples. Existing similarity joins often rely on discrete location samples, which fail to capture movement uncertainty and may miss meaningful interactions. To address this limitation, we propose Intersection Similarity Join (IS-Join), a novel approach that identifies object pairs based on the overlap of their motion ranges rather than location-based proximity. We define motion ranges as the spatial regions an object may traverse within a given time period, and introduce an intersection similarity measure that quantifies their overlap. To efficiently process IS-Join queries, we develop a Hybrid Ball-tree indexing structure with a repartitioning strategy, enabling scalable candidate filtering. Additionally, we introduce pre-checking and pruning techniques to further reduce computational overhead. Extensive experiments on two real-world trajectory datasets demonstrate that IS-Join significantly outperforms well-designed baselines, achieving up to a 3x reduction in runtime. Our work opens new opportunities for applications such as urban mobility analysis, traffic monitoring, wildlife tracking, and contact tracing.