Skip to main content

Subscriber assignment for wide-area content-based publish/subscribe

Publication ,  Journal Article
Yu, A; Agarwal, PK; Yang, J
Published in: Proceedings - International Conference on Data Engineering
June 6, 2011

We study the problem of assigning subscribers to brokers in a wide-area content-based publish/subscribe system. A good assignment should consider both subscriber interests in the event space and subscriber locations in the network space, and balance multiple performance criteria including bandwidth, delay, and load balance. The resulting optimization problem is NP-complete, so systems have turned to heuristics and/or simpler algorithms that ignore some performance criteria. Evaluating these approaches has been challenging because optimal solutions remain elusive for realistic problem sizes. To enable proper evaluation, we develop a Monte Carlo approximation algorithm with good theoretical properties and robustness to workload variations. To make it computationally feasible, we combine the ideas of linear programming, randomized rounding, coreset, and iterative reweighted sampling. We demonstrate how to use this algorithm as a yardstick to evaluate other algorithms, and why it is better than other choices of yardsticks. With its help, we show that a simple greedy algorithm works well for a number of workloads, including one generated from publicly available statistics on Google Groups. We hope that our algorithms are not only useful in their own right, but our principled approach toward evaluation will also be useful in future evaluation of solutions to similar problems in content-based publish/subscribe. © 2011 IEEE.

Duke Scholars

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

June 6, 2011

Start / End Page

267 / 278
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Yu, A., Agarwal, P. K., & Yang, J. (2011). Subscriber assignment for wide-area content-based publish/subscribe. Proceedings - International Conference on Data Engineering, 267–278. https://doi.org/10.1109/ICDE.2011.5767882
Yu, A., P. K. Agarwal, and J. Yang. “Subscriber assignment for wide-area content-based publish/subscribe.” Proceedings - International Conference on Data Engineering, June 6, 2011, 267–78. https://doi.org/10.1109/ICDE.2011.5767882.
Yu A, Agarwal PK, Yang J. Subscriber assignment for wide-area content-based publish/subscribe. Proceedings - International Conference on Data Engineering. 2011 Jun 6;267–78.
Yu, A., et al. “Subscriber assignment for wide-area content-based publish/subscribe.” Proceedings - International Conference on Data Engineering, June 2011, pp. 267–78. Scopus, doi:10.1109/ICDE.2011.5767882.
Yu A, Agarwal PK, Yang J. Subscriber assignment for wide-area content-based publish/subscribe. Proceedings - International Conference on Data Engineering. 2011 Jun 6;267–278.

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

June 6, 2011

Start / End Page

267 / 278