PaIndex: An online index system for vehicle trajectory data exploiting parallelism

The rapid development and adoption of location-acquisition and mobile sensing technologies have enabled the tracking of vehicle movement. Massive trajectory data are collected and uploaded to central servers continually in IOV (Internet of Vehicles) scenario, and many IOV applications such as traffic congestion management have range query demands to these data. How to make these queries efficient is a critical and challenging problem. Most existing studies or systems generally put all the entries together when building index, which is not suitable for concurrent access and results in low index insert performance as well as high query latency. And in fact, many applications are characterized as only need the most recent data, it is unnecessary for the index system to manage all the data. So in this paper, we design an online index system for vehicle trajectory data, named PaIndex. Through partitioning technique that maintains data locality, PaIndex can significantly reduce the time cost of range query and support high insert throughput by parallel operations. Taking the advantage of large memory available in modern machines, we maintain the trajectory data and its corresponding index of the past several days in memory, and older ones are kept in disk. Firstly, our index is organized as regular partitioned grids and a temporal index is maintained under a grid if there are data inside that grid. Secondly, to further reduce cost we proceed to partition the temporal index as Time Range Buckets. Finally, in each Time Range Bucket, we index the data with a B+ tree. By this multi-level partitioning technique, we can process insertions or queries between grids or Time Range Partitions in parallel. The experiments conducted on the real-world IOV dataset demonstrate the effectiveness and efficiency of our method.