Efficient Proximity Detection among Mobile Users via SelfTuning Policies

Given a set of users, their friend relationships, and a distance
threshold per friend pair, the proximity detection problem is to
find each pair of friends such that the Euclidean distance between
them is within the given threshold. This problem plays an essential
role in friend-locator applications and massively multiplayer online
games. Existing proximity detection solutions either incur substantial
location update costs or their performance does not scale well to
a large number of users. Motivated by this, we present a centralized
proximity detection solution that assigns each mobile client with a
mobile region. We then design a self-tuning policy to adjust the
radius of the region automatically, in order to minimize communication
cost. In addition, we analyze the communication cost of our
solutions, and provide valuable insights on their behaviors. Extensive
experiments suggest that our proposed solution is efficient and
robust with respect to various parameters.