Research And Implementation Of Optimized Approximate Dynamic Cycle Matching Strategy For Homogeneous Symmetric Publish/Subscribe System

With the development of Internet and delivery services, online barter trade has become more and more convienent and popular. Examples inlude item exchange services, home exchange, and organ transplant etc.. As a class of publish/subscribe applications, online exchange services play an important role in modern trade and daily life.Existing work of homogneous symmetric publish/subscribe system, cycle matching algorithm is one of the key problems. By calculating the probability of a subscription to be matched on the fly, approximate dynamic cycle matching strategy can estimate upper and lower bound of space saved, which is used to set the threshold to filter the cycle matching with lower quality. This strategy solves the problem of massive middle results of dynamic cycle matching algorithm, nevertheless whose estimating formula is not accurate and whose strategy can only work in the enviornment of uniform ditribution. This paper, therefore, presents an optimized approximate dynamic cycle matching strategy, which can work in any environment. This paper first presents estimating formula of upper and lower bound of space saved for any data distribution with the theory of probability. Further, in order to get more accurate estimating formula, the distribution probability of subscriptions to be matched is calculated more predicatly. Finaly, the proposals are evaluated in a simulated enviornment with regards to data distribution, selectivity, dimension etc.. Compared with unoptimized strategy, the optimal strategy we present improves average15percent points.It is necessary and significant for publish/subscribe system to solve the problem of system maximizing profits and user maximizing satisfaction. System optimized algorithm solves the problem of system maximizing profits well, which can get the result set with the most subscriptions. The motivation behind this paper is the lack of compehensive and efficient recommendation algorithm for publish/subscribe system. In this paper, from user oriented view, at first pub/sub model is extended and the evaluating meathod of candidate cycle matchings is designed. Further, Heap based top-k and loser tree based top-k algorithms are presented to recommend better cycle matchings to users. Finaly, the algorithms presented in this paper are evaluated in a simulated enviornment from different perspectives. With the selectivity larger, the number of subscriptions larger and the number of dimensions less, loser tree based algotithm is better than the heap based algorithm. Under the budget constraints, loser tree based top-k algorithm has higher accuracy with regards to matching results.