Computer Science ›› 2017, Vol. 44 ›› Issue (9): 200-207.doi: 10.11896/j.issn.1002-137X.2017.09.038

Previous Articles     Next Articles

K-nearest Neighbor Based Interest Group Query in Geo-social Networks

WANG Jia-nan, CHEN Mo, GONG Shu-feng and YU Ge   

  • Online:2018-11-13 Published:2018-11-13

Abstract: 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.

Key words: Geo-social networks,K-nearest neighbor,Interest group,Pruning,Grid

[1] HRISTOVA D,WILLIAMS M J,MUSOLESI M,et al.Measu-ring Urban Social Diversity Using Interconnected Geo-Social Networks[C]∥Proceedings of the 25th International Confe-rence on World Wide Web.2016:21-30.
[2] GAO H,TANG J,LIU H.Addressing the cold-start problem in location recommendation using geo-social correlations[J].Data Mining and Knowledge Discovery,2015,29(2):299-323.
[3] ANEJA N,GAMBHIR S.Geo-Social Semantic Profile Matching Algorithm for Dynamic Interests in Ad-hoc Social Network[C]∥2015 IEEE International Conference on Computational Intelligence & Communication Technology (CICT).IEEE,2015:354-358.
[4] LI Y F,WU D M,XU J L,et al.Spatial-aware interest groupqueries in location-based social networks[C]∥ Proceedings of the 21st ACM International Conference on Information and Knowledge Management.2012:2643-2646.
[5] ROUSSOPOULOS N,KELLEY S,Vincent F.Nearest neighbor queries[J].ACM Sigmod Record.ACM,1995,24(2):71-79.
[6] PAPADIAS D,SHEN Q,TAO Y,et al.Group nearest neighbor queries[C]∥20th International Conference on Data Enginee-ring,2004.IEEE,2004:301-312.
[7] TAO Y,PAPADIAS D,SHEN Q.Continuous nearest neigh-bor search[C]∥Proceedings of the 28th International Confe-rence on Very Large Data Bases.VLDB Endowment,2002:287-298.
[8] GAO Y,ZHENG B,LEE W C,et al.Continuous visible nearest neighbor queries[C]∥Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.ACM,2009:144-155.
[9] GAO Y,ZHENG B.Continuous obstructed nearest neighborqueries in spatial databases[C]∥Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.ACM,2009:577-590.
[10] HJALTASON G R,SAMET H.Distance browsing in spatialdatabases[J].ACM Transactions on Database Systems(TODS),1999,24(2):265-318.
[11] ZHOU Y,XIE X,WANG C,et al.Hybrid index structures for location-based Web search[C]∥Proceedings of the 14th ACM International Conference on Information and Knowledge Ma-nagement.ACM,2005:155-162.
[12] CONG G,JENSEN C S,WU D.Efficient retrieval of the top-k most relevant spatial web objects[J].Proceedings of the VLDB Endowment,2009,2(1):337-348.
[13] CHEN L,CONG G,CAO X.An efficient query indexing mechanism for filtering geo-textual data[C]∥ACM SIGMOD International Conference on Management of Data.2013:749-760.
[14] CHEN L,CONG G,CAO X,et al.Temporal Spatial-Keyword Top-k publish/subscribe[C]∥International Conference on Data Engineering.IEEE,2015:255-266.
[15] YANG D N,SHEN C Y,LEE W C,et al.On socio-spatial group query for location-based social networks[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2012:949-957.
[16] LIU W,SUN W,CHEN C,et al.Circle of friend query in geo-social networks[M]∥Database Systems for Advanced Applications.Springer Berlin Heidelberg,2012:126-137.
[17] JIANG J,LU H,YANG B,et al.Finding top-k local users in geo-tagged social media data[C]∥2015 IEEE 31st International Conference on Data Engineering (ICDE).IEEE,2015:267-278.
[18] CHEEMA M A,YUAN Y,LIN X.Circulartrip:an effective algorithm for continuous kNN queries[M]∥Advances in Databases:Concepts,Systems and Applications.Springer Berlin Heidelberg,2007:863-869.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .