Paper 4
Predictive Line Queries for Trac PredictionAuthors: Lasanthi Heendaliya, Dan Lin, and Ali Hurson |
AbstractThe advances in communication and positioning device tech- nologies have made it possible to track the locations of moving objects, such as vehicles equipped with GPS. As a result, a new series of applica- tions and services have been commenced into people’s life. One popular application is the real-time trac system which provides current road condition and trac jam information to commuters. To further enhance this location-based experience, this paper proposes an advanced type of service which can predict trac jams so that commuters can plan their trips more e ectively. In particular, trac prediction is realized by a new type of query, termed as the predictive line query, which estimates the amount of vehicles entering a querying road segment at a speci ed future timestamp and helps query issuers adjust their travel plans in a timely manner. Only a handful of existing work can eciently and e ectively handle such queries since most methods are designed for objects moving freely in the Euclidean space instead of under road-network constraints. Taking the road network topology and object moving patterns into ac- count, we propose a hybrid index structure, the RD-tree, which employs an R*-tree for network indexing and direction-based hash tables for man- aging vehicles. We also develop a ring-query-based algorithm to answer the predictive line query. We have conducted an extensive experimental study which demonstrates that our approach signi cantly outperforms existing work in terms of both accuracy and time eciency. |