User-Rating-Based Trip Planning Query Optimization

Location-based services(LBS) are one of the most frequently used tools in people’s daily life nowadays, and most of them rely on the trip planning techniques to provide related traffic services. With the rapid development of Mobile Web and geo-positioning technologies, people can access to applications integrated with trip planning techniques more easily via smart terminals. Based on the above facts, trip planning algorithms play a key role to improve the quality and efficiency of our travel.The biggest challenge in research work on trip planning is that the problem is a NPComplete problem like the famous Traveling Salesman Problem. In another word, the efficiency of trip planning algorithms would be intolerable with explosion of node number.Besides, the existing methods rarely consider the possible constraints of POI(point of interest) in required types to be covered for user intended activities.In this paper, we study the problem of multiple-criterion-based trip search on categorical POI sites, to return users the trip that maximize user satisfaction score within a given distance or travel time threshold. The key points making our work outstanding are listed as follows:(1) Different from traditional trip planning works, this paper introduces the concept of user satisfaction. The user satisfaction score of a specific POI site can be computed as the average of all the scores marked by historical guests, which implies the general attitude most people took towards the POI.(2) We not only propose a baseline method that gives accurate answer, but also provide the spatial sketch-based trip planning algorithm, through which we could achieve a high performance with a little loss of accuracy.(3) In addition, some practical techniques are used to speed up the processing user queries such as query optimization and buffer management.