Enabling Scalable Geographic Service Sharing with Weighted Imprecise Voronoi Cells

Xike Xie, Peiquan Jin, Man Lung Yiu, Jiang Du, Mingxuan Yuan, Christian S. Jensen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)


We provide techniques that enable a scalable so-called Volunteered Geographic Services system. This system targets the increasing populations of online mobile users, e.g., smartphone users, enabling such users to provide location-based services to each other, thus enabling citizen reporter or citizen as a sensor scenarios. More specifically, the system allows users to register as service volunteers, or micro-service providers, by accepting service descriptions and periodically updated locations from such volunteers; and the system allows users to subscribe to notifications of available, nearby relevant services by accepting subscriptions, formalized as continuous queries, that take service preferences and user locations as arguments and return relevant services. Services are ranked according to their relevance and distance to a query, and the highest ranked services are returned. The key challenge addressed is that of scalably providing up-to-date results to queries when the query locations change continuously. This is achieved by the proposal of a new so-called safe-zone model. With safe zones, query results are accompanied by safe zones with the property that a query result remains the same for all locations in its safe zone. Then, query users need only notify the system when they exit their current safe zone. Existing safe-zone models fall short in the papers setting. The new model is enabled by (i) weighted and (ii) set weighted imprecise Voronoi cells. The paper covers underlying concepts, properties, and algorithms, and it covers applications in VGS tracking and presents findings of empirical performance studies.
Original languageEnglish
Article number7247730
Pages (from-to)439-453
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
Publication statusPublished - 1 Feb 2016


  • Spatial Keyword Search
  • Volunteered Geographic Service
  • Weighted Imprecise Voronoi Cell

ASJC Scopus subject areas

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

Cite this