Efficient proximity detection among mobile users via self-tuning policies

Man Lung Yiu, U. Leong Hou, Simonas Šsaltenis, Kostas Tzoumas

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)


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 substan- tial 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 communi- cation cost. In addition, we analyze the communication cost of our solutions, and provide valuable insights on their behaviors. Exten- sive experiments suggest that our proposed solution is efficient and robust with respect to various parameters.
Original languageEnglish
Pages (from-to)985-996
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number1
Publication statusPublished - 1 Jan 2010

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Cite this