Exploit sequencing to accelerate hot XML query pattern mining

ABSTRACT

Speeding up query evaluation in large XML repositories becomes a challenging and all-important problem with vast XML-related applications arising. Upon discovery of hot XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Previous algorithms for finding hot query patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present, SOLARIA, an efficient algorithm for mining hot XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. With the motivation of indexing and caching in XML query optimization, we also propose the derived algorithm SOLARIA for mining hot "closed" XML query patterns which provide compact and complete structure information. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA over the previous known alternative. SOLARIA is also linearly scalable in terms of XML queries' size.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: T. Asai, K. Abe, S. Kawasoe, et. al. Efficient Substructure Discovery from Large Semi-structured Data. Proc. of the 2nd SIAM Int. Conf. on Data Mining, 2002, Arlington, VA, USA.
• 3: Jay Ayres , Jason Flannick , Johannes Gehrke , Tomi Yiu, Sequential PAttern mining using a bitmap representation, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775109]
• 4: C. Bettini, X. Wang, and S. Jajodia, Mining temporal relationals with multiple granularities in time sequences. Data Engineering Bulletin, 1998.
• 5: D. Chamberlin, D. Florescu, J. Robie, J. Simon, and M. Stefanescu. XQuery: A Query Language for XML W3C working draft, 2001.
• 6: Qun Chen , Andrew Lim , Kian Win Ong, D(k)-index: an adaptive structural summary for graph-structured data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872776]
• 7: J. Clark and S. DeRose. XML Path Language (XPath) version 1.0 W3C recommendation, 1999.
• 8: L. Dehaspe, H. Toivonen, R. D. King. Finding Frequent Substructures in Chemical Compounds. Proc. of 4th Int. Conf. on Knowledge Discovery and Data Mining, Aug. 1998, New York, New York, USA.
• 9: Efficient Mining of Partial Periodic Patterns in Time Series Database, Proceedings of the 15th International Conference on Data Engineering, p.106, March 23-26, 1999
• 10: Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347167]
• 11: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 12: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 13: Florent Masseglia , Fabienne Cathala , Pascal Poncelet, The PSP Approach for Mining Sequential Patterns, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.176-184, September 23-26, 1998
• 14: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 15: Banu Özden , Sridhar Ramaswamy , Abraham Silberschatz, Cyclic Association Rules, Proceedings of the Fourteenth International Conference on Data Engineering, p.412-421, February 23-27, 1998
• 16: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 17: S. Picciotto. How to Encode a Tree. PhD thesis, University of California, San Diego, 1999.
• 18: 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
• 19: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 20: Alexandre Termier , Marie-Christine Rousset , Michèl Sebag, TreeFinder: a First Step towards XML Data Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.450, December 09-12, 2002
• 21: Jianyong Wang , Jiawei Han, BIDE: Efficient Mining of Frequent Closed Sequences, Proceedings of the 20th International Conference on Data Engineering, p.79, March 30-April 02, 2004
• 22: W. Wang, H. Jiang, H. Lu, and J. X. Yu. PBiTree coding and efficient processing of containment joins. Proc. of the 19th Int. Conf. on Data Engineering, Mar. 2003, Bangalore, India.
• 23: 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]
• 24: X. Yan, J. Han, R. Afshar, CloSpan: Mining Closed Sequential Patterns in Large Databases. Proc. of the 3rd SIAM Int. Conf. on Data Mining, May 2003, San Francisco, CA, USA.
• 25: L. H. Yang, M. L. Lee, W. Hsu. Efficient Mining of XML Query Patterns for Caching. Proc. of the 29th Int. Conf. on Very Large Data Bases, Sept. 2003, Berlin, Germany.
• 26: Liang Huai Yang , Mong Li Lee , Wynne Hsu , Sumit Acharya, Mining Frequent Quer Patterns from XML Queries, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.355, March 26-28, 2003
• 27: Jiong Yang , Wei Wang , Philip S. Yu , Jiawei Han, Mining long sequential patterns in a noisy environment, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564738]
• 28: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design