Clique detection is a base mechanism of proactive multitarget Location-based Services (LBSs), ranging from mobile social network services to logistics. A clique is a set of  n  mobile targets which are pairwise located within spatial proximity range. Clique detection refers to automatically detecting such cliques within a set  S  of size  s  ≥  n  of tracked targets. Assuming terminal-based positioning like GPS, the paper presents an efficient clique detection strategy for reducing the message exchange between the targets' devices and a central location server for correlating the targets' positions. The basic idea is to prove the non-existence of a clique as long as it does not exist. Based on conclusions from graph theory, this is achieved by distributing the members of  S  into  n  -- 1 so-called independent sets, which are sets of targets known to be pairwise not within proximity range. For maintaining the independent sets, proximity detection between two targets, for which efficient strategies already exist, is dynamically applied to selected pairs of targets. Based on simulations it turns out that, compared to a rudimentary strategy, the achieved message savings are substantial.
['Georg Treu', 'Axel Küpper', 'Oliver Neukum', 'Claudia Linnhoff-Popien']
Efficient clique detection among mobile targets