Buddy tracking - efficient proximity detection among mobile friends

Arnon Amir, Alon Efrat, Jussi Myllymaki, Lingeshwaran Palaniappan, Kevin Wampler

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


Global positioning systems (GPS) and mobile phone networks make it possible to track individual users with an increasing accuracy. It is natural to ask whether this information can be used to maintain social networks. In such a network each user wishes to be informed whenever one of a list of other users, called the user's friends, appears in the user's vicinity. In contrast to more traditional positioning based algorithms, the computation here depends not only on the user's own position on a static map, but also on the dynamic position of the user's friends. Hence it requires both communication and computation resources. The computation can be carried out either between the individual users in a peer-to-peer fashion or by centralized servers where computation and data can be collected at one central location. In the peer-to-peer model, a novel algorithm for minimizing the number of location update messages between pairs of friends is presented. We also present an efficient algorithm for the centralized model, based on region hierarchy and quadtrees. The paper provides an analysis of the two algorithms, compares them with a naive approach, and evaluates them on user motions generated by the IBM City Simulator system.

Original languageEnglish (US)
Pages (from-to)489-511
Number of pages23
JournalPervasive and Mobile Computing
Issue number5
StatePublished - Oct 2007


  • Dynamic nearest neighbors
  • Global positioning systems
  • Location based services
  • Social networks
  • Strips algorithm

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Buddy tracking - efficient proximity detection among mobile friends'. Together they form a unique fingerprint.

Cite this