Approximate Dynamic Cycle Matching Strategy for Homogeneous Symmetric Pub/Sub System

摘要

In this paper we consider the problem of approximate dynamic matching for homogeneous symmetric publish/subscribe system. In this kind of applications, besides one-to-one swap, exchange can occur between more than two subscriptions, which is called cycle matching. There the number of possible cycle matching increases exponentially with the number of subscriptions and cycle length, one challenge is that how to get the cycle matchings with high probability to be selected by users. As far as we know, there is only few work on cycle matching, which is focusing on finding cycle matchings with high quality based on a pre-built graph. There, how to find cycle matchings dynamically with limited resources, which is essential for most of applications, is neglected. In this paper, we propose a probability-based cycle matching strategy to save the space used to keep intermediate results, and give the upper and lower bounds of threshold probability. Our proposal is evaluated in a simulated environment. With the probability-based strategy, the best result shows that 90% candidates can be found with 10% space.