Spatio-temporal Keywords Query Processing For Social Network

With the proliferation of mobile phones,smart watches,civilian GPS devices,and the growth of location-based social media and geo-location labels,social networks have become increasingly connected with spatio-temporal keyword information.More specifically,smartphone users are increasingly volunteering their own geo-location information,including check-in,push-to-push,geotagging,location reporting,GPS tracking,etc,which makes a direct result of a variety of vast spatial-temporal data distribution.In the face of this situation and the development trend of comprehension and generalization,the traditional social network query and spatial object query and recommendation has been unable to meet the needs of different users.Spatio-temporal social network keyword query come into being.Spatio-temporal social network is composed of social network,spatial network and temporal network.It includes social network information,activity information?including spatial object information?,user participation activity information and user's trajectory information.It covers two hot research branch:temporal social network and geographic social network.In the context of big data,how to efficiently realize the multi-attribute complex query is the key point and special difficulty.In this paper,from the point of view of users,businesses and system management,this paper puts forward various kinds of spatio-temporal keyword query.In order to achieve efficient query processing,we establish spatial-temporal keyword indexes for different data types,and implement query processing algorithms based on these index structure.The main contributions of our work are:?1?This paper gave a comprehensive summary of the relevant work and summarize the main problems in the current study to indicate the direction of the follow-up study.Different from the study of geographical social network query,the study of the temporal social network query is not comprehensive,lacking the research of establishing relevant index that combines time information and social network.In order to synchronize with the actual development of social media,the concept of activity,user participation and user trajectory is introduced to enrich the social network model.Group query research is difficult,but the actual application value is huge,and the traditional mCK query is also lack of user characteristics.?2?Temporal social network model is proposed.The objects contained in the model are described and formalized,and the characteristics of each data object are analyzed.The basic query algebra and the basic query types are defined in order to unify formal query,which lays the foundation for the research on the query technology of the spatial-temporal keywords social network.?3?Based on the spatio-temporal social network model,the temporal social network?TSN?model is separated.On the basis of this model,four specific queries are proposed:FIA,UTF,GURD and TGQ queries,among which GURD and TGQ are more complex group queries.In order to answer the temporal social network queries,four kinds of temporal keyword indexes are designed,and the corresponding efficient algorithms are proposed based on these index structure.?4?This paper proposes two groups query:STGI and STGLP for the spatio-temporal social network.Among them,STGI query is for the user check-in information,while STGLP query is for the user trajectory information.For these two group query,we design spatio-temporal keyword index structure,and then propose their own query processing algorithms,which include the corresponding group process.?5?Since the traditional mCK problem does not include social network information,the result does not have user characteristics.Introducing the concept of social distance between POIs,a new mCK query,called GS-mCK query,is proposed,which considers spatial distance,social distance,and keyword phrase constraints,simultaneously.Since the GS-mCK problem is an NP-hard problem,in the case of big data,it cannot be solved with an exact algorithm,and an effective approximation algorithm is sought.First,the G²SKG algorithm with approximate factor of 2 is proposed based on the IR-tree.In order to further reduce the size of the approximation factor,an S²KEC algorithm with an approximate factor of 2/3^1/2?1.15 is proposed.?6?This paper designs and implements the query and analysis prototype system of spatio-temporal social network,and validates the validity and feasibility of the method and technology in this paper.