LIEM: A Learned Interval-Based Event Matching Algorithm for Content-Based Publish/Subscribe Systems
摘要
High-throughput publish/subscribe systems are critical to modern distributed applications, yet their performance and stability are often limited by the event matching algorithm–especially under large subscription volumes or high-dimensional content spaces, where state-of-the-art methods suffer from high latency and long-tail effects. To overcome these challenges, we introduce the Learned Interval-based Event Matching (LIEM) algorithm, featuring two key innovations. First, we propose the Predicate-Disjoint Set (PDS) partitioning strategy, which splits subscription sets into non-overlapping subsets for efficient multi-attribute matching, and enhance it with the Optimized PDS (OPDS) cost model to mathematically determine the optimal subset count, minimizing latency and improving stability. Second, we introduce a learned indexing mechanism using a specialized neural network trained per PDS partition. This model learns to map event attribute values directly to the corresponding subscription indices, serving as a highly compressed subscription index that significantly accelerates the matching process. Extensive experiments show that LIEM outperforms leading methods–REIN, Ada-REIN, WPA-REIN, OEM, and TAMA–reducing average matching latency by \(88.51\%\) , \(86.05\%\) , \(83.30\%\) , \(39.71\%\) , and \(83.93\%\) , respectively. Moreover, LIEM eliminates long-tail latency, improving stability with a \(49.15\%\) reduction in matching time standard deviation.