Diversifying Top-k Routes with Spatial Constraints

Abstract

Trip recommendation has become increasingly popular with the rapid growth of check-in data in location-based social networks. Most existing studies focused only on the popularity of trips. In this paper, we consider further the usability of trip recommendation results through spatial diversification. We thereby formulate a new type of queries named spatial diversified top-k routes (SDkR) query. This type of queries finds k trip routes with the highest popularity, each of which starts at a given starting point, consumes travel time within a given time budget, and passes through points of interest (POIs) of given categories. Any two trip routes returned are diversified to a certain degree defi..