Indexing spatiotemporal trajectory data streams on key-value storage

In a trajectory management system, moving objects are typically equipped with GPS devices to report their locations to a data store. Given the potentially high frequency of location updates by multiple moving objects, these data stores often operate under write-intensive conditions. Existing trajectory indexing methods, such as XZ-ordering, which are geared towards static trajectory data, may experience considerable latency under such demanding workloads. In response, this paper introduces spatio-temporal index structures that can be constructed with low latency. Trajectories are categorized into two types for storage: ‘live’ and ‘static’. Live trajectories are indexed by the Dual-Key Encoding (DKE) scheme, where each data point is represented by two key-value entries, facilitating both ID-temporal and spatial queries. Static trajectories, on the other hand, offer a more compact storage solution, reducing the overhead associated with live trajectories. Upon the completion of a trip, live trajectory data is transformed into a static trajectory entry through a compaction process. To augment the efficiency of spatial index construction for static trajectories, we introduce a new encoding scheme, XS2, coupled with an adaptive segmentation policy, AdaptSeg, to optimize trajectory segmentation, thereby enhancing index building and query processing efficiency. The indexing methods are demonstrated atop of LevelDB, an LSM-based key-value storage library, resulting the proposed LevelDB^ST system. Performance evaluations conducted using both synthetic and real-world datasets reveal that LevelDB^ST is capable of constructing spatial indexes for continuously updating trajectories with reduced latency, in comparison to traditional XZ-ordering methods. This efficiency is achieved while maintaining an acceptable balance in data accessing time and storage costs. © The Author(s), under exclusive licence to Springer-Verlag GmbH Austria, part of Springer Nature 2024