Abstract
Geo-social group
queries, which return a social cohesive user group with a spatial
constraint, have receive significant research interests due to their
promising applications for group-based activity planning and scheduling
in location-based social networks (LBSNs). However, existing studies on
geo-social group queries mostly assume the users are stationary whereas
in realistic LBSN application scenarios all users may continuously move
over time. Thus, in this paper, we investigate the problem of
continuous geo-social groups monitoring
(
CGSGM
) over moving users. A challenge in answering CGSGM queries over moving
users is how to efficiently update geo-social groups when users are
continuously moving. To address the CGSGM problem, we first propose a
baseline algorithm, namely
Baseline-BB
, which recomputes the new geo-social groups from scratch at each time
instance by utilizing a branch and bound (BB) strategy. To improve the
inefficiency of BB, we explore a new strategy, called common neighbor or
neighbor expanding (CNNE), which expands the common neighbors of edges
or the neighbors of users in intermediate groups to quickly produce the
valid group combinations. Accordingly, another baseline algorithm,
namely
Baseline-CNNE
, is proposed. As these baseline algorithms do not maintain intermediate
results to facilitate further query processing, we develop an
incremental algorithm, called
incremental monitoring algorithm (IMA)
, which maintains the support, common neighbors and the neighbors of
current users when exploring possible user groups for further updates
and query processing. Since IMA requires many times of truss
decomposition when processing mutiple-users updates, we propose an
improved incremental algorithm, called
improved incremental monitoring algorithm (IIMA)
, which performs truss decompostion only once. Moreover, we design
algorithms for handling the social changes that result in
insertion/deletion of some edges in the social network. Owing to the
challenge in setting, an appropriate monitoring distance, we further
study the top
$N$
CGSGM problem, which finds top
$N$
result groups at each time instance. Finally, we conduct extensive
experiments using four real datasets to validate our ideas and evaluate
the proposed algorithms.
Original language | English |
---|---|
Pages (from-to) | 7815-7828 |
Number of pages | 14 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 35 |
Issue number | 8 |
Early online date | 2 Nov 2022 |
DOIs | |
Publication status | Published - 1 Aug 2023 |
Scopus Subject Areas
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
User-Defined Keywords
- Continuous queries
- geo-social group query
- location-based services
- monitoring
- nearest neighbor