近年來，隨著行動網路和智慧型裝置的逐漸普及，資料服務相關的應用也隨之出現，出版/訂閱(publish/subscribe)系統提供了其中一種重要的服務模式。該類服務中，使用者的需求和事件(event)分別被描述為subscriptions與publications，而該系統主要提供所有的subscriptions當其與publication匹配時即可收到通知的服務。近年來，隨著資料量與種類的快速成長，出版/訂閱的匹配問題主要關注於如何有效率的處理大量和多樣化的資料，使得在巨量、多樣化的資料中也能夠快速的找到匹配的結果。
在本論文中，為了更加有效率的處理匹配問題，我們提出一個以主宰關係為基礎的資料結構，該結構可以大量減少不必要的匹配，以改善系統的效能，其中，我們的重點之一是提出一套建立整合型主宰關係的方法以解決不同屬性型式之間無優劣關係的問題。此外，我們也提出多個能夠進一步提升效能的策略，最後我們會對於所提出的方法以合成資料集進行效能評估及分析。

With the popularity of mobile network and smart devices, the corresponding applications of data service arise recently, publish/subscribe systems provide one of the important service models. In these kinds of service, user demands can be described as subscriptions and events can be described as publications respectively. Publish/Subscribe systems mainly provide a service to all subscriptions, that is, with respect to an incoming publication, the systems will find all matched subscriptions and then send immediate notifications to them. With the rapid growth of data and the increasing diversity of data, the main challenge of matching problem in the publish/subscribe system during recent years is focused on how to efficiently cope with these data so as to find out the result in a timely manner.
In this paper, we propose a data structure based on dominating relation. By utilizing this data structure, a large number of unnecessary checks can be avoided and the performance of the system can be greatly enhanced. Additionally, one of our key points is proposing an integrated method to build dominance relation between two incomparable attribute format. Moreover, we also propose some strategies to improve performance and employ synthetic data in the experiments to show that our method outperforms the OpIndex significantly.

[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]S. Akkermans, R. Bachiller, and M. Vucinic, “Towards efficient publish-subscribe middleware in the IoT with IPv6 multicast,” in Proc. IEEE Int’l Conf. on Communications(ICC), 2016, pp.1-6.
[3]T. B. Mishra, and S. Sahni, “PUBSUB: An efficient publish/subscribe system,” in Proc. IEEE Symposium on Computers and Communications (ISCC), 2013, pp.606-611.
[4]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.
[5]A. Carzaniga, D. Rosenblum, and A. Wolf, “Design and evaluation of wide-area event notification service,” ACM Transactions on Computer Systems (TOCS), vol. 19, no. 3, 2001, pp. 332-383.
[6]A. Carzaniga, and A. L. Wolf, “Forwarding in a content-based network,” in Proc. SIGCOMM, 2003, pp. 163-174.
[7]C. Y. Chan, M. N. Garofalakis, and R. Rastogi, “Re-tree: an efficient index structure for regular expressions,” VLDB, 2003, pp. 102-119.
[8]B. Chandramouli, J. Phillips, and J. Yang, “Value-based notification conditions in large-scale publish/subscribe systems,” in Proc. VLDB, 2007, pp. 878-889.
[9]B. Chandramouli, and J. Yang, “End-to-end support for joins in large-scale publish/subscribe systems,” in Proc. VLDB, 2008, pp. 434-450.
[10]Z. Cui, Z. Wu, C. Zhou, G. Gao, J. Yu, Z. Zhao, and B. Wu, “An efficient subscription index for publication matching in the cloud,” Knowledge-Based Systems, 2016, pp.110-120.
[11]A. J. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. M. White, “Towards expressive publish/subscribe systems,” in Proc. Extending Database Technology(EDBT), 2006, pp. 627-644.
[12]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.
[13]W. Fan, Wenhao, Y. A. Liu, and B. Tang, “GEM: An analytic geometrical approach to fast event matching for multi-dimensional content-based publish/subscribe services,” in Proc. INFOCOM, 2016, pp. 1-9.
[14]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.
[15]A. Machanavajjhala, E. Vee, M. Garofalakis, and J. Shanmugasundaram, “Scalable ranked publish/subscribe,” in Proc. VLDB, 2008, pp. 451-462.
[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]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, vol. 26, no. 8, 2014, pp. 1853-1865.
[19]R. L. Szabo, and K. Farkas, “Publish/Subscribe Communication for Crowd-sourcing Based Smart City Applications,” in Proc. International Conference of Informatics and Management Sciences (ICTIC), 2013, pp.25-29.
[20]Y. Teranishi, R. Banno, and T. Akiyama, “Scalable and Locality-Aware Distributed Topic-Based Pub/Sub Messaging for IoT,” in Proc. IEEE Global Communications Conference (GLOBECOM), 2015, pp. 1-7.
[21]X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang, “AP-Tree: efficiently support location-aware Publish/Subscribe,” VLDB, vol. 24, no. 6, 2015, pp. 823-848.
[22]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.
[23]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, vol. 27, no. 4, 2015, pp. 950-963.
[24]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.