Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Scalable ranked publish/subscribe

Machanavajjhala Ashwin, Vee Erik, Garofalakis Minos, Shanmugasundaram, Jayavel

Full record

---

Summary

Publish/subscribe (pub/sub) systems are designed to efficiently match incomingevents (e.g., stock quotes) against a set of subscriptions (e.g., traderprofiles specifying quotes of interest). However, current pub/sub systemsonly support a simple binary notion of matching: an event either matches asubscription or it does not; for instance, a stock quote will either match ornot match a trader profile. In this paper, we argue that this simple notion ofmatching is inadequate for many applications where only the “best” matchingsubscriptions are of interest. For instance, in targeted Web advertising,an incoming user (“event”) may match several different advertiser-specifieduser 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. Wefocus 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 allthe 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-scoringmatching subscriptions. Unfortunately, adapting existing index structuresto solve this problem results in either an unacceptable space overhead ora significant performance degradation. We thus propose two novel indexstructures that are both compact and efficient. Our experimental evaluationshows that the proposed structures provide a scalable basis for designingranked pub/sub systems.

Services