A Survey of XML Tree Patterns <s> Frequent subtree mining algorithms <s> As XML prevails over the Internet, the efficient retrieval of XML data becomes important. Research to improve query response times has been largely concentrate on indexing XML documents and processing regular path expressions. Another approach is to discover frequent query patterns since the answers to these queries can be stored and indexed. Mining frequent query patterns requires more than simple tree matching since the XML queries involves special characters such as "*" or "//". In addition, the matching process can be expensive since the search space is exponential to the size of XML schema. In this paper, we present two mining algorithms, XQPMiner and XQPMinerTID, to discover frequent query pattern frees from a large collection of XML queries efficiently. Both algorithms exploit schema information to guide the enumeration of candidate subtrees, thus eliminating unnecessary node expansions. Experiments results show that the proposed methods are efficient and have good scalability. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Frequent subtree mining algorithms <s> As XML becomes ubiquitous, the efficient retrieval of XML data becomes critical. Research to improve query response time has been largely concentrated on indexing paths, and optimizing XML queries. An orthogonal approach is to discover frequent XML query patterns and cache their results to improve the performance of XML management systems. In this paper, we present an efficient algorithm called FastXMiner, to discover frequent XML query patterns. We develop theorems to prove that only a small subset of the generated candidate patterns needs to undergo expensive tree containment tests. In addition, we demonstrate how the frequent query patterns can be used to improve caching performance. Experiments results show that FastXMiner is efficient and scalable, and caching the results of frequent patterns significantly improves the query response time. <s> BIB002 </s> A Survey of XML Tree Patterns <s> Frequent subtree mining algorithms <s> With the proliferation of XML-based data sources available across the Internet, it is increasingly important to provide users with a data warehouse of XML data sources to facilitate decision-making processes. Due to the extremely large amount of XML data available on web, unguided warehousing of XML data turns out to be highly costly and usually cannot well accommodate the users' needs in XML data acquirement. In this paper, we propose an approach to materialize XML data warehouses based on frequent query patterns discovered from historical queries issued by users. The schemas of integrated XML documents in the warehouse are built using these frequent query patterns represented as Frequent Query Pattern Trees (FreqQPTs). Using hierarchical clustering technique, the integration approach in the data warehouse is flexible with respect to obtaining and maintaining XML documents. Experiments show that the overall processing of the same queries issued against the global schema become much efficient by using the XML data warehouse built than by directly searching the multiple data sources. <s> BIB003 </s> A Survey of XML Tree Patterns <s> Frequent subtree mining algorithms <s> Since tree-structured data such as XML files are widely used for data representation and exchange on the Internet, discovering frequent tree patterns over tree-structured data streams becomes an interesting issue. In this paper, we propose an online algorithm to continuously discover the current set of frequent tree patterns from the data stream. A novel and efficient technique is introduced to incrementally generate all candidate tree patterns without duplicates. Moreover, a framework for counting the approximate frequencies of the candidate tree patterns is presented. Combining these techniques, the proposed approach is able to compute frequent tree patterns with guarantees of completeness and accuracy. <s> BIB004
One of the first frequent RST mining algorithm, XQPMiner BIB001 , operates like the famous frequent itemset mining algorithm Apriori  . XQPMiner initializes by enumerating all frequent 1-edge RSTs. Then, each further step i is subdivided in two substeps: 1) candidate i-edge RSTs are built from (i − 1)-edge RSTs and filtered with respect to the minimum support; 2) each remaining i-edge RST is tested for containment in each TP of C to compute its support. FastXMiner optimizes this process by constructing a global query pattern tree (G-QTP, Section 3.2.1) over C. Then, a tree-encoding scheme is applied on the G-QTP to partition candidate RSTs into equivalence classes. The authors show that only single-branch candidate RSTs need to be matched against the TPs from C, which leads to a large reduction in the number of tree inclusion tests BIB002 . MineFreq further builds upon this principle by mining frequent RST sets BIB003 . A frequent RST set must satisfy two requirements: 1) support requirement: sup(r 1 , r 2 , ..., r n ) ≥ minsup; 2) confidence requirement: ∀r i , f req(r1,r2,...,rn) f req(ri) ≥ minconf , where minconf is a minimum confidence user-specified threshold. The algorithm again proceeds by level, the n-itemset RST candidates being generated by joining (n − 1)itemset frequent RSTs. Candidates in which one or more (n − 1)-subsets are infrequent are pruned, for they cannot be frequent. Remaining candidates are then filtered with respect to support and confidence. Finally, frequent TPs are built by joining all RSTs in each frequent RST set. Eventually, Stream Tree Miner (STMer) mines frequent labeled ordered subtrees over a tree-structured data stream BIB004 . Its main contribution lies in candidate subtree generation, which is suitably incremental.