Publish/subscribe (pub/sub) systems are designed to efficiently match incoming
events (e.g., stock quotes) against a set of subscriptions (e.g., trader
profiles specifying quotes of interest). However, current pub/sub systems
only support a simple binary notion of matching: an event either matches a
subscription or it does not; for instance, a stock quote will either match or
not match a trader profile. In this paper, we argue that this simple notion of
matching is inadequate for many applications where only the “best” matching
subscriptions are of interest. For instance, in targeted Web advertising,
an incoming user (“event”) may match several different advertiser-specified
user profiles (“subscriptions”), but given the limited advertising real-estate,
we want to quickly discover the best (e.g., most relevant) ads to display.
To address this need, we initiate a study of ranked pub/sub systems. We
focus on the case where subscriptions correspond to interval ranges (e.g,
age in [25,35] and salary > $50, 000), and events are points that match all
the intervals that they stab (e.g., age=28, salary = $65,000). In addition,
each interval has a score and our goal is to quickly recover the top-scoring
matching subscriptions. Unfortunately, adapting existing index structures
to solve this problem results in either an unacceptable space overhead or
a significant performance degradation. We thus propose two novel index
structures that are both compact and efficient. Our experimental evaluation
shows that the proposed structures provide a scalable basis for designing
ranked pub/sub systems.
(EN)
