A travel time prediction algorithm using rule-based classification on mapreduce

Recently, the amount of trajectory data has been rapidly increasing with the popularity of LBS and the development of mobile technology. Thus, the analysis of trajectory patterns for large amounts of trajectory data has attracted much interest. To improve the quality of trajectory-based services, it is essential to predict an exact travel time for a given query on road networks. One of the typical schemes for travel time prediction is a rule-based classification method which can ensure high accuracy. However, the existing scheme is inadequate for the processing of massive data because it is designed without the consideration of distributed computing environments. To solve this problem, this paper proposes a travel time prediction algorithm using rule-based classification on MapReduce for a large amount of trajectory data. First, our algorithm generates classification rules based on the actual traffic statistics and measures adequate velocity classes for each road segment. Second, our algorithm generates a distributed index by using the grid-based map partitioning method. Our algorithm can reduces the query processing cost because it only retrieves the grid cells which contain a query region, instead of the entire road network. Furthermore, it can reduce the query processing time by estimating the travel time for each segment of a given query in a parallel way. Finally, we show from our performance analysis that our scheme performs more accurate travel time prediction than the existing algorithms.