An Implementation of Tree Match Algorithm for Effective Xml Tree Pattern Matching

IJCSEC Front Page

XML (Extensible Markup Language) has become a popular standard for storing and sharing data across various platforms. The emergence of XML promised significant advances in B2B (Business-to-Business) integration. Due to its popularity there is an increasing demand for the efficient query processing on XML File. For performing query processing operations on XML file an input XML Dataset is required. Such an XML files are viewed as an XML Tree using XML DOM Parser. The core operation of our project is to perform Pattern Matching in XML Tree. The Existing XML Tree Pattern Matching Techniques uses XQuery, XPath and TwigStack Algorithm. But XQuery and XPath are complicated to understand by non-database users. In the proposed system Keyword Search Technique and TreeMatch algorithm is used to perform exact pattern matching for text, images and audio files. An XML Search engine is created to achieve this. The downloading time of images and audio files are compared with the local search engine. It is shown that XML Search engine takes less downloading time.

Keywords: XML, TreeMatch, TwigStack, XQuery, XPath..


  1. Wen-Chiao, Hsuand I. H. Kasimoglu, “A Compacted Indexing Scheme for efficient query evaluation of XML Documents ” Elsevier Journal., vol. 241, no. 4, pp. 195-211, Mar. 2013.
  2. J. Hidders, “Satisfiability of XPath Expressions ” Proc. Ninth Int’l Workshop Database Programming Languages (DBPL ’03), pp. 21-36, Oct.2004.
  3. J. Yao and M. Zhang, “A Fast Tree Pattern Matching Algorithm for XML Query” Proc. IEEE/WIC/ACM Int’l Conf. Web Intelligence(WI ’04), pp. 235-241, Jan. 2004.
  4. L.V.S. Lakshmanan, “XML Tree Pattern, XML Twig Query” Encyclopedia of Database Systems, pp. 3637-3640, Springer, 2009.
  5. Mirjana Mazuran, Elisa Quintarelli, and Letizia Tanca, “Data Mining for XML Query Answering Support” IEEE Transactions on Knowledge and Data Engineering, pp.1393-1407,2012.
  6. D. Beech, A. Malhotra, and M. Rys, “A Formal Data Model and Algebra for XML” technical report, W3C XML Query Working Group Note, 1999.
  7. L.V.S. Lakshmanan, G. Ramesh, H. Wang, and Z.J. Zhao, “On Testing Satisfiability of Tree Pattern Queries” Proc. 30th Int’l Conf. Very Large Data Bases (VLDB ’04), pp. 120-131, 2004.
  8. L. Quin, “Extensible Markup Language (XML)” World Wide Web Consortium (W3C),, 2006.
  9. W. Wang, H. Wang, H. Lu, H. Jiang, X. Lin, and J. Li, “Efficient processing of XML path queries using the disk-based F&B index” in VLDB, pages 145–156, 2005.
  10. Jaihaeng Lu, “XML Tree Pattern Matching: Theories and Algorithms” IEEE Transactions on Knowledge and Data Engineering, pp.1393-1407, June, 2012.
  11. Xiaoying Wu, Stefanos Souldatos, “Extended XML Tree Pattern Matching” Data and Knowledge Eng., vol. 64, no. 3, pp. 580-599, 2011.
  12. R. Goldman and J. Widom, “Data Guides: Enabling Query Formulation and Optimization in Semi structured Databases” Proc. 23rd Int’l Conf. Very Large Data Bases, pp. 436-445, 1997.
  13. R. Baca, M. Kra´tk y, and V. Sna´sel, “On the Efficient Search of an XML Twig Query in Large Data Guide Trees” Proc. 12th Int’l Database Eng. and Applications Symposium (IDEAS ’08), pp. 149-158, 2008.
  14. Y. Chen and D. Che, “Efficient Processing of XML Tree Pattern Queries” Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 10, no. 5, pp. 738-743, 2006.
  15. Li et al. “Queries and Computation on the Web” Theoretical Computer Science, vol. 239, no. 2, pp. 231-255, 2000.
  16. C.Y. Chan, W. Fan, P. Felber, M.N. Garofalakis, and R. Rastogi, “Tree Pattern Aggregation for Scalable XML Data Dissemination” Proc. 28th Int’l Conf. Very Large Data Bases (VLDB ’02), pp. 826-837,2002.
  17. J.D. Ullman, Principles of Database and Knowledge-Base Systems, vol. 1. Computer Science Press, 1988.
  18. Y. Chen and D. Che, “Minimization of XML Tree Pattern Queries in the Presence of Integrity Constraints” Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 10, no. 5, pp. 744-751, 2006.
  19. S. Al-Khalifa, H.V. Jagadish, J.M. Patel, Y. Wu, N. Koudas, and D. Srivastava “Structural Joins: A Primitive for Efficient XML Query Pattern Matching,” Proc. 18th Int’l Conf. Data Eng. (ICDE ’02), pp. 141- 149, 2002.
  20. Giorgio Busatto, “Efficient Memory Representation of XML Documents” Proc. 15th Int’l Conf. Database Systems for Advanced Applications (DASFAA’10), pp. 170-178, 2010.
  21. Sravan Kumar , Madhu “Efficient Handling of XML Tree Pattern Matching Queries – A Holistic Approach” International Journal of Advanced Research in Computer and Communication Volume 1 Issue 8, Oct 2012.
  22. Xiaoying Wu, Stefanos Souldatos, “XML Tree Pattern Processing Algorithms” Data and Knowledge Eng., vol. 64, no. 3, pp. 580-599, 2011.