TWIX: twig structure and content matching of selective queries using binary labeling

ABSTRACT

XML queries specify predicates on the content and the structure of the elements of tree-structured XML documents. Hence, discovering the occurrences of twig (tree structure) query patterns is a core operation for XML query processing. In this paper, we propose a novel technique for matching XML twig query patterns, named TWIX, which results in a substantial reduction of the search space, response time, size and structure invariance through a distributed binary labeling and tree traversal algorithm. Furthermore, TWIX benefits from an interactive graphical user interface for twig query matching.

REFERENCES

• 1: S. A. Aghili, H. Li, D. Agrawal and A. El Abbadi, MARS: A Matching and Ranking System for XML Content and Structure Retrieval. Technical Report 2005--11, UCSB (2005).
• 2: 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. ICDE, 141--152 (2002).
• 3: Shurug Al-Khalifa , Cong Yu , H. V. Jagadish, Querying structured text in an XML database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872761]
• 4: S. Alstrup, C. Gavoille, H. Kaplan and T. Rauhe, Nearest Common Ancestors: A Survey and a New Distributed Algorithm. Theory of Computing Systems 37, 441--456 (2002).
• 5: Chavdar Botev , Sihem Amer-Yahia , Jayavel Shanmugasundaram, A TeXQuery-based XML full-text search engine, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007710]
• 6: 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]
• 7: S. Chien, Z. Vagena, D. Zhang, V. J. Tsotras and C. Zaniolo, Efficient Structural Joins on Indexed XML Documents. VLDB, 263--274 (2002).
• 8: 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]
• 9: H. Jiang, W. Wang, H. Lu and J. X. Yu, Holistic Twig Joins on Indexed XML Documents. VLDB, 273--284 (2003).
• 10: DBLP Bibliography Server, http://dblp.uni-trier.de/.
• 11: Y. Li and C. Yu and H. V. Jagadish, Scheme-Free XQuery. VLDB, 72--83 (2004).
• 12: 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
• 13: Jiaheng Lu , Ting Chen , Tok Wang Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031272]
• 14: Jiaheng Lu , Tok Wang Ling , Chee-Yong Chan , Ting Chen, From region encoding to extended dewey: on efficient processing of XML twig pattern matching, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Praveen Rao , Bongki Moon, PRIX: Indexing And Querying XML Using Prüfer Sequences, Proceedings of the 20th International Conference on Data Engineering, p.288, March 30-April 02, 2004
• 16: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 17: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 18: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 19: Yu Xu , Yannis Papakonstantinou, Efficient keyword search for smallest LCAs in XML databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066217]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
      H.3.3 Information Search and Retrieval
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design