隨著行動裝置的快速發展，適地性服務亦逐漸受到高度的關注，並且成為相關研究領域之一相當有趣且具挑戰之研究議題。在此篇論文中，我們主要探討適地性服務中一研究議題:出版訂閱系統中具位置感知之事件偵測演算法。訂閱者會註冊其感興趣之需求條件(亦稱一訂閱)至出版訂閱系統中，此一感興趣之需求條件主要由許多屬性(以數值區間表示)以及空間區域所訂定而成。出版者則會送出出版(publication)，此一出版由其屬性以及屬性數值所組成，並且包含著空間資訊，亦即一特定位置點。若此出版符合訂閱者之所有屬性條件以及空間區域之範圍，則需要被進一步通知此一出版給予相對應之訂閱者。為了找出所有符合之訂閱者並快速通知，一個有效率的索引機制來處理龐大數量的訂閱者是極為重要的針對此一挑戰，本篇論文提出兩項方法來解決之，稱為以區間為基礎之方法(interval-based method)，以及空間鏈結方法(spatial link method)。我們主要以Bagus et al. 所提出之CDG索引架構為基礎，透過組織架構出訂閱間之支配關係(dominance relationship)，設計出一有效率之樹狀型態索引結構。透過我們所提出之方法，得以有效的降低不必要的檢視工作進而顯著地改善效率。不僅如此，現存研究中空間限制主要以矩陣型態為主，而我們所提出之空間鏈結方法(spatial link method)可以有效率處理不同型態之空間區域限制，如圓形或是不規則形態等等。研究結果顯示，與最近的相關研究GEM (Geometrical Event Matching)相比，本計畫所提出之方法提供一更高效率的解決機制。

Location-based services (LBS) have gained huge popularity due to the advance of mobile communication capabilities, and they are now becoming one of the most interesting research topics. In this thesis, we addresses one of the most popular LBS issues, which is a location-aware event matching problem in publish/subscribe systems. Subscribers register their interests which contain numeric attributes and a spatial region, while publishers post publications which contain attributes along with their values and a spatial point. A publication is said to match any subscriber if and only if this publication matches all attributes of any subscriber and it occurs inside the region of this subscriber. In order to deliver a publication to the relevant subscribers instantly, an efficient index structure is required to handle such a large number of subscriptions. To address this challenge, we propose two methods, called interval-based method and spatial link method. Based on the CDG structure proposed by Bagus et al., we further design an efficient graph-based index structure to solve this problem. We organize subscriptions based on the dominance relationship between subscriptions. Both our methods can significantly reduce unnecessary checks to improve the matching efficiency. Furthermore, unlike existing works which assume the spatial region in a rectangular form, our spatial link method can deal with a various form of spatial region, such as a circular or irregular form. Simulation results show that our proposed methods are able to offer much better performance when compared with a recent existing method, called GEM (Geometrical Event Matching).

[1] "MQ Telemetry Transport," http://mqtt.org.

[2] A. Campailla, S. Chaki, E. Clarke, S. Jha, and H. Veith, "Efficient filtering in publish-subscribe systems using binary decision diagrams," in Proc. Int’l Conf. on Software Engineering, 2001, pp. 443-452.

[3] A. Carzaniga and A. Wolf, "Forwarding in a content-based network," in ACM SIGCOMM, 2003, pp. 163-174.

[4] L. Chen, G. Cong, and X. Cao, "An efficient query indexing mechanism for filtering geo-textual data," in Proc. ACM Int’l Conf. on Management of Data (SIGMOD), 2013, pp. 749-760.

[5] L. Chen, G. Cong, X. Cao, and K. L. Tan, "Temporal spatial-keyword top-k publish/subscribe," in Proc. Int’l Conf. on Data Engineering (ICDE), 2015, pp. 255-266.

[6] P. T. Eugster, B. Garbinato, and A. Holzer, "Location-based publish subscribe," in ISNCA, 2005.

[7] 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 Proc. ACM Int’l Conf. on Management of Data (SIGMOD), 2001, pp. 115-126.

[8] W. Fan, Y. Liu, and B. Tang, "Gem: an analytic geometrical approach to fast event matching for multi-dimensional content-based publish/subscribe services," in Proc. IEEE INFOCOM, 2016.

[9] M. Fontoura, S. Sadanandan, J. Shanmugasundaram, S. Vassilvitski, E. Vee, S. Venkatesan, and J. Zien, "Efficiently evaluating complex Boolean expressions," in Proc. ACM Int’l Conf. on Management of data mining(SIGMOD), 2010, pp. 3-14.

