EXPedite: a system for encoded XML processing

ABSTRACT

As XML becomes an increasingly popular format for information exchange, the efficient processing of broadcast XML data on a constrained device (for example, a cell phone or a PDA) becomes a critical task. In this paper we present the EXPedite system: a new model of data processing in an information exchange environment, which "migrates" the power of the data-sending server to receivers for efficient processing. It consists of a simple and general encoding scheme for servers, and streaming query processing algorithms on encoded XML stream for data receivers with constrained computing abilities. Experiments show the impressive performance of EXPedite.

REFERENCES

• 1: Moving Picture Experts Group (MPEG), 2003. http://www.chiariglione.org/mpeg/index.htm.
• 2: TV-Anytime Forum, 2003. http://www.tv-anytime.org.
• 3: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 4: I. Avila-Campillo, T. J. Green, A. Gupta, M. Onizuka, D. Raven, and D. Suciu. XMLTK: An XML Toolkit for Scalable XML Stream Processing. In Programming Language Technologies for XML(PLAN-X), 2002.
• 5: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 6: J. M. Bull , L. A. Smith , L. Pottage , R. Freeman, Benchmarking Java against C and Fortran for scientific applications, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.97-105, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376823]
• 7: Efficient Filtering of XML Documents with XPath Expressions, Proceedings of the 18th International Conference on Data Engineering, p.235, February 26-March 01, 2002
• 8: S.-Y. Chien, Z. Vagena, D. Zhang, V. J. Tsotras, and C. Zaniolo. Efficient Structural Joins on Indexed XML Documents. In Proceedings of VLDB, 2002.
• 9: J. Clark and S. DeRose. XML Path language (XPath), November 1999. http://www.w3.org/TR/xpath.
• 10: David DeHaan , David Toman , Mariano P. Consens , M. Tamer Özsu, A comprehensive XQuery to SQL translation using dynamic interval encoding, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872832]
• 11: Y. Diao and M. J. Franklin. Query Processing for High-Volume XML Message Brokering. In Proceedings of VLDB, 2003.
• 12: Georgetown Protein Information Resource. Protein Sequence Database, 2001. http://www.cs.washington.edu/research/xmldatasets/.
• 13: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 14: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 15: Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564705]
• 16: IBM. XML Generator, 1999. http://www.alphaworks.ibm.com/tech/xmlgenerator.
• 17: H. Jiang, H. Lu, W. Wang, and B. C. Ooi. XR-Tree: Indexing XML Data for Efficient Structural Joins. In Proceedings of ICDE, 2003.
• 18: Laks V. S. Lakshmanan , Sailaja Parthasarathy, On Efficient Matching of Streaming XML Documents and Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.142-160, March 25-27, 2002
• 19: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 20: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 21: B. Ludascher, P. Mukhopadhayn, and Y. Papakonstantinou. A Transducer-Based XML Query Processor. In Proceedings of VLDB, 2002.
• 22: Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, XPRESS: a queriable compression for XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872775]
• 23: D. Olteanu, T. Kiesling, and F. Bry. An Evaluation of Regular Path Expressions with Qualifiers against XML Streams. In Proceedings of ICDE, 2003.
• 24: 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]
• 25: L. Quin. W3C Workshop on Binary Interchange of XML Information Item Sets. http://www.w3.org/2003/08/binary-interchange-workshop/Report.html.
• 26: J. Siméon and M. Fernández. Galax. http://db.bell-labs.com/galax.
• 27: XGRIND: A Query-Friendly XML Compressor, Proceedings of the 18th International Conference on Data Engineering, p.225, February 26-March 01, 2002
• 28: W3C. XML Query Use Cases, 2003. http://www.w3.org/TR/xquery-use-cases.
• 29: W. Wang, H. Jiang, H. Lu, and J. X. Yu. PBiTree Coding and Efficient Processing of Containment Joins. In Proceedings of ICDE, 2003.
• 30: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Design, Performance

Keywords:
XML, XPath, binary encoding, query processing