  With the advent of location-based social networks, users can tag their daily
activities in different locations through check-ins. These check-in locations
signify user preferences for various socio-spatial activities and can be used
to build their profiles to improve the quality of services in some applications
such as recommendation systems, advertising, and group formation. To support
such applications, in this paper, we formulate a new problem of identifying
top-k Socio-Spatial co-engaged Location Selection (SSLS) for users in a social
graph, that selects the best set of k locations from a large number of location
candidates relating to the user and her friends. The selected locations should
be (i) spatially and socially relevant to the user and her friends, and (ii)
diversified in both spatially and socially to maximize the coverage of friends
in the spatial space. This problem has been proved as NP-hard. To address the
challenging problem, we first develop a branch-and-bound based Exact solution
by designing some pruning strategies based on the derived bounds on diversity.
To make the solution scalable for large datasets, we also develop an
approximate solution by deriving the relaxed bounds and advanced termination
rules to filter out insignificant intermediate results. To further accelerate
the efficiency, we present one fast exact approach and a meta-heuristic
approximate approach by avoiding the repeated computation of diversity at the
running time. Finally, we have performed extensive experiments to evaluate the
performance of our proposed models and algorithms against the adapted existing
methods using four real-world large datasets.
