Finding nearest Neighbor in Geo-Social Query Processing

Abstract

Recording the region of people using location-acquisition technologies, such as GPS, allows generating life patterns, which associate people to places they habitually visit. Considering life patterns as edges that connect users of a social network to geographical entities on a spatial network, improves the social network, providing an integrated geo-social graph. Queries over such graph excerpt information on users, with respect to their location history, and excerpt information on geographical entities in correspondence with users who normally visit these entities. A repeated type of query in spatial networks (e.g., road networks) is to find the k- nearest neighbors (k-NN) of a given query objects. With these networks, the distances between objects depend on their network connectivity and it is expensive to compute the distances (e.g., shortest paths) between objects. We present the concept of a geo-social graph that is based on life patterns, where users are connected to geographical entities using life-pattern edges more specifically to allow finding a group of users in a Geo-Social network whose members are close to each other both socially and geographically. We proposed a new approach to find the group of k users who are geo-socially attached to each other and satisfy the all the query points. We used the Bottom up pruning technique for effective pruning of geo-social group queries. An important contribution of this work is in illustrating the usefulness and the feasibility of maintaining and querying integrated geo-social graphs.