王佳楠,陈默,巩树凤,于戈.地理社交网络中基于K近邻的兴趣组查询[J].计算机科学,2017,44(9):200-207
地理社交网络中基于K近邻的兴趣组查询
K-nearest Neighbor Based Interest Group Query in Geo-social Networks
投稿时间:2016-08-13  修订日期:2016-11-09
DOI:10.11896/j.issn.1002-137X.2017.09.038
中文关键词:  地理社交网络,K近邻,兴趣组,剪枝,网格
英文关键词:Geo-social networks,K-nearest neighbor,Interest group,Pruning,Grid
基金项目:本文受国家自然科学基金资助
作者单位E-mail
王佳楠 东北大学计算机科学与工程学院 沈阳110819 wjn920227@163.com 
陈默 东北大学计算机科学与工程学院 沈阳110819  
巩树凤 东北大学计算机科学与工程学院 沈阳110819  
于戈 东北大学计算机科学与工程学院 沈阳110819  
摘要点击次数: 201
全文下载次数: 108
中文摘要:
      为满足地理社交网络平台中用户对附近区域内具有相同兴趣的其他用户的查找需求,提出一种新型空间查询——基于K近邻的兴趣组查询(K-Nearest Neighbor Based Interest Group Query,KNNIG)。与基于距离约束的传统空间K近邻查询不同,KNNIG查询还加入了基于查询关键字的兴趣值约束,并在此基础上提出了D-I评价函数。查询结果为分值最高的用户集合。此外,提出了3种查询处理算法:基本KNNIG查询处理算法(KNNIG-G)、KNNIG查询的优化算法(KNNIG-G*)以及基于网格的距离松弛算法(KNNIG-DR)。在KNNIG-G基础上,KNNIG-G*和KNNIG-DR分别通过空间剪枝和距离松弛策略,在可容忍误差范围内有效地减少了计算开销,提高了查询效率。在真实数据集上进行的实验验证了所提算法的可行性与有效性。
英文摘要:
      Users on geo-social networks may want to find the other users with the same interests,motivated by which,we proposed a new type of spatial query named K-nearest neighbor based interest group query(KNNIG).Different from traditional spatial K-nearest neighbor queries which only consider the constraint of distance,KNNIG query also consi-ders the users’ interest values of the query keyword,based on which,we derived a D-I ranking function.KNNIG query retrieves a user group of size k that maximizes the ranking function.In addition,we proposed three kinds of query processing algorithms,including a basic processing algorithm KNNIG-G,an optimization algorithm KNNIG-G* and a distance relaxation algorithm KNNIG-DR based on grid index.Based on KNNIG-G,KNNIG-G* and KNNIG-DR are developed by a spatial pruning strategy and a distance relaxation strategy respectively,which effectively reduce computational cost and improve the query efficiency.Experimental results on a real dataset demonstrate the feasibility and effectiveness of the proposed algorithms.
查看全文  查看/发表评论  下载PDF阅读器