Efficient trip planning for maximizing user satisfaction

Trip planning is a useful technique that can find various applications in Location-Based Service systems. Though a lot of trip planning methods have been proposed, few of them have considered the possible constraints of POI sites in required types to be covered for user intended activities. In this paper, we study the problem of multiplecriterion-based trip search on categorical POI sites, to return users the trip that can maximize user satisfaction score within a given distance or travel time threshold. To address this problem, we propose a spatial sketch-based approximate algorithm, which extracts useful global information based on spatial clusters to guide effective trip search. The efficiency of query processing can be fully guaranteed because of the superior pruning effect on larger granularity. Experimental results on real dataset demonstrate the effectiveness of the proposed methods.