S. Wu, Z. Pang, G. Chen, Y. Gao, C. Zhao and S. Xiang, "NEIST: a Neural-Enhanced Index for Spatio-Temporal Queries," in IEEE Transactions on Knowledge and Data Engineering, doi: 10.1109/TKDE.2019.2945947.
Previous work on the spatial-temporal index often adopts a simple linear model to predict the future positions of moving objects, which may generate numerous errors for complex road networks and fast moving objects. In this paper, we propose NEIST, a neural-enhanced index to process spatial-temporal queries with enhanced efficiency and accuracy, by intelligently leveraging the movement patterns among moving objects. NEIST applies a Recurrent Neural Network (RNN) model to predict future positions of moving objects based on observed trajectories. To reduce the prediction overhead, a suffix-tree is further built to index trajectories with similar suffixes, and thus similar objects within a given similarity bound are grouped together to share the same prediction result. A prediction result in NEIST represents possible positions of a group of moving objects in the next t time slots. Inside each time slot, traditional linear prediction model is then adopted and a TPR-Tree is built to support spatial-temporal queries. We use Singapore taxi trajectory dataset collected over one whole month to evaluate NEIST. Compared to previous approaches, NEIST achieves a much more efficient query performance and is able to produce about 30% more accurate results.
This research is supported by the National Research Foundation, Prime Minister’s Office, Singapore, under NRF-NSFC Joint Research Grant Call on Data Science (NRF2016NRF-NSFC001-113).