Xml data dissemination using automata on top of structured overlay networks

ABSTRACT

We present a novel approach for filtering XML documents using nondeterministic finite automata and distributed hash tables. Our approach differs architecturally from recent proposals that deal with distributed XML filtering; they assume an XML broker architecture, whereas our solution is built on top of distributed hash tables. The essence of our work is a distributed implementation of YFilter, a state-of-the-art automata-based XML filtering system on top of Chord. We experimentally evaluate our approach and demonstrate that our algorithms can scale to millions of XPath queries under various filtering scenarios, and also exhibit very good load balancing properties.

REFERENCES

• 1: DBLP XML records. http://dblp.uni-trier.de/xml/.
• 2: IBM XML Generator. http://www.alphaworks.ibm.com/tech/xmlgenerator.
• 3: XMark: An XML Benchmark Project. http://www.xml-benchmark.org/.
• 4: YFilter 1.0 release. http://yfilter.cs.umass.edu/code_release.htm.
• 5: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 6: Denilson Barbosa , Laurent Mignet , Pierangelo Veltri, Studying the XML Web: Gathering Statistics from an XML Sample, World Wide Web, v.9 n.2, p.187-212, June 2006 [doi>10.1007/s11280-006-8437-6]
• 7: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 8: Angela Bonifati , Ugo Matrangolo , Alfredo Cuzzocrea , Mayank Jain, XPath lookup queries in P2P networks, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031464]
• 9: N. Bruno, L. Gravano, N. Koudas, and D. Srivastava. Navigation- vs. Index-Based XML Multi-Query Processing. In ICDE 2003.
• 10: C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient Filtering of XML Documents with XPath Expressions. In ICDE 2002.
• 11: Chee Yong Chan , Yuan Ni, Efficient xml data dissemination with piggybacking, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247562]
• 12: R. Chand , P. A. Felber, A Scalable Protocol for Content-Based Routing in Overlay Networks, Proceedings of the Second IEEE International Symposium on Network Computing and Applications, p.123, April 16-18, 2003
• 13: J. Clark and S. J. DeRose. XML Path Language (XPath) Version 1.0. World Wide Web Consortium, Recommendation, November 1999.
• 14: Mariano P. Consens , Tova Milo, Optimizing queries on files, ACM SIGMOD Record, v.23 n.2, p.301-312, June 1994
• 15: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 16: Yanlei Diao , Shariq Rizvi , Michael J. Franklin, Towards an internet-scale XML dissemination service, Proceedings of the Thirtieth international conference on Very large data bases, p.612-623, August 31-September 03, 2004, Toronto, Canada
• 17: Pascal Felber , Chee-Yong Chan , Minos Garofalakis , Rajeev Rastogi, Scalable Filtering of XML Data for Web Services, IEEE Internet Computing, v.7 n.1, p.49-57, January 2003 [doi>10.1109/MIC.2003.1167339]
• 18: Daniela Florescu , Chris Hillery , Donald Kossmann , Paul Lucas , Fabio Riccardi , Till Westmann , J. Carey , Arvind Sundararajan, The BEA streaming XQuery processor, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.294-315, September 2004 [doi>10.1007/s00778-004-0137-1]
• 19: Leonidas Galanis , Yuan Wang , Shawn R. Jeffery , David J. DeWitt, Locating data sources in large distributed systems, Proceedings of the 29th international conference on Very large data bases, p.874-885, September 09-12, 2003, Berlin, Germany
• 20: Xueqing Gong , Weining Qian , Ying Yan , Aoying Zhou, Bloom Filter-Based XML Packets Filtering for Millions of Path Queries, Proceedings of the 21st International Conference on Data Engineering, p.890-901, April 05-08, 2005 [doi>10.1109/ICDE.2005.26]
• 21: Todd J. Green , Ashish Gupta , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML streams with deterministic automata and stream indexes, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042051]
• 22: 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
• 23: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 24: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 25: Shuang Hou , H.-Arno Jacobsen, Predicate-based Filtering of XPath Expressions, Proceedings of the 22nd International Conference on Data Engineering, p.53, April 03-07, 2006 [doi>10.1109/ICDE.2006.115]
• 26: G. Koloniari and E. Pitoura. Content-based Routing of Path Queries in Peer-to-Peer Systems. In EDBT 2004.
• 27: Mirella M. Moro , Petko Bakalov , Vassilis J. Tsotras, Early profile pruning on XML-aware publish-subscribe systems, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 28: Feng Peng , Sudarshan S. Chawathe, XPath queries on streaming data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872810]
• 29: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
• 30: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.149-160, October 2001
• 31: 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]
• 32: Hiroyuki Uchiyama , Makoto Onizuka , Takashi Honishi, Distributed XML Stream Filtering System with High Scalability, Proceedings of the 21st International Conference on Data Engineering, p.968-977, April 05-08, 2005 [doi>10.1109/ICDE.2005.50]
• 33: Aoying Zhou , Weining Qian , Xueqing Gong , Minqi Zhou, Sonnet: an efficient distributed content-based dissemination broker, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247618]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data description languages (DDL); Query languages

General Terms:
Algorithms, Design, Experimentation

Keywords:
automata, load balancing, structured overlay networks, xml data dissemination