AWB+-Tree: A Novel Width-Based Index Structure Supporting Hybrid Matching for Large-Scale Content-Based Pub/Sub Systems

Event matching is a key component in a large-scale content-based publish/subscribe system. The performance of most existing algorithms is easily affected by the subscription matching probability. In this paper, we propose a new data structure, named AW <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AW B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Tree</i>, which is based on the width of the predicates, to efficiently index the subscriptions. The most notable feature of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AW B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Tree</i> is its ability to combine the advantages of different matching methods, thus achieving high and robust performance in dynamic environments. First, we implement both a forward matching method (AFM) and a backward matching method (ABM) based on <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AW B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Tree</i>. Then, we introduce a hybrid matching method (AHM) that combines AFM and ABM. Moreover, we extend <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AW B</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup>-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Tree</i> in three aspects: approximate matching, string type matching, and fine-grained parallelization. We conducted extensive experiments to evaluate the performance of the proposed matching algorithms on synthetic and real-world datasets. The experiment results reveal that AHM achieves a reduction in matching time by up to 53.8% compared to the state-of-the-art method. Additionally, AHM exhibits improved performance robustness, with up to a 76.9% reduction in terms of the standard deviation of matching time. Particularly in dynamic scenarios, AHM is at least 2.3 times faster and 41.3% more stable than its counterparts. Furthermore, by implementing parallelization, the matching speed of 8 threads can be accelerated by 4.16 times compared to the single-thread matching speed.