Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams

ABSTRACT

In this paper, we propose a new location-aware pub/sub system, Elaps, that continuously monitors moving users subscribing to dynamic event streams from social media and E-commerce applications. Users are notified instantly when there is a matching event nearby. To the best of our knowledge, Elaps is the first to take into account continuous moving queries against dynamic event streams. Like existing works on continuous moving query processing,Elaps employs the concept of safe region to reduce communication overhead. However, unlike existing works which assume data from publishers are static, updates to safe regions may be triggered by newly arrived events. In Elaps, we develop a concept called \textit{impact region} that allows us to identify whether a safe region is affected by newly arrived events. Moreover, we propose a novel cost model to optimize the safe region size to keep the communication overhead low. Based on the cost model, we design two incremental methods, iGM and idGM, for safe region construction. In addition, Elaps uses boolean expression, which is more expressive than keywords, to model user intent and we propose a novel index, BEQ-Tree, to handle spatial boolean expression matching. In our experiments, we use geo-tweets from Twitter and venues from Foursquare to simulate publishers and boolean expressions generated from AOL search log to represent users intentions. We test user movement in both synthetic trajectories and real taxi trajectories. The results show that Elaps can significantly reduce the communication overhead and disseminate events to users in real-time.

References

1. J. Bao, M. Mokbel, and C.-Y. Chow, "Geofeed: A location aware news feed system," in ICDE, 2012, pp. 54--65.
2. G. Li, Y. Wang, T. Wang, and J. Feng, "Location-aware publish/subscribe," in KDD, 2013, pp. 802--810.
3. L. Chen, G. Cong, and X. Cao, "An efficient query indexing mechanism for filtering geo-textual data," in SIGMOD, 2013, pp. 749--760.
4. G. Cugola and A. Margara, "High-performance location-aware publish-subscribe on gpus," in Middleware, 2012, pp. 312--331.
5. J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee, "Location-based spatial queries," in SIGMOD, 2003, pp. 443--454.
6. M. Hasan, M. A. Cheema, X. Lin, and Y. Zhang, "Efficient construction of safe regions for moving knn queries over dynamic datasets," in phSSTD, 2009, pp. 373--379.
7. B. Bamba, L. Liu, A. Iyengar, and P. S. Yu, "Safe region techniques for fast spatial alarm evaluation," Georgia Institute of Technology, 2008.
8. D. Wu, M. L. Yiu, C. S. Jensen, and G. Cong, "Efficient continuously moving top-k spatial keyword query processing," in ICDE, 2011, pp. 541--552.
9. W. Huang, G. Li, K.-L. Tan, and J. Feng, "Efficient safe-region construction for moving top-k spatial keyword queries," in CIKM, 2012, pp. 932--941.
10. L. Guo, J. Shao, H. Aung, and K.-L. Tan, "Efficient continuous top-k spatial keyword queries on road networks," Geo Informatica, pp. 1--32, 2014.
11. R. Finkel and J. Bentley, "Quad trees a data structure for retrieval on composite keys," Acta Informatica, vol. 4, no. 1, pp. 1--9, 1974.
12. W. Xu, C.-Y. Chow, M. L. Yiu, Q. Li, and C. K. Poon, "Mobifeed: A location-aware news feed system for mobile users," in SIGSPATIAL '12, 2012, pp. 538--541.
13. F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha, "Filtering algorithms and implementation for very fast publish/subscribe systems," in SIGMOD, 2001, pp. 115--126.
14. S. E. Whang, H. Garcia-Molina, C. Brower, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, and R. Yerneni, "Indexing boolean expressions," PVLDB, vol. 2, no. 1, pp. 37--48, 2009.
15. M. Sadoghi and H.-A. Jacobsen, "Be-tree: An index structure to efficiently match boolean expressions over high-dimensional discrete space," in SIGMOD, 2011, pp. 637--648.
16. D. Zhang, C.-Y. Chan, and K.-L. Tan, "An efficient publish/subscribe index for ecommerce databases," PVLDB, vol. 7, no. 8, pp. 613--624, 2014.
17. H. V. Jagadish, B. C. Ooi, K.-L. Tan, C. Yu, and R. Zhang, "idistance: An adaptive b-tree based indexing method for nearest neighbor search," TODS, vol. 30, no. 2, pp. 364--397, 2005.
18. T. W. Yan and H. García-Molina, "Index structures for selective dissemination of information under the boolean model," TODS, vol. 19, no. 2, pp. 332--364, 1994.
19. A. Guttman, "R-trees: A dynamic index structure for spatial searching," in SIGMOD, 1984, pp. 47--57.
20. T. Brinkhoff, "A framework for generating network-based moving objects," Geoinformatica, vol. 6, no. 2, pp. 153--180, 2002.
21. J. Zhou, A. K. Tung, W. Wu, and W. S. Ng, "A 'semi-lazy' approach to probabilistic path prediction in dynamic environments," in KDD '13, 2013, pp. 748--756.
22. G. Antoshenkov and M. Ziauddin, "Query processing and optimization in oracle rdb," The VLDB Journal, vol. 5, no. 4, pp. 229--237, 1996.
23. K. Wu, E. J. Otoo, and A. Shoshani, "Optimizing bitmap indices with efficient compression," ACM Trans. Database Syst., vol. 31, no. 1, pp. 1--38, Mar. 2006.
24. F. Ramsak, V. Markl, R. Fenk, M. Zirkel, K. Elhardt, and R. Bayer, "Integrating the ub-tree into a database system kernel," in VLDB '00, 2000, pp. 263--272.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems