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.


Many location-based services require rich and expressive query language support for filtering large amounts of information over thousands of concurrently executing continuous queries. Parts of these queries may overlap or logically depend on each other suggesting the possibility to amortize the query execution over shared sub-queries and prune query execution according to dependencies to achieve real-time processing requirements inherent to many location-based applications. In this paper spatio-temporal queries constitute location constraints monitored by applications. We develop the Constraint Combination Binary Decision Diagrams (CCBDD), an efficient location constraint matching algorithm, and query indexing based on Binary Decision Diagrams. With CCBDD, redundant computations in shared sub-queries are avoided, and query dependencies are identified and pruned. Empirical results show that the CCBDD structure greatly improves matching performance with shared query execution and economical memory use.


Tags: algorithms, bdd, content-based matching, content-based publish/subscribe, event processing, topss, publish/subscribe, spatial query, location-based services

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