Processing proximity relations in road networks

Zhengdao Xu, Hans Arno Jacobsen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

32 Scopus citations


Applications ranging from location-based services to multi-player online gaming require continuous query support to monitor, track, and detect events of interest among sets of moving objects. Examples are alerting capabilities for detecting whether the distance, the travel cost, or the travel time among a set of moving objects exceeds a threshold. These types of queries are driven by continuous streams of location updates, simultaneously evaluated over many queries. In this paper, we define three types of proximity relations that induce location constraints to model continuous spatio-temporal queries among sets of moving objects in road networks. Our focus lies on evaluating a large number of continuous queries simultaneously. We introduce a novel moving object indexing technique that together with a novel road network partitioning scheme restricts computations within the partial road network. These techniques reduce query processing overhead by more than 95%. Experiments over real-world data sets show that our approach is twenty times faster than a baseline algorithm.

Original languageEnglish
Title of host publicationProceedings of the 2010 International Conference on Management of Data, SIGMOD '10
Number of pages12
StatePublished - 2010
Externally publishedYes
Event2010 International Conference on Management of Data, SIGMOD '10 - Indianapolis, IN, United States
Duration: 6 Jun 201011 Jun 2010

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Conference2010 International Conference on Management of Data, SIGMOD '10
Country/TerritoryUnited States
CityIndianapolis, IN


  • constraint processing
  • location constraint
  • location query
  • location-based services
  • publish/subscribe
  • road networks


Dive into the research topics of 'Processing proximity relations in road networks'. Together they form a unique fingerprint.

Cite this