Paper Info
Title
Efficiently evaluating graph constraints in content-based publish/subscribe
Abstract
We introduce the problem of evaluating graph constraints in content-based publish/subscribe (pub/sub) systems. This problem formulation extends traditional content-based pub/sub systems in the following manner: publishers and subscribers are connected via a (logical) directed graph G with node and edge constraints, which limits the set of valid paths between them. Such graph constraints can be used to model a Web advertising exchange (where there may be restrictions on how advertising networks can connect advertisers and publishers) and content delivery problems in social networks (where there may be restrictions on how information can be shared via the social graph). In this context, we develop efficient algorithms for evaluating graph constraints over arbitrary directed graphs G. We also present experimental results that demonstrate the effectiveness and scalability of the proposed algorithms using a realistic dataset from Yahoo!'s Web advertising exchange.
Year
DOI
Venue
2011
10.1145/1963405.1963476
WWW
Keywords
Field
DocType
pub sub,publish subscribe,directed graph,indexation,social network,indexing
Data mining,Graph database,World Wide Web,Social graph,Social network,Computer science,Search engine indexing,Directed graph,Wait-for graph,Graph (abstract data type),Scalability
Conference
Citations 
PageRank 
References 
3
0.40
21
Authors
7
Name
Order
Citations
PageRank
Andrei Broder17357920.20
Shirshanka Das232626.28
Marcus Fontoura3111661.74
Bhaskar Ghosh430624.02
Vanja Josifovski52265148.84
Jayavel Shanmugasundaram63555244.00
Sergei Vassilvitskii72750139.31