Interest clustering techniques for efficient event routing in large-scale settings

ABSTRACT

The publish/subscribe interaction paradigm is today becoming mainstream in a large number of very large scale applications like news syndication (with RSS) or massive multi-player games. These applications are often still implemented by means of centralized services that will hardly scale with the user growth expected in the next years. Modern publish/subscribe systems are striving to address these scalability needs to play a dominant role in this future market. A very important contribution, on the road to reach this goal, is given by the interest clustering techniques adopted by these systems. Interest clustering aims at putting in close applicative relationship groups of users sharing similar interests in order to reduce the effort needed to dispatch a message to group. This technique can be applied to event dissemination mechanisms based on filtering to reduce the total amount of messages generated during event routing and, consequently, improve the overall system performance. In this paper we explore this topic to discover the potentialities of interest clustering, to understand how it can be implemented in a publish/subscribe system, and to study, through a small focussed survey, the central role played by this technique in modern systems.

REFERENCES

• 1: Rss 2.0 specification.
• 2: Sebastien Baehni , Patrick Th. Eugster , Rachid Guerraoui, Data-Aware Multicast, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.233, June 28-July 01, 2004
• 3: Roberto Baldoni , Roberto Beraldi , Vivien Quema , Leonardo Querzoni , Sara Tucci-Piergiovanni, TERA: topic-based event routing for peer-to-peer architectures, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada [doi>10.1145/1266894.1266898]
• 4: Roberto Baldoni , Roberto Beraldi , Leonardo Querzoni , Antonino Virgillito, Efficient Publish/Subscribe Through a Self-Organizing Broker Overlay and its Application to SIENA, The Computer Journal, v.50 n.4, p.444-459, July 2007 [doi>10.1093/comjnl/bxm002]
• 5: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 6: M. Castro, P. Druschel, A. Kermarrec, and A. Rowston. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications, 20(8), October 2002.
• 7: Gregory Chockler , Roie Melamed , Yoav Tock , Roman Vitenberg, SpiderCast: a scalable interest-aware overlay for topic-based pub/sub communication, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada [doi>10.1145/1266894.1266899]
• 8: Étienne Rivière , Roberto Baldoni , Harry Li , José Pereira, Compositional gossip: a conceptual architecture for designing gossip-based applications, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007 [doi>10.1145/1317379.1317387]
• 9: Patrick Th. Eugster , Pascal A. Felber , Rachid Guerraoui , Anne-Marie Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys (CSUR), v.35 n.2, p.114-131, June 2003 [doi>10.1145/857076.857078]
• 10: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 11: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 12: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium, p.5-14, August 30-September 01, 2004
• 13: Lukasz Opyrchal , Mark Astley , Joshua Auerbach , Guruduth Banavar , Robert Strom , Daniel Sturman, Exploiting IP multicast in content-based publish-subscribe systems, IFIP/ACM International Conference on Distributed systems platforms, p.185-207, April 03-07, 2000, New York, New York, United States
• 14: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 15: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 16: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 17: Peter Triantafillou , Andreas Economides, Subscription Summarization: A New Paradigm for Efficient Publish/Subscribe Systems, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.562-571, March 24-26, 2004
• 18: S. Voulgaris, E. Rivière, A.-M. Kermarrec, and M. van Steen. Sub-2-sub: Self-organizing content-based publish and subscribe for dynamic and large scale collaborative networks. Research Report RR5772, INRIA, Rennes, France, December 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS