Efficient Notification of Meeting Points for Moving Groups via Independent Safe Regions

Jing Li, Jeppe Rishede Thomsen, Man Lung Yiu, Nikos Mamoulis

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

In applications like social networking services and online games, multiple moving users which form a group may wish to be continuously notified about the best meeting point from their locations. A promising technique for reducing the communication frequency of the application server is to employ safe regions, which capture the validity of query results with respect to the users' locations. Unfortunately, the safe regions in our problem exhibit characteristics such as irregular shapes and inter-dependencies, which render existing methods that compute a single safe region inapplicable to our problem. To tackle these challenges, we first examine the shapes of safe regions in our problem's context and propose feasible approximations for them. We design efficient algorithms for computing these safe regions. We also study a variant of the problem called the sum-optimal meeting point and extend our solutions to solve this variant. Experiments with both real and synthetic data demonstrate the effectiveness of our proposal in terms of computational and communication costs.
Original languageEnglish
Article number6847137
Pages (from-to)1767-1781
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume27
Issue number7
DOIs
Publication statusPublished - 1 Jul 2015

Keywords

  • Query processing
  • spatial databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this