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.


An important problem for many location-based applications is the continuous evaluation of proximity relations among moving objects. These relations express whether a given set of objects is in a spatial constellation or in a spatial constellation relative to a given point of demarcation in the environment. We represent proximity relations as location constraints, which resemble standing queries over continuously changing location position information. The challenge lies in the continuous processing of large numbers of location constraints as the location of objects and the constraint load change. In this paper, we propose an adaptive location constraint indexing approach which adapts as the constraint load and movement pattern of the objects change. The approach takes correlations between constraints into account to further reduce processing time. We also introduce a new location update policy that detects constraint matches with fewer location update requests. Our approach stabilizes system performance, avoids oscillation, reduces constraint matching time by 70% for in-memory processing, and reduces secondary storage accesses by 80% for I/O-incurring environments.


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
  • 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.