Internet scale string attribute publish/subscribe data networks

ABSTRACT

With this work we aim to make a three-fold contribution. We first address the issue of supporting efficiently queries over string-attributes involving prefix, suffix, containment, and equality operators in large-scale data networks. Our first design decision is to employ distributed hash tables (DHTs) for the data network's topology, harnessing their desirable properties. Our next design decision is to derive DHT-independent solutions, treating DHT as a black box. Second, we exploit this infrastructure to develop efficient content based publish/subscribe systems. The main contribution here are algorithms for the efficient processing of queries (subscriptions) and events (publications). Specifically, we show that our subscription processing algorithms require O(logN) messages for a N-node network, and our event processing algorithms require O(l x logN) messages (with l being the average string length).Third, we develop algorithms for optimizing the processing of multi-dimensional events, involving several string attributes. Further to our analysis, we provide simulation-based experiments showing promising performance results in terms of number of messages, required bandwidth, load balancing, and response times.

REFERENCES

• 1: Karl Aberer, P-Grid: A Self-Organizing Access Structure for P2P Information Systems, Proceedings of the 9th International Conference on Cooperative Information Systems, p.179-194, September 05-07, 2001
• 2: An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.262, May 31-June 04, 1999
• 3: Antonio Carzaniga , Alexander L. Wolf, Forwarding in a content-based network, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863975]
• 4: M. Castro, P. Druschel, A. Kermarrec, and A. Rowstron. Scribe: A large-scale and decentralized application-level multicast infrastructure. Journal on Selected Areas in Communication, 2002.
• 5: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 6: Gianpaolo Cugola , Elisabetta Di Nitto , Alfonso Fuggetta, The JEDI Event-Based Infrastructure and Its Application to the Development of the OPSS WFMS, IEEE Transactions on Software Engineering, v.27 n.9, p.827-850, September 2001 [doi>10.1109/32.950318]
• 7: Prasanna Ganesan , Beverly Yang , Hector Garcia-Molina, One torus to rule them all: multi-dimensional queries in P2P systems, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017081]
• 8: Abhishek Gupta , Ozgur D. Sahin , Divyakant Agrawal , Amr El Abbadi, Meghdoot: content-based publish/subscribe over P2P networks, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 9: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 10: N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In USITS03, 2003.
• 11: R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, and I. Stoica. Querying the internet with pier. In VLDB'03, 2003.
• 12: G. Koloniari and E. Pitoura. Content-based routing of path queries in peer-to-peer systems. In EDBT'04.
• 13: S. W. Ng, B. C. Ooi, K. L. Tan, and A. Zhou. Peerdb: A p2p-based system for distributed data sharing. In ICDE'03, 2003.
• 14: V. Papadimos, D. Maier, and K. Tufte. Distributed query processing and catalogs for peer-to-peer systems. In Proc. CIDR'03, 2003.
• 15: 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
• 16: 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
• 17: 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
• 18: S. Shi, G. Yang, D. Wang, J. Yu, S. Qu, and M. Chen. Making peer-to-peer keyword searching feasible using multi-level partitioning. In IPTPS04, 2004.
• 19: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 20: D. Tam, R. Azimi, and H. Jacobsen. Building content-base publish/subscribe systems with distributed hash tables. In Proc. DBISP2P'03, 2003.
• 21: Wesley W. Terpstra , Stefan Behnel , Ludger Fiege , Andreas Zeidler , Alejandro P. Buchmann, A peer-to-peer approach to content-based publish/subscribe, Proceedings of the 2nd international workshop on Distributed event-based systems, June 08-08, 2003, San Diego, California [doi>10.1145/966618.966627]
• 22: P. Triantafillou and I. Aekaterinidis. Publish-subscribe over structured p2p networks. In DEBS 04, 2004.
• 23: 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
• 24: P. Triantafillou and A. Economidis. Subscription summaries for scalability and efficiency in publish/subscribe systems. In DEBS'02, 2002.P. Triantafillou and A. Economidis. Subscription summaries for scalability and efficiency in publish/subscribe systems. In DEBS'02, 2002.
• 25: P. Triantafillou, C. Xiruhaki, M. Koubarakis, and N. Ntarmos. Towards high performance peer-to-peer content and resource sharing systems. In CIDR'03.
• 26: Christos Tryfonopoulos , Stratos Idreos , Manolis Koubarakis, Publish/subscribe functionality in IR environments using structured overlay networks, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076090]
• 27: Beverly Yang , Patrick Vinograd , Hector Garcia-Molina, Evaluating GUESS and Non-Forwarding Peer-to-Peer Search, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.209-218, March 24-26, 2004
• 28: G. I. Zachary, N. Khandelwal, A. Kapur, and M. Cakir. Orchestra: Rapid, collaborative sharing of dynamic data. In CIDR'05, 2005.
• 29: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 30: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance

Keywords:
DHT networks, performance, publish-subscribe paradigm, string-attribute queries over DHTs