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