[10] L. Guo, D. Zhang, G. Li, K. L. Tan, and Z. Bao, "Location-aware pub/sub system: when continuous moving queries meet dynamic event streams," in Proc. ACM Int’l Conf. on Management of Data (SIGMOD), 2015.

[11] H. Hu, Y. Liu, G. Li, J. Feng, and K. L. Tan, "A location-aware publish/subscribe framework for parameterized spatio-textual subscriptions," in Proc. Int’l Conf. on Data Engineering (ICDE), 2015, pp. 711-722.

[12] Z. Jerzak and C. Fetzer, "Bloom filter based routing for content-based publish/subscribe," in Proc. ACM Int’l Conf. on Distributed and Event-based Systems (DEBS), 2008, pp. 71-81.

[13] H. Jiang, P. Zhao, V. S. Sheng, G. Liu, A. Liu, J. Wu, and Z. Cui, "An efficient location-aware publish/subscribe index with boolean expressions," in Proc. Int’l Conf. on Web Information Systems Engineering (WISE), 2015, pp. 216-231.

[14] H. Leung and H.-A. Jacobsen, "Efficient matching for state-persistent publish/subscribe systems," in Proc. Conf. of the Centre for Advanced Studies on Collaborative research, 2003, pp.182-196.

[15] G. Li, S. Hou, and H.-A. Jacobsen, "A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams," in Proc. Int’l Conf. on Distributed Computing Systems, 2005, pp. 447-457.

[16] G. Li, Y. Wang, T. Wang, and J. Feng, "Location-aware publish/subscribe," in Proc. ACM Int’l Conf. on Knowledge Discovery and Data Mining (SIGKDD), 2013, pp. 802-810.

[17] M. Li, F. Ye, M. Kim, H. Chen, and H. Lei, "A scalable and elastic publish/subscribe service," in Proc. IEEE Int'l Symposium on Parallel and Distributed Processing (IPDPS), 2011, pp. 1254-1265.

[18] A. Margara and G. Cugola, "High-performance publish-subscribe matching using parallel hardware," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 1, pp. 126-135, 2014.

[19] V. Muthusamy and H. A. Jacobsen, "Infrastructure-free content-based publish/subscribe," IEEE/ACM Transactions on Networking, vol. 22, no. 5, pp. 1516-1530, 2014.

[20] S. Qian, J. Cao, Y. Zhu, and M. Li, "Rein: a fast event matching approach for content-based publish/subscribe systems," in Proc. IEEE INFOCOM, 2014, pp. 2058-2066.
[21] S. Qian, J. Cao, Y. Zhu, M. Li, and J. Wang, "H-tree: an efficient index structure for event matching in content-based publish/subscribe systems," IEEE Transactions on Parallel and Distributed Systems, 2014.

[22] W. Rjaibi, K. R. Dittrich, and D. Jaepel, "Event matching in symmetric subscription systems," in Proc. Conf. of the Centre for Advanced Studies on Collaborative Research, 2002, pp. 9.

[23] M. Sadoghi and H. A. Jacobsen, "Be-tree: an index structure to efficiently match boolean expressions over high-dimensional discrete space," in Proc. ACM Int’l Conf. on Management of Data (SIGMOD), 2011, pp. 637-648.

[24] M. Sadoghi and H. A. Jacobsen, "Analysis and optimization for boolean expression indexing," ACM Transactions on Database Systems (TODS), vol. 38, no. 2, Jun. 2013.

[25] B. J. Santoso and G. M. Chiu, "Close dominance graph: an efficient framework for answering continuous top-k dominating queries," IEEE Transactions on Knowledge and Data Engineering, 2014, pp. 1853-1865.

[26] S. E. Whang, H. Garcia-Molina, C. Brower, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, and R. Yerneni, "Indexing boolean expressions," in Proc. VLDB, vol. 2, no. 1, pp. 37-48, 2009.

[27] T. Yan and H. Garcia-Molina, "Index structures for selective dissemination of information under the Boolean model," ACM Transactions on Database Systems (TODS), vol. 19, no.2, Jun. 1994.

[28] M. Yu, G. Li, T. Wang, J. Feng, and Z. Gong, "Efficient filtering algorithms for location-aware publish/subscribe," IEEE Transactions on Knowledge and Data Engineering, 2015, pp. 950-963.

[29] D. Zhang, C. Y. Chan, and K. L. Tan, "An efficient publish/subscribe index for e-commerce databases," in Proc. VLDB, vol. 7, no. 8, pp. 613-624, 2014.

[30] Y. Zhao and J. Wu, "Towards approximate event processing in a large-scale content-based network," in Proc. IEEE Int'l Conf. on Distributed Computing Systems (ICDCS), 2011, pp. 790-799.