Research On Local Distributed Group Travel Route Search Based On Check-in Data

With the development of mobile Internet,positioning technology and the popularity of handheld devices,people can get their location information more quickly.Internet application in growing Numbers are beginning to provide users with location sharing features,including some of the big social networking sites such as Foursquare,Flicker,etc.,providing users with the location-based social network service,producing large amounts of data.These data usually include the position and social network information,not only cover the users sharing the content of the daily,at the same time,record the activity information.On the data mining,we can get the detailed information of the user's location and understand user's behavior in the real world.These closely related to the user information can be used to provide a more personalized location-based social network services.Travel route search is the hot issues in the study of location-based social network services.Tourism has become indispensable to people a leisure activity,both the vacation travel and travel daily for short periods of time,all need to develop good travel route.Travel route search mainly solve the problem of the user's route query,according to the actual needs of users,to search travel route.Travel route search study is mainly to location based social network users to share in the data mining,based on the mining information,effective processing travel route search requests from users.Existing studying of group travel route search usually aggregates user's preferences,after that use search algorithm for individual travel route to search.In real life,when the group through the travel route,there are some individual users want to choose other place according to their preference.In real life,when group browse a global route,individual user want to select different attractions in the local area of attractions in the route.Based on this requirement,this paper proposes the problem of Local Distributed Group Travel Route Search(LGRS)with the goal of getting a travel route which has local distributed POI(Point of Interest)and can make high satisfaction for the overall group.In order to effectively solve the problem of LGRS,the search finds the optimal route using transfer graph which generated by the check-in data.BTRS search algorithm is designed at the same time,the BTRS algorithm uses depth first backtracking search.BTRS algorithm can obtain exact solutions of the problem,but its efficiency is low,when the data size growth,poor algorithm on scalability.In order to improve the search efficiency,this paper puts forward two kinds of approximate optimization algorithm,the GSRS algorithm based on greedy strategy and BBRS algorithm based on branch threshold method.GSRS algorithm uses the greedy choice way of searching local optimal solution,using the local optimal solution constructed the global optimal solution.BBRS algorithm based on branch and bound search strategy further improves the searching efficiency by using the controlled relationship between nodes.This paper proposes a Double-Hierarchy Transfer Graph generated with the popularity and metastasis of POI,achieving hierarchical query.On this basis,this paper based on backtracking method,the greedy algorithm and branch threshold method respectively puts forward the DTG-BT,DTG-GS and DTG-BB algorithm.Using check-in data sets from Foursquare and Gowalla social networking websites,evaluate the effectiveness of the proposed algorithms with extensive experiments on the route profit and searching efficiency,verifying the effectiveness of the algorithms.