研究生: |
林依帆 Yi-Fan - Lin |
---|---|
論文名稱: |
出版訂閱系統中基於主宰關係之事件匹配研究 A Study on Event Matching based on Dominance Relationship for Publish/Subscribe Systems |
指導教授: |
邱舉明
Ge-Ming Chiu |
口試委員: |
項天瑞
Tien-Ruey Hsiang 鮑興國 Hsing-Kuo Pao 鄧惟中 Wei-Chung Teng |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
論文出版年: | 2017 |
畢業學年度: | 105 |
語文別: | 中文 |
論文頁數: | 49 |
中文關鍵詞: | 主宰關係 、布林表達式 、發佈訂閱系統 、事件匹配 |
外文關鍵詞: | Dominating relation, Boolean Expression, Publish/Subscribe systems, Event Match |
相關次數: | 點閱:254 下載:1 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來隨著網際網路智慧型行動裝置的迅速發展,人們的生活與網路服務已經密切結合。許多網路服務(如Electronic Commerce 、Groupon…etc)可以藉由發佈/訂閱系統推廣自己的產品,並且讓人們可以自動取得自己喜愛的資訊。而發佈/訂閱系統的架構,對於使用者偏
好條件設定的描述, 常會使用特定的布林表達式(Boolean Expression model)來表達。本論文主要討論的議題為,在發佈/訂閱系統環境下,當事件發生時,如何在龐大的訂閱量中,快速且
有效率的找出匹配的訂閱者。就此,我們提出以dominance為基礎的方法,來增強資料庫查詢的效率,降低事件匹配所需的時間。
我們在研究中會根據訂閱者是屬於同質性與異質性的兩種類別分別討論其特性,這兩種類別的差異在於所有訂閱者所訂閱的屬性集合是相同或是不同。最後我們會針對我們研究的方法進行模擬,進而與現有的方法比較,證明我們的方法確實能夠有效的降低事件匹配時間。
In recent years, with the rapid development of Internet smart mobile devices, people's lives, and Internet services have been closely integrated. Many web services (such as Electronic Commerce, Groupon ... etc) can promote their products through the publish /subscribe system and allow people to automatically get their favorite information. The architecture of the publish /subscribe system, which describes the user preference conditions, is expressed using a specific Boolean expression model. The main topic of this paper is to discuss how to find out the matching subscribers quickly and efficiently in the large data volume in the publish/subscribe system environment when the event occurs. Therefore, we propose a dominance-based approach to enhance database query efficiency and reduce event matching time.
In this study, we discuss the advantages and disadvantages of the two types of subscribers, which are homogeneous and heterogeneous. The difference between the two categories is that all the subscribers subscribe to the same or different set of attributes. Lastly, we will simulate with our method, and compared with the existing methods, we prove that our method can effectively reduce the event matching time.
[1] M. K. Aguilera, R. E. Strom, D. C. Sturman, M. Astley, and T. D. Chandra. “Matching events in a content-based subscription system,” in Proc. ACM symposium on Principles of distributed computing(PODS), 1999, pp.53-61.
[2] L. Atzori, A. Iera, G. Morabito, "The internet of things: A survey", Comput. Netw., vol. 54, no. 15, pp. 2787-2805, 2010.
[3] 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
[4] C.-Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. “On high dimensional skylines,” In Proc. Int’l Conf. on Advances in Database Technology, 2006.
[5] C. Y. Chan et al. “Finding k-dominant skylines in high dimensional space,” in Proc. ACM Int’l Conf. on Management of data(SIGMOD), 2006.
[6] F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha, “Filtering algorithms and implementation for fast pub/sub systems,” in Proc. ACM Int’l Conf. on Management of data(SIGMOD), 2001, pp. 115-126.
[7] 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
[8] M.Freeston, “A general solution of n-dimensional B-tree problem,” SIGMOD’95.
[9] 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.
[10] 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
[11] J. Liu, L. Xiong, J. Pei, J. Luo, and H. Zhang, “Finding pareto optimal groups: group-based skyline,” Proceedings of the VLDB Endowment,2015, pp. 2086-2097
[12] G. Mao, B. Fidan, B. D. O. Anderson, "Wireless sensor network localization techniques", Comput. Netw., vol. 51, no. 10, pp. 2529-2553, Jan. 2007.
[13] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries,” In Proc. ACM SIGMOD Int'l Conf. Management of Data (SIGMOD) , 2003, pp. 467-478.
[14] 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.
[15] B. J. Santoso and G.-M. Chiu, “Close dominance graph: An efficient framework for answering continuous top- k dominating queries,” IEEE Transactions Knowledge and Data Engineering, vol. 26, no. 8, pp. 1853-1865, Aug. 2014
[16] 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 mining(SIGMOD), 2011, pp. 637-648
[17] 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.
[18] S. Whang, C. Brower, J. Shanmugasundaram, S. Vassilvitskii, E. Vee, /R. Yerneni, and H. Garcia-Molina, “Indexing Boolean expressions,” in Proc. VLDB, 2009, pp. 37-48.
[19] 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.
[20] M. L. Yiu and N. Mamoulis, “Efficient processing of top-k dominating queries on multi-dimensional data,” In Proc. VLDB, pp.
483–494, 2007.
[21] J. Yick, B. Mukherjee, D. Ghosal, "Wireless sensor network survey", Comput. Netw., vol. 52, no. 12, pp. 2292-2330, 2008.
[22] A. Zanella, N. Bui, A. Castellani, L. Vangelista, M. Zorzi, "Internet of Things for smart cities", IEEE Internet Things J., vol. 1, no. 1, pp.
22-32, Feb. 2014.
[23] D. Zhang, C.Y. Chan, and K.L. Tan, “An efficient publish/subscribe index for e-commerce databases,” in Proc. VLDB, 2014, pp. 613-624.
[24] L. Zou, L. Chen , “Pareto-based dominant graph: An efficient indexing structure to answer top-k queries,” IEEE Transactions Knowledge and Data Engineering, vol. 23, no. 5, pp. 727-741, Nov. 2011
[25] https://en.wikipedia.org/wiki/Bitwise_operation
[26] https://en.wikipedia.org/wiki/Breadth-first_search