Exact and Heuristic Algorithms for Some Spatial-aware Interest Group Query Problems

Abstract

Location-based social networks are important issues in the recent decade. In modern social networks, such as Twitter, Facebook, and Plurk, attempt to get the accurate address positions from their users, and try to reduce the gap between virtuality and reality. This paper mainly aims at both the interests of Internet users and their real positions. This issue is called the spatial-aware interest group query problem (SIGQP). Given a user set U with n users, a keyword set W with m words, and a spatial object set S with s items, each of which contains one or multiple keywords. If a user checks in a certain spatial object, it means the user could be interested in that part of keywords, which is countable to clarify the interests of the user. The SIGQP then tries to find a k -user set U_k, k ≤ n , such that the union of keywords of these k users will equal to W , and additionally, the diameter (longest Euclidean distance of two arbitrary users in U_k) should be as small as possible. The SIGQP has been proved as NP-Complete, and two heuristic algorithms have been proposed. Extended from SIGQP, another problem is in finding the smallest k for U_k to cover all the keywords, with the users’ distance as the secondary criterion, called as “minimum user spatial-aware interest group query problem” (MUSIGQP). This paper designs a branch & bound method and a measure & conquer method to solve SIGQP and MUSIGQP respectively, and a performance analysis is given.