Short-term Experience Route Search Based On Check-in Data

With the combination of Location-Based Service (LBS) and public online social network platform, Location-Based Social Networks (LBSNs) has become a hot research field. A large number of people upload their travel photos or trajectory data which include spatial-location information to the LBSNs, recording and sharing their travel experiences. Through analyzing a large number of this type of data, user's behaviors can be modeled accurately and user's personal preference can be learned. Those can be used to make recommendation and search service for individual or collective.The route search is an important research direction in the research fields of LBSNs. According to user's current position and personalized demands, the route search service can return an optimal route for user which can be used to guide user's daily trip or travel plan. There are many optimal evaluation standards such as most saving time, most saving cost, most popularity or most in line with the user's preferences. The existing studies on route searches can be divided into three types, namely route search based on the popularity of attractions, route search based on the user's need, and query-sensitive route search.In order to make user experience various categories of attractions in short-term, this paper proposes a novel type of route search named Short-term Experience Route Search (SERS). Given a query position, the travel time constraint and categories set of the attractions, SERS finds a maximum gain route, which makes the categories of attractions richness and not reduplicate. In order to meet the user's experience need, SERS puts emphasis on various categories of attractions. At the same time, it takes attractions'popularity into consideration, not the travel routes'.This paper proposes three algorithms to process SERS. BSL algorithm needs to traverse all the solutions satisfying the constraints in the solution space tree, which makes it poor performance. In order to process SERS efficiently, we pre-compute the upper bounds of gain for nodes and propose two optimized algorithms to improve the efficiency of SERS, Single Upper Bound (SUB) pruning search algorithm and Multiple Upper Bound (MUB) pruning search algorithm. These algorithms prune the search branches that cannot generate results by upper bound filtering, which improves the searching efficiency. Based on the SUB algorithm, MUB algorithm chooses the node's upper bound dynamically according to the rest of time, which improves the searching efficiency further.Using check-in data sets from Gowalla and Foursquare social networking websites, we evaluate the efficiency of the proposed algorithms with extensive experiments under a wide range of parameter settings, verifying the effectiveness of the algorithms. Experiment results show that SUB algorithm and MUB algorithm obtain an order of magnitude speed-up comparing to algorithm BSL algorithm and MUB algorithm has the highest performance. By comparing with the existing route search in meeting the user's needs for categories, SERS can get a better performance. Combined with the real search examples, these confirm the effectiveness of SERS.SERS is the expansion of the route search in the LBSNs fields, meeting the needs of user to experience various categories of attractions in short-term. Through the SUB algorithm and MUB algorithm, user can get an optimal route quickly, enhancing the user's travel experience.