TL;DR
This paper introduces "ranked publish/subscribe" (ranked pub/sub), a new paradigm for matching events to subscriptions where only the "best" matches are desired, not all of them. They propose novel index structures, the IR-tree and SOPT-R-tree, that efficiently handle this ranked retrieval for multi-dimensional interval data, offering significant improvements in time and space complexity over existing methods.
What Problem Does This Paper Address?
Traditional publish/subscribe (pub/sub) systems operate on a binary matching principle: an event either matches a subscription or it doesn't. All matching subscriptions are then returned. However, many emerging applications, such as targeted web advertising, online job matching, and application-level routers, require a more nuanced approach. In these scenarios, only the top-k "best" matching subscriptions are relevant due to display limitations or efficiency concerns. For instance, in advertising, an incoming user might match dozens of ads, but only a few can be shown. The "best" can be defined by various criteria like relevance, profitability, or advertiser priority. This paper addresses the challenge of efficiently implementing such ranked matching in pub/sub systems, particularly for multi-dimensional interval-based subscriptions and point-based events.
Methods
The authors propose a novel approach that leverages multi-dimensional interval indexing. Instead of adapting existing binary matching indices, they focus on creating "scored interval indices" for each dimension. These indices are designed to efficiently retrieve intervals containing a query point, ordered by their score.
Key contributions include:
- Formalization of Ranked Pub/Sub: Defining the problem where subscriptions have scores and the goal is to retrieve top-k matches.
- Scored Interval Index Structures:
- Scored Interval Tree: An adaptation of standard interval trees that sorts intervals by score.
- Scored Segment Tree: An adaptation of segment trees, efficient but with higher space complexity.
- Scored R-Tree: An adaptation of R-trees that groups intervals by score, but can suffer from "holes" leading to inefficient traversal.
- Novel Index Structures:
- IR-Tree (Interval R-tree): A hybrid structure that uses R-trees within interval tree nodes to index intervals. It offers a good balance of time and space efficiency and supports incremental updates.
- SOPT-R-Tree (Score-Optimal R-tree): A carefully constructed R-tree that rearranges intervals to minimize "holes" and achieve optimal query time for ranked retrieval. It achieves near-optimal space complexity and significantly faster query times.
- Fagin's Threshold Algorithm: Used in conjunction with the dimensional indices to aggregate scores and efficiently find the top-k subscriptions.
Datasets
The authors used a synthetically generated subscription workload for their experiments. They generated subscriptions as hyper-rectangles and queries as points in a d-dimensional space. The data generation process involved a d-dimensional Zipfian data generator, allowing control over parameters like dimensionality, number of subscriptions, and subscription overlap (controlled by skewlength). They also mention having access to a real dataset from Yahoo!'s Behavioral Targeting group but found it unsuitable for their work due to limitations in specifying arbitrary intervals.
Key Insights and Ideas
- The "Best" Matters: The core insight is that in many real-world applications, returning all matches is inefficient and unnecessary; focusing on the top-k is crucial.
- Dimensionality vs. Overlap Tradeoff: The performance of different index structures varies significantly with the dimensionality of the data and the degree of overlap between subscriptions.
- "Holes" in R-Trees: A key challenge with score-sorted R-trees is the presence of "holes" (regions covered by an R-tree node but containing no actual intervals), which can severely degrade query performance. The SOPT-R-tree directly addresses this by intelligently rearranging intervals.
- Space-Time Tradeoffs: The paper highlights a clear tradeoff between space efficiency and query time. Segment trees are space-inefficient but fast, while interval and R-trees are space-efficient but can be slow for ranked queries. The proposed IR-tree and SOPT-R-tree aim to achieve the best of both worlds.
- Intervals vs. Points: The problem is fundamentally different from nearest-neighbor search because it involves indexing intervals (subscriptions) and querying with points (events), requiring specialized index structures.
Key Results
- SOPT-R-tree Performance: The SOPT-R-tree consistently outperformed other methods, offering up to a 2x speedup over other approaches in experiments.
- IR-Tree Performance: The IR-tree was a close second to the SOPT-R-tree, offering similar benefits with the added advantage of supporting incremental updates.
- Space Efficiency: The Segment Tree was found to be highly space-inefficient, becoming impractical for large datasets. The IR-tree and SOPT-R-tree (as an R-tree variant) offered low space overhead, with the IR-tree being at most twice the size of a standard interval tree.
- Dimensionality Impact: As dimensionality increased, the performance of all indices converged, a manifestation of the "dimensionality curse." However, for reasonable dimensions (1-4), SOPT-R-tree and IR-tree showed significant benefits.
- Subscription Overlap Impact: Increasing subscription overlap (lower
skewlength) generally benefited interval-based indices but degraded the performance of standard scored R-trees due to increased "holes." The SOPT-R-tree, however, handled overlap well due to its intelligent rearrangement. - Build Times: Index build times were generally fast, under a minute per dimension even for a million subscriptions.
Limitations and Future Work
- Updateability of SOPT-R-Tree: The authors acknowledge that the SOPT-R-tree's performance relies on a carefully constructed arrangement, making incremental updates (insertions/deletions) challenging as they can drastically alter the constraint graph. They suggest IR-trees as a better option for updateable scenarios.
- More Expressive Subscriptions: Future work could explore subscriptions based on XML hierarchical documents or those mixing structural and content filters.
- More Expressive Events: Handling events that are themselves intervals or have uncertainty (e.g., probabilistic ranges) requires new index structures.
- Score Updates: The current structures do not efficiently support dynamic updates to subscription scores, which is important for applications like online advertising.
- Scaling to High Dimensions: For hundreds of dimensions, current multi-dimensional indexing approaches are insufficient, necessitating new techniques like dimensionality reduction or specialized multi-dimensional scored indices.
Summary updated