Efficient Clique Detection among Mobile Targets

摘要

Clique detection is a base mechanism of proactive multi-target 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.