Evaluating Proximity Relations Under Uncertainty

Zhengdao Xu and Hans-Arno Jacobsen.

In IEEE 23rd International Conference on Data Engineering, pages 876-885, April 2007. Istanbul, Turkey.
Acceptance rate: 19 %. Number of submissions: 659.


For location-based services it is often essential to efficiently process proximity relations among mobile objects, such as to establish whether a group of friends or family members are within a given distance of each other A severe limitation in accurately establishing such relations is the inaccuracy of dynamically obtained position data, the point in time, and the frequency with which the position data is collected. In this paper, we use the common model of interpreting the unknown position of an object by a probability distribution centered around the last know position of the object. While this approach is straight forward, it poses severe difficulties for establishing the truth or falsehood of the proximity relation. To address this problem, we analytically quantify the lower and upper bounds of the size of the smallest circle that covers the mobile objects involved in the proximity relation. Based on this result we propose two novel algorithms that closely monitor the relation at low location update cost. Furthermore, we develop a cost-effective estimation technique to determine the probability of match for a given proximity relation.


Readers who enjoyed the above work, may also like the following:

  • Processing Proximity Relations in Road Networks.
    Zhengdao Xu and Hans-Arno Jacobsen.
    In SIGMOD'2010, pages 243-254, June 2010.
    Tags: spatial query, location-based services, publish/subscribe
  • Expressive Location-based Continuous Query Evaluation With Binary Decision Diagrams.
    Zhengdao Xu and Hans-Arno Jacobsen.
    In IEEE International Conference on Data Engineering (ICDE), pages 1155-1158, March 2009.
    Acceptance rate: 27 %. Number of submissions: 554.
    Tags: algorithms, bdd, content-based matching, content-based publish/subscribe, event processing, topss, publish/subscribe, spatial query, location-based services
  • Adaptive Location Constraint Processing.
    Zhengdao Xu and Hans-Arno Jacobsen.
    In 26th ACM SIGMOD Conference, pages 581-592, Beijing China, June 2007.
    Acceptance rate: 14%. Number of submissions: 480.