Efficient Path Query Processing over Massive Trajectories on the Cloud

A path query aims to find trajectories passing a given sequence of connected road segments within a time period. It is very useful in many urban applications: 1) traffic modeling, 2) frequent path mining, 3) intersection coordination, and 4) traffic anomaly detection. Existing solutions for path query processing are implemented based on single machines, which are not efficient for the following tasks: 1) indexing large-scale historical data; 2) handling real-time trajectory updates; and 3) processing concurrent path queries from urban data mining applications. In this paper, we design and implement a cloud-based path query processing framework based on Microsoft Azure. We modify existing suffix tree structure to index trajectories using Azure Table. The proposed system consists of two main parts: 1) back-end processing, which performs pre-processing and index building tasks with Azure Storm used to efficiently handle massive real-time trajectory updates; and 2) query processing, which answers path queries using Azure Storm to improve efficiency and overcome I/O bottleneck. Extensive experiments are performed based on the real-time taxi trajectories from Guiyang City, China to confirm the system efficiency. We also demonstrate a real deployed traffic analysis system based on our query processing framework.