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:
- Modelling Performance Optimizations for Content-based Publish/Subscribe.
Alex Wun and Hans-Arno Jacobsen.
In DEBS 2007, pages 171-179, Toronto, Canada, June 2007.
Tags: content-based matching, content-based publish/subscribe, event processing, padres, publish/subscribe, topss, algorithms
- Predictive Publish/Subscribe Matching.
Vinod Muthusamy, Haifeng Liu, and Hans-Arno Jacobsen.
In ACM Distributed Event-based Systems (DEBS), pages 14-25, July 2010.
Acceptance rate: 25% .
Tags: algorithms, content-based publish/subscribe, publish/subscribe, pub/sub applications, predictive publish/subscribe, topss, event processing, p-topss, probabilistic data management
- G-ToPSS: Fast Filtering of Graph-based Metadata.
Milenko Petrovic, Haifeng Liu, and Hans-Arno Jacobsen.
In World Wide Web Conference, pages 539-547, Chiba, Japan, May 2005.
Nominated for best paper award, i.e., one of four finalist papers. Acceptance rate: 14%. Number of submissions: 550.
Tags: algorithms, content-based publish/subscribe, event processing, publish/subscribe, topss, graph-based pub/sub