【作者】 田源；

【导师】 金培权；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2018， 硕士

【摘要】 随着在线社交网络及位置服务(Location-Based Services,LBS)的快速发展,根据社交网络中不同用户行为偏好,结合用户地理位置,为用户提供个性化的服务,成为近年来的研究热点,由此也催生了位置相关社交网络这一研究方向。位置相关社交网络中蕴含涉及用户历史行为偏好及商家店铺评分等多方面的信息。如何有效利用这些信息,在满足用户多样化需求的前提下提供令用户满意的服务,是目前位置相关社交网络中的核心问题之一。本文以位置相关社交网络的发展为背景,以社交网络中的用户群组(如好友圈)为研究对象,定义了一类新的查询——空间组偏好查询,并提出了有效的查询处理算法。位置相关社交网络中的空间组偏好查询基于用户群组中不同用户的偏好、兴趣点(Point Of Interets,POI,如餐厅、旅店等)评分及POI间互相影响等多种约束下,返回满足要求的POI集合。空间组偏好查询在日常聚会地点的选择,众包游戏的任务分配等方面都有重要的意义。本文首先提出了一种基于用户偏好和POI匹配的空间组偏好查询算法,进而对该算法进行扩展,提出了基于语义扩展的空间组偏好查询算法。总体而言,本文的主要工作和贡献归纳如下:(1)基于用户偏好和POI匹配的空间组偏好查询算法:针对位置相关社交网络中的组偏好问题,定义了结合用户当前位置和用户对POI偏好的空间组偏好查询,设计了用户群组满意度的计算公式,并提出了一种基于剪枝策略的查询处理算法OPA。在此基础上,为进一步提高查询性能,论文提出了一种带有位置语义类别标签及其他附加信息的索引结构——CR-tree,并基于CR-tree设计了OPC算法,对OPA的剪枝策略从空间、POI属性等方面进行了优化。在大规模数据集上的实验结果表明了 OPA和OPC算法的有效性。(2)基于语义扩展的空间组偏好查询算法:由于OPA和OPC算法均没有考虑查询中的语义相关性(例如查询词和POI类别词之间的相似度),因此论文进一步研究了语义扩展的空间组偏好查询问题,提出了基于语义扩展的空间组偏好查询算法OPS。在OPS算法中,我们建立语义树来描述不同POI位置描述间的层次关系,并基于此定义了 POI对应的扩展位置语义模式。此外,我们结合语义树改进了最长公共子序列LCSS算法实现POI位置语义相似性的度量,并将POI语义相似性作为度量用户群组满意程度的重要因素。与此同时,为保证查询的高效执行并返回合理的查询结果,我们设计并实现了包含POI空间属性与位置语义属性的SR-tree索引和多种剪枝策略,两者结合共同对数据集中的POI进行空间过滤、POI偏好过滤及POI语义相似性过滤。在广州和上海两个真实POI数据集上的实验验证了 OPS算法的有效性。更多还原

【Abstract】 With the rapid development of online social networking and Location-Based Services(LBS),providing personalized services for users has become a hotspot in recent years,which combining with behavior preferences and locations of different users in social networks.Research on location-based social networks appeared.Location-based social networks contain information about historical behavior preferences of users and ratings of merchant stores.How to effectively use such information to provide users with satisfactory services is one core issue in current location-based social networks.Based on the development of location-based social networks,in this article,we define a new query-spatial group preference query and propose an efficient query processing algorithm.The query,at the background of location-based social network,returns the set of POIs(such as restaurants,hotels.etc.)that meet the preferences requirements of different usersin group.scores and also considering POI ratings and interactions among POIs.Spatial group preference query is of great significance meeting places selecting and task allocation of crowdsourcing games.First,we propose a spatial group preference query algorithm based on user preferences and poi matching,and then we extend the algorithm to solve the problem with semantic extension.In general,the main work and contributions of this article are summarized as follows:(1)Spatial group preference query based on user preference and poi matching.Aiming at the group preference problem in location-based social networks,the spatial group preference query isdefined,combining users’ current locations and POI preferences.The calculation formula of user group satisfaction is designed,and a query processing algorithm OPAwhich based on pruning strategies is proposed.This article aslo proposes an index structurecalled CR-tree,with POI semantic category tags and other additional information.The OPC algorithm is designedto further improve the query performance.Experimental results on large-scale datasets show the effectiveness of OPA and OPC algorithms.(2)Spatial group preference query algorithm based on semantic extension.Neither the OPA nor the OPC algorithm does not consider semantic relevance(e.g.,similarity between query terms and POI category terms).Thus,we further study the spatial group preference query problem based on semantic extension and propose the spatial group preference query algorithm OPS based on semantic extension.In the OPS algorithm,we establish a semantic tree to describe the hierarchical relationship between differentdescriptions of POIs.In addition,we improve the longest common subsequence LCSS algorithm to measure the semantic similarity between POIs based on semantic tree.The semantic similarityof POIsis taken as an important factor tomeasure the satisfaction of queries.At the same time,we design and implement the SR-tree index withPOI spatial attributes and semantic attributes to ensure efficient execution of query and return reasonable query results.A variety of pruning strategies are used to filter POI.Experiments on two real datasets in Guangzhou and Shanghai demonstrate the effectiveness of the OPS algorithm.更多还原