Efficient Mining of XML Query Patterns for Caching
Elsevier eBooksPublished 1 January 2003
Liang Huai Yang, Mong Li Lee, Wynne Hsu
Citations118
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Theorems are developed to prove that only a small subset of the generated candidate patterns needs to undergo expensive tree containment tests, and it is demonstrated how the frequent query patterns can be used to improve caching performance.
Abstract
This chapter discusses the efficient mining of XML query patterns for caching. 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. This chapter presents an efficient algorithm called Fast X-Miner, to discover frequent XML query patterns. This chapter develops theorems to prove that only a small subset of the generated candidate patterns needs to undergo expensive tree containment tests. In addition, it demonstrates how the frequent query patterns can be used to improve caching performance. Experiment results show that Fast X-Miner is efficient and scalable, and caching the results of frequent patterns significantly improves the query response time.
Keywords
Computer Science
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Frequent subgraph discovery
1,063 Citations2002M. Kuramochi, George Karypis
The empirical results show that the algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though it has to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
Holistic twig joins
875 Citations2002Nicolas Bruno, Nick Koudas +1 more
This paper proposes a novel holistic twig join algorithm, TwigStack, that uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern.
Structural joins: a primitive for efficient XML query pattern matching
779 Citations2003Shurug Al-Khalifa, H. V. Jagadish +4 more
It is shown that, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse, and this behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack- tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-MERge algorithms do not have the same guarantee.
Indexing and Querying XML Data for Regular Path Expressions
760 Citations2001Quanzhong Li, Bongki Moon
A new system for indexing and storing XML data based on a numbering scheme for elements that quickly determines the ancestor-descendant relationship between elements in the hierarchy of XML data is proposed.
Semantic Data Caching and Replacement
502 Citations1996Shaul Dar, Michael J. Franklin +3 more
A semantic model for client-side caching and replacement in a client-server database system and compared to page caching and tuple caching strategies is proposed and validated with a detailed performance study.
Efficiently mining frequent trees in a forest
467 Citations2002Mohammed J. Zaki
This work presents TREEMinER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list, and finds that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties.
Accelerating XPath location steps
442 Citations2002Torsten Grust
This work is a proposal for a database index structure that has been specifically designed to support the evaluation of XPath queries, capable to support all XPath axes and able to start traversals from arbitrary context nodes in an XML document.
Efficient Substructure Discovery from Large Semi-structured Data
363 Citations2002Tatsuya Asai, Kenji Abe +4 more
Covering indexes for branching path queries
307 Citations2002Raghav Kaushik, Philip Bohannon +2 more
This paper asks if the traditional relational query acceleration techniques of summary tables and covering indexes have analogs for branching path expression queries over tree- or graph-structured XML data and shows that the forward-and-backward index already proposed in the literature can be viewed as a structure analogous to a summary table or covering index.
XQuery
285 Citations2003Donald D. Chamberlin
This tutorial will provide an overview of the syntax and semantics of XQuery, as well as insight into the principles that guided the design of the language.
APEX
281 Citations2002Chin‐Wan Chung, Jun‐Ki Min +1 more
Experimental results with synthetic and real-life data sets clearly confirm that APEX improves query processing cost typically 2 to 54 times better than the existing indexes, with the performance gap increasing with the irregularity of XML data.
TreeFinder: a first step towards XML data mining
185 Citations2003Alexandre Termier, M.-C. Rousset +1 more
This paper considers the problem of searching frequent trees from a collection of tree-structured data modeling XML data, and shows that TreeFinder reaches completeness or falls short for a range of experimental settings.
Kyushu University Institutional Repository (QIR) (Kyushu University)Efficient Substructure Discovery from Large Semi-structed Data
183 Citations2001Tatsuya Asai, 達哉 浅井 +10 more
IEEE Transactions on Knowledge and Data EngineeringDiscovering structural association of semistructured data
139 Citations2000Ke Wang, Huiqing Liu
The discovery task is affected by structural features of semistructured data in a nontrivial way and traditional data mining frameworks are inapplicable.
The VLDB JournalSemantic caching of Web queries
74 Citations2000Boris Chidlovskii, Uwe M. Borghoff
This work studies the problem of semantic caching of Web queries and develops a caching mechanism for conjunctive Web queries based on signature files and develops the cache replacement strategy to treat situations when cached items differ in size and contribution when providing partial query answers.
XCache
67 Citations2002Li Chen, Elke A. Rundensteiner +1 more
A containment mapping process to incorporate type inference and subtyping mechanisms provided by XDuce to establish containment mappings between regular-expression-type-based pattern variables of two queries is designed, which is the first solution for XQuery processing using cached views.
Data & Knowledge EngineeringWeb log data warehousing and mining for intelligent web caching
59 Citations2001Francesco Bonchi, Fosca Giannotti +6 more
Journal of the ACMNonlinear pattern matching in trees
53 Citations1992R. Ramesh, I. V. Ramakrishnan
This paper presents new sequential algorithms for nonlinear pattern matching in trees that improves upon know tree pattern matching algorithms in important aspects such as time performance, ease of integration with several reduction strategies and ability to avoid unnecessary computation steps on match attempts that fail.
Columbia Academic Commons (Columbia University)Holistic Twig Joins: Optimal XML Pattern Matching
51 Citations2002Bruno, Nicolas, Koudas, Nick +1 more
Mining frequent query patterns from XML queries
50 Citations2003Liang Huai Yang, Mong Li Lee +2 more
Two mining algorithms are presented, XQPMiner and XZPMinerTID, to discover frequent query pattern frees from a large collection of XML queries efficiently, which exploit schema information to guide the enumeration of candidate subtrees, thus eliminating unnecessary node expansions.
Rule-assisted prefetching in Web-server caching
43 Citations2000Bin Lan, Stéphane Bressan +2 more
The main contribution lies in the design of a novel prefetching strategy, called RAP, which combines a set of association rules from the Web server's access log and outperforms existing schemes.
Automated discovery of active motifs in multiple RNA secondary structures
25 Citations1996Jason T. L. Wang, Bruce A. Shapiro +3 more
A method for discovering approximately common motifs in multiple RNA secondary structures using two optimization heuristics based on sampling and pattern matching techniques and demonstrating the utility of these algorithms to conducting the phylogenetic study of RNA sequences obtained from GenBank.
Tree subsumption: reasoning with outlines
9 Citations1992Fausto Giunchiglia, Toby Walsh