M Alrammal

G Hains

M Zergaoui

C M Alrammal

Realistic Performance Gain Measurements for XML Data Streaming with Meta Data

This report is part of our ongoing project on the optimization of stream processing for XPath queries on XML documents. The fact that XML documents can be large relative to query-processing memory is one of the reasons to favour streaming over in-core processing. But even in streaming mode query processing uses storage and hence time proportional to the depth of sub-documents. With the goal of querying large documents on mobile devices, or very large ones on normal machines, we have designed a scheme whereby exhaustive searching can be traded against streaming performance.

Our scheme uses query meta-data which restricts the search to a subset of the document. In an earlier report we have measured the maximal theoretical gains possible with perfect "chance" on choosing the meta-data for synthetic documents, and have found them attractive. In this report we verify two further necessary properties of our scheme, namely 1. the maximal theoretical gains are confirmed on a realistic data set 2. randomly-chosen metadata also leads to substantial performance gains, which we quantify against the percentage of actual solutions found for the query.

Introduction

XML [START_REF] W3c | Extensible Markup Language (XML) 1.0[END_REF] has become the standard for data exchange and representation between applications such as GML [START_REF] Cox | Geography markup language (gml) implementation specication[END_REF] for spatial data, ebXML [START_REF]ebXML Requirements Specication Version 1[END_REF] for e-commerce, and OWL [START_REF] Patel-Schneider | Owl web ontology language semantics and abstract syntax, w3c candidate recommendation[END_REF] for the next generation web. When more and more systems started using XML, processing XML documents became a critical and integral part of those applications. As a result, a lot of research concerning indexes [START_REF] Min | An adaptive path index for xml data using the query workload[END_REF], [START_REF] Leela | Haritsa, schema-conscious xml indexing[END_REF], [START_REF] Zuopeng | An efficient index structure for xml based on generalized sux tree[END_REF], labeling [START_REF] Yi | Xml application schema matching using similarity measure and relaxation labeling[END_REF], and structural joins [START_REF] Kim | Advanced structural joins using element distribution[END_REF] have been conducted for XML data.

Often, data is too large to fit into limited internal memory and in many cases it needs to be processed in real time during a single forward sequential scan. In addition, sometimes query results should be output as soon as they are found, in this case streaming is the best approach to process the XML Data. The term data streaming is used to describe data items that are available for reading only once and that are provided in a fixed order determined by the data source. In the streaming model queries must be known before any data arrive, so queries can be preprocessed by building automata and customized algorithms for query evaluation.

Recently, research on processing XML data stream has been conducted [START_REF] Bose | Data stream management for historical xml data[END_REF], [START_REF] Diao | Ecient and scalable filtering of xml documents[END_REF], [START_REF] Josifovski | Querying XML Streams[END_REF], [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF], [START_REF] Peng | XPath Queries on Streaming Data[END_REF]. Among various XML query languages, XPath [START_REF] Clark | XML Path Language (XPath)[END_REF] is generally used as the description language for the users since it is simple, but powerful enough to address any part of an XML document.

Data streaming is a necessary and useful technique to process very large XML documents but poses serious algorithmic problems. The challenges it poses are how to efficiently handle large amounts of XML documents or documents too large to be processed in memory. The critical complexity parameters of the streaming algorithms are: the query evaluation strategy, the XPath expression (path pattern/twig pattern with) and the structure of the XML document (depth/width/size).

The rest of this report is organized as follows : in section two we present the related work. Section 3 contains our motivations and objective. In section 4 we present our proposal searching range. Section 5 contains the experiments performed and their analyze. In section 6 we summarize our work and conclude. Finally, in section 6 we present the future work. This article presents a new approach a new approach to the optimization of XML data stream querying. Our concept is to rely on the structure of the document, the information it contains, and Oriented XPath: forward XPath augmented with meta-data for orienting the search. A prototype OXPath was implemented to account for the challenges of querying XML data streams and the critical complexity parameters of streaming algorithms. OXPath consists of two models 1) Perfomance Model which is a mathematical model of performance (Time/Space) prediction. This model provide us in advance with the expected Time/space to satisfy the XPath Expression.

2) Data Oriented Model to predicate future queries and the location of their results from past queries on a fixed XML dataset. An example of past queries importance is a 2005 study of Yahoo's query logs revealed 33% of the queries from the same user were repeat queries and that 87% of the time the user would click on the same result. This suggests that many users use repeat queries to revisit or re-find information 1.

Space and time measurements are applied to state the possible performance gains from OXPath to orient searching in XML data streams with respect to different structures of XML documents (width/depth/size). Our experiments presented here come from a realistic XPath query-processing algorithm.

Related work

A large amount of research work has been conducted to process XML documents in streaming fashion. The different approaches to evaluate XPath queries on XML data streams can be categorized as follows (1) Stream-filtering : determining whether there exists at least one match of the query Q in the XML document D (boolean), for example XTire [START_REF] Chan | Efficient filtering of xml documents with xpath expressions[END_REF]. (2) Stream-querying: which part or parts of the document D match the query Q? It implies outputting all nodes in an XML document D (answer nodes) which satisfy a query Q at its result node. for example XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF].

Various stream-filtering systems have been proposed. XFilter [START_REF] Altinel | Efficient filtering of xml documents for selective dissemination of information[END_REF], a filtering system, is the first one that addresses the processing of streaming XML data. In XFilter, each XPath query is transformed into a separate deterministic finite automaton (DFA). In YFilter [START_REF] Diao | Ecient and scalable filtering of xml documents[END_REF] , a set of XPath expressions is transformed into a single non-deterministic finite automaton (NFA) by sharing the prex. Another filtering system is XTier [START_REF] Chan | Efficient filtering of xml documents with xpath expressions[END_REF] which supports tree shaped XPath expressions containing predicates. In XTier, a path expression is decomposed into several substrings each of which is a sequence of labels, then each substring is recorded in a table, called Substring-Table .  The information in the table is used to check for partial matchings.

Recently, to improve the performance of stream-filtering, XPush machine [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF] was proposed. It process large number of XPath expressions with many predicates per query on a stream of XML data. XPush machine transforms each XPath expression into an NFA and by grouping the states in a set of NFAs, a single deterministic pushdown automaton (DPA) is constructed lazily. This is similar to the algorithm for converting an NFA to a DFA [START_REF] Hopcraft | Introduction to automata theory, language, and computation[END_REF].

However, stream-filtering systems deliver whole XML documents which satisfy the filtering condition to the interested users. Thus, the burden of selecting the interesting parts from the delivered XML documents is left upon the users.

Also, different stream-quyering systems have been proposed. In TurboXPath [START_REF] Josifovski | Querying XML Streams[END_REF] which is a lazy system for evaluating XQuery-like , the input query is translated into a set of parse trees. Whenever a matching of a parse tree is found within the data stream, the relevant data is stored in form of a tuple that is afterward evaluated to check whether predicate and join conditions are fulfilled. The output is constructed out of those tuples of which have been evaluated to true. Other systems are XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF] and SPEX [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF], they propose a method for evaluating XPath queries over streaming data to handle closures, aggregation and multiple predicates. Their method is designed based on hierarchical arrangement of push-down transducers augmented with buffers. Automata is extended by actions attached to states, extended by a buffer to evaluate XPath queries. The main idea is a non-deterministic push-down transducer (PDT) that is generated for each location step in an XPath query, these PDTs are combined into a hierarchical pushdown transducer in the form of a binary tree. In [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF] authors propose a lazy stream-querying algorithm TwigM, to avoid the exponential time and space complexity incurred by XSQ. TwigM extends the multi-stack framework of the TwigStack algorithm [START_REF] Bruno | Holistic twig joins: optimal xml pattern matching[END_REF].

Recently [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] propose a lazy system for stream-querying called LQ. In this system the input query is translated into a table throughout stream processing and statically stored on the memory. Whenever a matching of the xpath expression is found within the data stream, the evaluation process is occurred only at the closing tag of the streaming element(root element of the XPath expression). LQ was proposed to handle two challenges of stream-querying were not solved by [START_REF] Peng | XPath Queries on Streaming Data[END_REF] and [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF]. These challenges are : the recursion in the XML document and the existence of the same label-node in the XPath expression. LQ is the algorithm used in our experiments, in section 4 we justify our choice of using this algorithm.

In the next section we present our motivations then our objective to optimize the streamquerying process, which is based on our motivation.

As we mentioned before, data streaming is a necessary and useful technique to process very large XML documents but poses serious algorithmic problems. Below we discuss few of these challenges :

• Unlimited XML document Size : an XML document is often large, sometimes very large, thus using the data streaming systems in the related work still requires resources ( memory, disk storage, and network bandwidth). In our situation these resources might do not fit the capacity of the end-user pc.

• User resources (Machine): in certain situations processing the XML document occurs through portable devices with small memory sizes, thus we need to optimize the streaming process to fit our resources.

• Importance of past queries : an example of past queries importance is a 2005 study of Yahoo's query logs revealed 33 % of the queries from the same user were repeat queries and that 87 % of the time the user would click on the same result. This suggests that many users use repeat queries to revisit or re-find information [START_REF] Teevan | History repeats itself: Repeat Queries in Yahoo's query logs[END_REF].

Based on the above mentioned, further optimization for processing XML data stream is required. Our objective is to improve the stream-querying process even thought this improvement may decrease the possibility of finding all matches in the XML document.

To optimize the stream-querying process we propose searching range which augment the XPath expression with mete data to orient searching process. In this syntax, we search over a subset of the XML document as specified by the searching interval of searching range. Searching range can be provided to our algorithm implicitly by predicting future queries and the location of their results from past queries on a fixed XML dataset or explicitly based on either the knowledge of the user about the searching range or a decision taken by him to chose searching range randomly.

This process yields a semi-stream-querying algorithm which is an algorithm returns true (correct) if it finds the result(s) , in the same time, it does not guarantee to return the result(s) if it exists in the XML document (incomplete). This is why we call it correct but incomplete.

In the next section, we introduce our proposal.

4 Oriented XPath and searching range

Concept definition

As we mentioned before, stream-filtering systems deliver whole XML documents which satisfy the filtering condition to the interested users. Thus, the burden of selecting the interesting parts from the delivered XML documents is left upon the users. While stream-querying systems imply outputting all matches in an XML document D which satisfy a query Q, thus poses algorithmic challenges in a particular situation like using a portable devices with limited resources( small memory size) with very large XML documents.

In this report we define stream-scanning: to process XML data stream with minimal resources, this process searches the position of a specific element in XML document D and it does not require caching nor buffering. Where caching : is to cache specific nodes of the XML document D in the run-time stacks, these nodes correspond to the axis node of the query Q. And buffering : is to buffer the potential answer nodes of XML Document D. These nodes correspond to the answer node of Q.

Our concept is to rely on the structure of the document, the information it contains, and Oriented XPath: an XPath augmented with searching range (meta data) for orienting the search as described below. Searching range is a meta data augmented to XPath expression, it consist of two points : start-search (lt) and end-search (lt). start-search (lt) is the moment we stop stream-scanning and start stream-querying based on its lt (Location tag) value. It provides the algorithm in the location of the tag in the XML document, more precisely, the location of the tag of the first node X in the XML document order that corresponds to the root node of XPath sent. While, end-search(lt) is the moment we decide to stop processing the XML document based on its lt (Location tag) value. It provides the algorithm in the location of the tag(lt) of the last node Y in the XML document order that corresponds the answer node of XPath sent.

To explain the idea of the location tag, we present the example below : The idea is to first learn from past queries to "guess" in advance those parts of the document that contain the information to be found. This information may also be explicitly provided by the user of a querying interface, for example one may want to search a very large documents knowing that the information sought is located in the second half of the document. Whatever the source of metadata (and this will be the subject of future research) we plan to use it to direct search closer/faster stream-scanning to those parts of the document where stream-querying is to be applied using Lazy query evaluation.

The purpose of learning from past queries could be to provide us in the metadata with the exact element e in document D that matches the query root. The oriented XPath expression including the new meta data: could be for example a query together with a Dewey path for orientation of search.

Prototype

To enable the empirical study, we build the stream-query system LQ [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF], our choice for this system returns to the following raisons: (1) the authors in [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] explain the algorithm in details thus facilitate the implementation process. (2) As we mentioned before, the query evaluation technique of LQ is lazy, thus it is easier to implement than Eegar one. (3) Finally and the most important, LQ was proposed to handle two challenges of stream-querying were not solved by [START_REF] Peng | XPath Queries on Streaming Data[END_REF] and [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF]. These challenges are : the recursion in the XML document and the existence of the same label-node in the XPath expression. Based on that the algorithm complexity (Time/Memory) of LQ is the best between the stream-qyerying systems mentioned in our related work.Our prototype was implemented using the functional language Ocaml [START_REF]Objective Caml Language[END_REF].

To augment the XPath expression with searching range, LQ was modified and called OXPath. The architecture of OXPath is shown in figure 2.

OXPath takes three input parameters. The first one is the XPath expression that will be transformed to a query table statically using our Forward XPath Parser. The second is the searching range which contain the start-search and end-search points . After that, the main function will be called, it reads the tree data set line by line repeatedly, each time it generates a token. The value of lt (location tag) of the generated token is matched with the lt value of the start-search point of searching range. If the matching condition is true, stream-scanning will stop then we start stream-querying process. Based on the token generated during the stream-querying process, the matching condition of end-search point is checked, if it is false, then a corresponding startBlock (SB) or endBlock (EB) function is called to process this token, Figure 2: Architecture of OXPath otherwise the processing the XML document will stop. Finally,during the stream-querying process, if tree data set satisfies the XPath expression, then the main function generates an output stream lazily. Notice that, we stop stream-querying process the moment our condition is true.

The automation process for learning from past queries is not implemented yet, but in order to perform our experiments, the algorithm was modified in a way that it calculates the searching range of the XPath sent for the first time, thus the moment we send the same XPath another time, it augments this XPath with searching range. This means that searching range is implicitly calculated by the algorithm. Furthermore, it possible to provide the algorithm in the searching range explicitly. As we explained before, explicit searching range is either based on the user knowledge about the location of the answer or a decision taken by him to chose searching range randmoly.

Experiments

In this section, we demonstrate the efficiency and scalability of Searching range.

Experiments environment

Experiments were performed using a MacBook with the following technical specifications: Intel Core 2 Duo, 2.4 GHz clock speed , 4 GB RAM.

Data sets

We performed the experiments using the data set treeBank [START_REF] Suciu | Treebank:XML data repository[END_REF] . It is a real data set which has a narrow and deep structure and it has a size of 2500 tokens.

XPath Queries

The XPath queries used for the experiments were generated using Exhaustive testing. Exhaustive testing is a comprehensive testing process to test all XPath queries possible in the data set Treebank. They have the following forms : //A, //A/B, //A/[./B] where A and B can be any element in the data set TreeBank. The purpose of this process is to have a complete statistics related to query evaluation cost.

In this test we measure for each query the best case of the possible time/memory gain i.e. the difference between the cost of a normal streaming query over the whole document vs one where the algorithm simply scans tokens until reaching the answers in an interval indicated by the meta-data. This is of course only possible if the meta-data has been computed from a previous occurrence of the same query over the same document. But our intention is to use this measurement as a target for performance improvement with more realistic e.g. random meta-data. This last observation will be briefly expanded in our second set of tests below: T4, T5, T6.

Query evaluation cost (Time/Memory) of one XPath is : -Min. Time: Returns the processor time in seconds, used by the program since the beginning of execution till finding the first answer if any, or reaching the end of the document of not -Avg. Time : (Σ (time for each match))/ total number of matches.-Max. Time :returns the processor time in seconds, used by the program since the beginning of execution till the end of XML document processing. -Min. Memory: the total amount of memory allocated by the program size in KB since the beginning of execution till finding the first answer if any, or reaching the end of the document of not. -Avg. Memory: (Σ (memory size in KB for each match))/ total number of matches.-Max. Memory: the total amount of memory allocated by the program size in KB since the beginning of execution till the end of XML document processing.

We classify the tests of our experiments as follows : (1) Test with implicit searching range, these tests are : T1 : XPath with the shape //A , this XPath is sent without searching range. T1 : XPath with the shape //A, This XPath is sent with ideal searching range obtained from T1 to demonstrate the best time/memory gain possible. T2 : XPath with the shape //A/B , this XPath is sent without searching range. T2 : XPath with the shape//A/B, this XPath is sent with ideal searching range obtained from T2 to demonstrate the best time/memory gain possible. T3 : XPath with the shape //A[./B], this XPath is sent without searching range. T3 : XPath with the shape //A[./B], this XPath is sent with ideal searching range obtained from T3 to demonstrate the best time/memory gain possible.

(2) Test with explicit searching range ( random choice). In each test, the same XPath was sent 25 times, each time XPath was augmented in searching range as follows : -size: is the size of our data set which contains 2500 tokens. len is the length of the searching range(interval), it equals size/10. Also, end-seach = start-search/len, and the difference between start-search points each time is 100 tokens. for example : searching range( start-search, end-search ) searching range (1, (1+len) . searching range(100, (100+len). The purpose of this type of tests is to demonstrate the possible time/memory gain. Our demonstration will be represented as a histogram for time gain and another one for the memory gain for each test. The tests of this type are : T4 : XPath with the shape //A , this XPath is sent without searching range, then with a varying searching range. T5 : XPath with the shape //A/B , this XPath is sent without searching range, then with a varying searching range. T6 : XPath with the shape //A[./B] , this XPath is sent without searching range, then with a varying searching range.

Experiments results

Exhaustive testing on TreeBank

T1 and T1

In this experiment, we show the efficiency of using searching range compared to the existing stream-querying algorithm LQ. figure 3 shows the queries evaluation cost of T1 and T1 . In this experiment, we calculated the query evaluation cost for 45 positive queries.

Figure 3: Query evaluation cost for T1 and T1 Figure 3 (A) shows the queries evaluation cost (time) of T1 and T1 . The Min Time of T1 is 0.001027 s while for T1 is 0.000985 s, the slight gain of time returns to the start-search point of the searching range. The Avg Time of T1 is 0.005176 s while for T1 is 0.005146 s , the slight gain of time returns to start-search and end-search points of the searching range. The Max Time for T1 is 0.010512 s while for T1 is 0.009745 s, the slight gain of time returns to end-search point of searching range. As we see from the results of the experiment in the figure 3 (A) , our idea does not affect the query evaluation cost negatively, on the contrary in specific situations where the interval of the searching range is small, we can have dramatic gain of time. Figure 3 (B) shows the queries evaluation cost (Memory) of T1 and T1 . The Min Memory of T1 is 323.47 K.B. while for T1 is 317.55 K.B., the slight gain of memory returns to the start-search point of the searching range. The Avg Memory of T1 is 876.73 K.B. while for T1 is 870.81 K.B. , the slight gain of memory returns to start-search and end-search points of the searching range. The Max Memory for T1 is 1736.96 K.B. while for T1 is 1435.12 K.B. , the obvious gain of time returns to end-search point of searching range.

T2 and T2

In this experiment, we show the efficiency of using searching range compared to the existing stream-querying algorithm LQ. We calculated the query evaluation cost for 75 positive queries, 1861 negative queries and for 1936 queries as a total number. figure ?? (A) shows the queries evaluation cost(Time) of T2 and T2 . The Min Time of total, negative and positive queries in figure 4 (A) are 0.004850 s, 0.005004s, and 0.001768 s respectively, while in figure 4 (B) they are 0.0000115 s, 0.000061s and 0.001438 s, the gain of the time returns to start-search point of the searching range and because the number of negative queries is large thus decreases the time. The Avg Time of total, negative and positive queries in figure 4 (A) are 005228 s, 0.005004s, and 0.009708 s respectively, while in figure 4 (B) they are 0.000602 s, 0.000061s and 0.0014010 s, the gain of the time for the total and negative queries returns to start-search and search points of the searching range and because the number of negative queries is large thus decreases the time. Concerning the Avg Time of positive queries , it increases from 0.009708 s to 0.014010 s because as we explained before the evaluation technique used is lazy, thus in specific cases we can not return the last match of the positive query which respects the searching range interval. As a result the average time increases. The Max Time of total, negative and positive queries in figure 4 (A) are 0.006047 s, 0.005004s, and 0.026947 s respectively, while in figure 4 (B) they are 0.001191 s, 0.000061s and 0.028217 s, the gain of the time for the total and negative queries returns to start-search and search points of the searching range and because the number of negative queries is large thus decreases the time. Concerning the Max Time of positive queries , it increases from 0.026947 s to 0.028217 s because of the same raison as it is explained above for the Avg Time of positive queries.

Figure 5 shows the queries evaluation cost (Memory) of T2 and T2 . The Min Memory of total, negative and positive queries in figure 5

T3 and T3

In this experiment, we show the efficiency of using searching range compared to the existing stream-querying algorithm LQ. We calculated the query evaluation cost for 75 positive queries, 1861 negative queries and for 1936 queries as a total number. Figure 6 (A) shows the queries evaluation cost (Time) of T3 and T3 . The Min Time of total, negative and positive queries in figure 6(A) are 0.004842 s, 0.004997s, and 0.001736 s respectively, while in figure 6 (B) they are 0.0000117 s, 0.000060s and 0.001530 s, the gain of the time returns to start-search point of the searching range and because the number of negative queries is large thus decreases the time. The Avg Time of total, negative and positive queries in figure 6 (A) are 005223 s, 0.004997s, and 0.009750 s respectively, while in figure 6 (B) they are 0.000574 s, 0.000061s and 0.000060 s, the gain of the time for the total and negative queries returns to start-search and search points of the searching range and because the number of negative queries is large thus decreases the time. Concerning the Avg Time of positive queries , it increases from 0.009750 s to 0.013338 s because as we explained before the evaluation technique used is lazy, thus in specific cases we can not return the last match of the positive query which respects the searching range interval. As a result the average time increases. The Max Time of total, negative and positive queries in figure 6 (A) are 0.006043 s, 0.0049974 s, and 0.027001 s respectively, while in figure 6 (B) they are ,001126 s, 0.000060s and 0.027589 s, the gain of the time for the total and negative queries returns to start-search and search points of the searching range and because the number of negative queries is large thus decreases the time. Concerning the Max Time of positive queries , it increases slightly from 0.027001 s to 0.027589 s because of the same raison as it is explained above for the Avg Time of positive queries.

Figure 7 (B) shows the queries evaluation cost (Memory) of T3 and T3 .

T4

T4 is a query of the form //A for which we measure the performance gain for meta-data indicating a search interval of 1/10th the size of the document i.e. 250 over 2500 tokens. The test measures time-and space gains over the possible location of this interval in the document. Because the query's answers are distributed across the document, each query has obtained a proprotional fraction of matches. The intersting parameter to observe here is thus the performance gain. The results show up to 100% speedup with an average speedup around 75% and never less than a 50% speedup. Space gains are somewhere at 50% on average and are uniformly distributed between 0% and 90%. There is approximately a 1 on 2 chance of obtaining a 50% to 90% space gain.

T5

T5 is query of the form //A/B for which we apply the same test as T4. The observations for T5 are very similar to those for T4 except that the distribution of performance gains is a little more uniform.

T6

T6 is query of the form //A[.B] for which we apply the same test as T4 and T5. The results for T6 are almost to those for T5. Overall the results for tests T4, T5 and T6 support our view that even a random choice of interval for the algorithm's searching range will yield substantial time and space gains. It will remain to:

1. confirm these results by varying the test queries and the document;

2. observe and model the ratio between the subset of matches found and the performance gains.

This last value may prove elusive in general, but any empirical or statistical progress on its prediction will allow users of our algorithm to balance the cost of a query with its potential to return most interesting matches to a query.

Conclusion

In this report we presented the idea of Oriented XPath that is augmented with meta-data to specify a searching range. A core prototype called OXPath was implemented to have a concrete understanding for the complexity of stream-querying process and to demonstrate the possible time/memory gain of our proposal. Experiments were performed using searching range implicitly and explicitly. We observed from the experiments with the implicit searching range the following : (1) in all tests Min Time was improved, this improvement returns to streamscanning.

(2) Memory gain depends on interval of searching range, if this interval is small a dramatic memory gain can be achieved, (3) negative queries in streaming is a critical point and very expensive, it affects the performance of stream-querying algorithms dramatically as we stated in our results.(4) Our current prototype uses our own implementation of Gou and Chirkova's query evaluation algorithm in its lazy version. This is relatively clean to implement but it delays outputting the result to the end user and in some cases it decrease the number of matches in the XML document which satisfy the XPath query. An implementation of the eager streaming algorithm is more complex but should yield more predictable performance and improve the space consumption in absolute terms while remaining the same processing speed. Finally, our experiments with random explicit meta-data (T4, T5, T6) have confirmed our implicit assumption that it will be possible to find scanning ranges that produce a reasonable balance of matches with performance gains.

Our future work will first design a quantitative performance model to relate the key parameters in our scheme: match-percentage, space and time gain. Once this model is designed and tested it we will develop a machine-learning algorithm whereby the performance model and hence the best choices of meta-data will be computed from past experience for streaming queries on a given XML document.

Figure 1 :

 1 Figure 1: An XML document and it SAX parser events

Figure 4 :

 4 Figure 4: Query evaluation cost for T2 and T2 -(Time)

  (A) are 1675.67 K.B , 1731.32 K.B, and 566.81 K.B respectively, while in figure 5 (B) they are 24.79 K.B, 9.14 K.B and 413.22 K.B, the gain of the memory returns to start-search point of the searching range and because the number of

Figure 5 :

 5 Figure 5: Query evaluation cost for T2 and T2 -(Memory)

Figure 6 :

 6 Figure 6: Query evaluation cost for T3 and T3 -(Time)

Figure 7 :

 7 Figure 7: Query evaluation cost for T3 and T3 -(Memory)

Figure 8 :

 8 Figure 8: T4 time/memory gain distribution against choice of streaming interval i.e. random meta-data

Figure 9 :

 9 Figure 9: T5 time/memory gain distribution against choice of streaming interval i.e. random meta-data

Figure 10 :

 10 Figure 10: T6 time/memory gain distribution against choice of streaming interval i.e. random meta-data


M Alrammal

G Hains

M Zergaoui

C M Alrammal

Performance measurements towards the optimization of stream processing for XML Data

 as an attempt to optimize stream processing for XML data. A core prototype called O-Search was implemented to have a concrete understanding for the complexity of stream-querying algorithms i, with respect to different structures of XML documents (wide, depth, various size). Space and time measurements are applied to state the possible performance gains from the use of meta data to orient searching in stream XML data.

Introduction

The extensible markup language (XML) [START_REF] W3c | Extensible Markup Language (XML) 1.0[END_REF], has gone from the latest buzzword to an entrenched e-Business technology in record time. XML is currently being heavily pushed by industry and developers as the lingua franca for data representation and exchange on the Internet. It provides a much needed non-proprietary universal format for sharing hierarchical data among different software systems, and does so in a user-friendly manner. It is a verbose plain-text format, making it robust, platform-independent and legible to humans without additional tools. This popularity of XML has created several important applications like information dissemination, processing of scientific data, and real time news. Query languages like XPath [START_REF] Clark | XML Path Language (XPath)[END_REF] and XQuery [START_REF] Boag | XQuery 1.0: An XML Query Language[END_REF] have been proposed for accessing the XML data, which provide a syntax for specifying which elements and attributes are sought to retrieve specific pieces of a document. Often, data is very large to fit into limited internal memory and in many cases it needs to be processed in real time during a single forward sequential scan. In addition, sometimes query results should be output as soon as they are found, in this case streaming fashion is the best approach to process the XML Data. The term data streaming is used to describe data items that are available for reading only once and that are provided in a fixed order determined by the data source. In the streaming model queries must be known before any data arrive, so queries can be preprocessed by building machines for query evaluation.

Concerning query evaluation process, usually two operations can be requested. First, does our document D match the query Q? In this case we determine whether there exists at least one match of Q in D this is called stream-filtering. Second, which part or parts of the document D match the query Q? It implies outputting all nodes in an XML data tree D (answer nodes) which satisfy a specified twig pattern Q at its result node stream-querying. Different strategies and streaming algorithms were implemented for this purpose, we can categorize some of them based on the time of predicate evaluations in queries. A Lazy streaming algorithm evaluates the predicates1 only when the closing tags of the streaming elements are encountered. While an Eager algorithm does that as soon an atom in a predicate is evaluated to true [START_REF] Gou | Efficient Algorithms for Evaluating XPath over Streams[END_REF].

In our first technical report [START_REF] Alrammal | Intelligent Ordered XPath for Processing Data Streams[END_REF] we surveyed different approaches used to evaluate XPath expressions over XML data streams. Furthermore, we estimated the streamable XPath fragments for the various streaming algorithms. In addition, we introduced variant examples to explain the critical complexity parameters of the streaming algorithms, like query evaluation strategy, the XPath expression (recursion) and the structure of the target XML document. Based on those observations, the notion of Oriented XPath for processing efficiently large XML data streams was proposed as an attempt to optimize for these critical performance parameters. In this technical report we present the first experimental results to support our proposal in [START_REF] Alrammal | Intelligent Ordered XPath for Processing Data Streams[END_REF].

The rest of the report is organized as follows: in section 2 we introduce the core of our prototypeO-Search. Section 3 is a detailed presentation of our experiments with all necessary details to allow their reproduction on a different architecture of with similar source code. Finally, in section 4 we analyze the results and evaluate the consequences for our proposed Oriented XPath scheme.

We developed the core of a prototype called O-Search to have better understanding for the complexity of stream-querying algorithms in practice, with respect to different structures of XML documents (wide, depth, various size). The evaluation technique used in our prototype is Lazy. Figure 1 shows the current structure of O-Search. O-Search will become our intermediate prototype for stream-querying of XML Data. It is implemented using the functional language Ocaml2 [START_REF]Objective Caml Language[END_REF]. We have currently implemented the basic search functions necessary for realizing XPath queries. To explain figure 1 we start in the input that is a simplified XML file which has the abstract syntax as in figure 2. • Element nodes: these correspond to tags in XML documents, and correspond to StartElement token in our concrete syntax, for example StartElement("A",[]). An attribute list is associated (optionally) with tags in the XML document , therefore it is associated with StartElement tokens in our concrete syntax, for example StartElement("B",[("attr","2")]).

Note that, the attribute list is not nested(an attribute can not have any sub-elements), not repeatable (tow same-name attributes can not occur under one element) and unordered (attributes of an element can freely interchange their occurrences location under element). These constraints are standard to XML.

• Text nodes: these correspond to data values in XML document, and correspond to Text token in our concrete syntax, for example Text("Any text"). The token generated by the lexer will be used by the processing function for matching and processing purposes. After each match the lexer is called repeatedly to generate another token. An example of this function is: val getSubStreamsForElement: string ->in channel -> string -> unit = <fun> were the input arguments are:

• string: our query.

• in channel: the input file.

• string: the name of the output file.

val getSubStreamsForElement calls recursively many other internals functions to generate the result as stream of tokens then call recursively the function: val stringOfToken: token -> string = <fun> to convert each token in the stream to string and sent it to the output channel.

Experimental Results

Experimental Setup

In this section we explain the experimental setup needed of the performance measurements using our prototype.

Data sets

To conduct the performance measurements, we implemented two types of synthetic data sets. These data sets are described below:

1. Wide tree data set: shallow structure, that does not include recursive elements. To generate the Wide tree data set, we use the following function val generateWideTree : string -> int -> in channel = <fun> where:

• string: is the output file name which will contain the wide tree data set.

• int: is the number of the shallow sub-trees in the wide tree data set. Queries will refer to each sub-tree's "token rank", see figure 4.

To know the total number of the tokens generated in our wide tree data set that was used for the performance tests, we use the following equation:

Tree/Data set size(tokens)= (n * 10) + 4

where:

• n: is the loop number. It is proportional to the tree data set width

• 10: is the number of tokens generated in each sub-tree.

• 4: is a constant number that represents: • string: is the output file name which will contain the deep tree data set.

1-StartDocument ("Doc 1") 2-StartElement("root", []) 3-EndElement("root") 4-EndDocument("Doc1")
• int: is the loop depth of the deep tree data set. Queries will refer to "token rank" in this tree data set, see figure 5.

To know the total number of tokens generated in our deep tree data set that was used for the performance tests, we use the following equation:

Tree/Data set size(tokens)= ((n * 6) + (n * 4)) + 4

where:

• n: is the loop number. It is proportional to the depth tree data set.

• 6: is the number of tokens(StartElement and Text) that are generated in each recursion.

• 4: is the number of tokens(EndElement ) that are generated in each recursion.

• 4: is a constant number that represents: • Memory: We measure the maximum depth of the running time stack (caching) using the following function:

1-StartDocument ("Doc 1") 2-StartElement("root", []) 3-EndElement("root") 4-EndDocument("Doc1")
val getMaxDepth: unit -> int = <fun> getMaxDepth();; this function returns an integer which indicates the maximum instantaneous number of tokens in the stack.

Queries

We used the following processing function: getSubStreamsForElement . Our tests have the following form:

getSubStreamsForElement<Token name> (generateWideTree "inputFile,txt"<data set token rank>) "outputFile,txt";;

where Token name can have the following values:

• A1: return the sub-tree of the element which exists at the beginning of the tree data set.

• A<token rank/2>: return the sub-tree of the element which exists in the middle of the tree data set.

• A<Data set token rank>: return the sub-tree of the element which exists at the end of the tree data set.

Furthermore, we use Positive and Negative queries, where:

• Positive: is a query that does not return an empty result.

• Negative: is a query that does return an empty result. We use negative queries with the two types of the tree data sets (Wide and Deep) as a reference for performance measurement. Note that, O-Search support other processing functions, for example: getSubStreamsForAttributeName<Token name>(generateWideTree "inputFile,txt" <Data set token rank>) "outputFile,txt" ;; getSubStreamsForAttributeValue<Token name>(generateWideTree "inputFile,txt"<Data set token rank>) "outputFile,txt";; getSubStreamsForTextEqual<Token name >(generateWideTree "inputFile,txt"<Data set token rank>) "outputFile,txt" ;;

3 Sys: portable system calls. To test the execution time, we compile the CAML file using ocamlopt: the Objective Caml highperformance native-code compiler. Generated code is almost 10 times faster than generated code by ocamlc.

To test the memory consumption, we use ocamlc which compiles CAML source files to byte-code object files and links these object files to produce standalone bytecode executable files. These executable files are then run by the bytecode interpreter ocamlrun. For memory tests, it is recommended to use ocamlc because it is more accurate than ocamlopt [START_REF]Module Gc[END_REF].

Results

This section details our measurements for (time/space) for the following data sets (Wide tree/Deep tree) for positive queries. Those tests are then repeated for negative queries.

Wide tree data set (Positive queries)

We performed two tests using this data set, they are:

1. Time test To explain this test, we start in explaining table 2 that includes all the information needed:

• Query: getSubStreamsForElement <Token name> (generateWideTree "inputFile,txt" <Data set token rank> "outputFile,txt");;

• Test type: table 2 contains three tests, they are y1, y2, and y3. In fact, we change the value of Token query rank with each test.

• Token name: the token name we search.

• Data set token rank: the rank of token of sub-tree, for better understanding see figure 4. • Input tree size(tokens): the total number of tokens generated in our wide tree data set. • T(total): the processor time in seconds since the beginning of the execution to generate the tree data set and answer the query. • T(data set): the processor time in seconds since the beginning of the execution to generate the tree data set. • T(total-data set): the processor time in seconds since the beginning of the execution to answer the query. • Stack max. depth (token)): is the maximum depth of the running time stack.

Figure 6 represents three tests to measure the execution time in the wide tree data set. Test y1 uses a 1M token document, y2 a 5M token document and y3 a 10M token document. We noticed that test y1 is steady linear at 1,81 seconds irrespective of the data set token rank. Also, test y2 is almost steady linear at 9,3 seconds. While test y3 is almost steady linear at 18,7 seconds with a slight increasing particularly at the point (A1000000 -1000000). Therefore, we conclude that execution time is independent of the data set token rank in the wide tree data set. We observe directly proportional to the input tree size: curves y2, y3 are multiples of y1 in this proportion.

Memory test

To explain this test, we start in explaining table 2 that includes all the information needed:

• Query: getSubStreamsForElement <Token name> (generateWideTree "inputFile,txt" <Data set token rank> "outputFile,txt");; Figure 7 represents three tests to measure the memory allocated to answer our query in the wide tree data set. Tests y1,y2 and y3 have the same value for the maximum number of tokens in the running stack which is 3 due to the symmetry of all sub-trees in the wide tree data set. Therefore, we conclude that the stack max. depth(tokens) is independent of the data set token rank in the wide tree data set. We performed two tests using this data set, they are:

1. Time The terms used in table 3 are the same as table 2. The time-rank relationship should normally be negative-linear and its quadratic behavior in our tests is due to a naive list implementation of one primitive. This will be changed in a future version and does not affect our conclusion in section 4.

Memory

The terms used in table 3 are the same as table 2.

Figure 9 represents three tests to measure the memory allocated to answer our query in the deep tree data set. We noticed that increasing the data set token rank and decreasing the value of query name will increase the value of stack max. depth(tokens). Furthermore, our evaluation technique is lazy 4 , therefore we are obliged to buffer the whole subtree. In test y1 the relationship between the memory usage (y) and data set token rank (x) is as the following y = -4 * x+4003. In test y2 the relation is: y = -4 * x+20003. While for the test y3 it is: y = -4 * x + 40003.. Therefore, we conclude that stack max. depth(tokens) is inverse-linearly related to the data set token rank in the wide tree data set, and linear proportional to the document size.

Wide tree data set (Negative queries)

We performed two tests using this data set, they are:

1. Time Terms in table 4 have the same meaning as table 2.

Figure 10 represents a test to measure the execution time in the wide tree data set using negative queries. We noticed that execution time increases with the increasing of the data set token rank due to the increasing of matching processes. More precisely, in test y1 the relationship between the execution time(y) and data set token rank (x) is as the following y = 0, 00001977 * x -1.8196. The importance of this test is to compare the measurements between wide tree data set and deep tree data set using negative queries.

ments are encountered.

Figure 10: Wide tree data set -Time (negative queries).

Memory

Terms in table 4 have the same meaning as table 2 Figure 11 represents a test to measure the maximum depth of the running stack (in tokens) to answer our negative query in the wide tree data set. We notice that the increasing the data set token rank does not affect the stack max. depth because our query is negative so we do not need to cache any element. We conclude that stack max. depth (tokens) is independent of the data set token rank in the wide tree data set.

Deep tree data set (Negative queries)

We performed two tests using this data set, they are:

1. Time Terms in table 5 have the same meaning as table 2.

Figure 12 represents a test to measure the execution time in the deep tree data set using negative queries. We noticed that execution time increases with the increasing of the data set token rank due to the increasing of matching processes. More precisely, in test y1 the relationship between the execution time(y) and data set token rank (x) y = 0.000019 * x -1.55737704918. Comparing the two linear equations to measure the execution time between both deep/Wide tree data sets using negative query indicates that deep tree data set has a better time performance than wide tree data set.

Figure 12: Deep tree data set -Time (negative queries).

Memory

Terms in table 5 have the same meaning as table 2.

Figure 13 represents a test to measure the maximum depth of the running stack (in tokens) to answer our negative query in the deep tree data set. We notice that the increasing the data set token rank does not affect the stack max. depth because our query is negative so we do not need to cache any element. We conclude that stack max. depth (tokens) is independent of the data set token rank in the deep tree data set. This report supports our proposal for a new approach to the optimization of XML data stream querying. Our concept is to rely on the structure of the document, the information it contains, and Oriented XPath: forward XPath augmented with meta-data for orienting the search as described below. The idea if to first learn from past queries to "guess" in advance those parts of the document that contain the information to be found. This information may also be explicitly provided by the user of a querying interface, for example one may want to search a large documents knowing that the information sought is located in the second half of the document. Whatever the source of metadata (and this will be the subject of future research) we plan to use it to direct search closer/faster stream-scanning to those parts of the document where stream-querying is to be applied using Lazy query evaluation.

The purpose of learning from past queries could be to provide us in the metadata with the exact element e in document D that matches the query root. The oriented XPath expression including the new meta data: could be for example a query together with a Dewey path for orientation of search. In this case, the syntax of metadata could be as follows:

<A 4 order="2.2.1.1" subTreeSize="4"... /A> In this example, the attribute order provides us with the path from the root to nodeA 4 (Dewey Path), while the attribute subTreeSize gives the size of the subtree of the node A 4 (see figure 14). To support Oriented XPath queries, the order information of nodes must be captured by the schema to process these queries efficiently. Figure 14 illustrates the information order of document D (ordered axes).

From A 1 to A 2 pure stream-scanning is applied to reach the specified point in document D that matches the query root. This process can save caching space as we will see in the example of section 4.2 The moment we reach the element A 4 we stop stream-scanning and start stream-querying for the whole sub-tree i.e. a complete querying algorithm is applied.

Performance gains

In this section we present two examples that explain the possible performance gains using Oriented XPath. Example 1: figure 14 represents an XPath expression //A//B[.//C]/K and an XML document with information order (Dewey Path). Note that we use node numbering for example A 2 to explain the performance gain, in other words, the node that we do not need to cache or buffer. In our XPath expression the single line edges represents child ('/'), the double line edges represents descendant('//'), single dashed line represents [./node()], double dashed line represents [.//node()] and the result node which is in this example the shaded node K. If XPath is provided with information as follows(start at the axis order 2 of node A) then, the syntax of XPath expression including the new meta data will be:

//A[@order = "2"]//B[.//C]/K.
in this case, based on figure 14 we do not need to cache the following nodes: B 4 , B 5 , also we do not need to buffer the node C 1 though they would otherwise match the sub-pattern of the query. Example 2: this example shows the possible gains of time and memory using Oriented XPath on our synthetic data sets (wide/deep). We assume that metadata can either indicate one precise subtree or a subset of subtrees where to search.

1. Wide tree data set: figure 15 is a wide tree data set.

Optimization for both time and memory has three scenarios:

• Worst case: we do not have any meta data to orient our search. Therefore there will be no memory or time saving, see figure 15.

• Average case: meta data orients our query to start searching somewhere after the middle of the tree data set, see figure 15. Stack consumption being already minimal, there is no expected saving from the use of meta data here. The saving in processing time will be proportional here to half of the document size and to the difference between the time to scan one token vs the time to process one token in query mode. This difference is not yet measurable in our tests, which is explained because it should increase with the complexity of query patterns. Our current tests only deal with elementary queries so scan time is currently almost equal to query processing time.

• Best case: meta data orients our query to a precise sub-tree that answers the query 15. Stack consumption being already minimal, there is no expected saving from the use of meta data here. The saving in processing time will be proportional here to the document size multiplied by (time to scan one token -time to process one token in query mode).

2. Deep tree data set: figure 16 is a deep tree data set. Optimization for both time and memory has three scenarios: • Worst case: we do not have any meta data to orient our search. Therefore there will be no memory or time saving, see figure 16.

• Average case: meta data orients our query to start searching somewhere after the middle-depth of the tree data set, see figure 16. The saving in stack consumption is here of 50% and an example of saving in time can be found by comparing tests in Table 3. For example time could be reduced from 223s to 41s when processing a document of 50004 tokens.

• Best case: meta data orients our query to a precise sub-tree that answers the query 16. Stack consumption is then almost reduced to 0, almost a 100% saving. The possible time saving is here also visible in Table 3. For example time could be dramatically reduced from 223s to 0,08s when processing a document of 50004 tokens.

Conclusion

In this report we presented the first experimental results to support our proposal to optimize stream processing for XML data with the use of meta data to orient search. A core prototype called O-Search was implemented to have a concrete understanding for the complexity of stream-querying algorithms , with respect to different structures of XML documents (wide, depth, size). measurements have confirmed and quantified the space time complexity of query processing primitives. Meta data can improve performance parameters in average, can not avoid the worst case performance but may in favorable cases yield dramatic improvements.

Our concept remains to be evaluated on complex queries and a realistic framework for providing meta data must be constructed. Even in the absence of any automated collection of meta data, there are scenarios for which manually-provided meta data is both realistic and necessary. For example, in situations involving portable devices with small memory sizes, explicit meta data provided by the user will allow searches to be performed even though a false negative result is possible. In this case the user would repeat his search. Our experiments and estimations have shown the gains possible in this manner, and future research could generalize its applicability to many other situations.

Figure 1 :

 1 Figure 1: Architecture of O-Search.

  type token = StartDocument of string | StartElement of string * (string * string) list | EndElement of string | Text of string | EndDocument of string ;;

Figure 2 :

 2 Figure 2: Abstract Syntax

Figure 3 :

 3 Figure 3: XML Tree Model.

Figure 4 4 Figure 4 :

 444 Figure 4 is an example of wide tree data with the following size: Tree/Data set size(tokens)= (100000 * 10) + 4

Figure 5

 5 Figure 5 is an example of deep tree data set with the following size: Tree/Data set size(tokens)= ((100000 * 6) + (100000 * 4)) + 4

Figure 5 :

 5 Figure 5: Deep tree data set

Figure 6 :

 6 Figure 6: Wide tree data set -Time

Figure 7 :

 7 Figure 7: Wide tree data set -Memory.

Figure 8 :

 8 Figure 8: Deep tree data set -Time.

Figure 8

 8 Figure 8 represents three tests to measure the execution time in the deep tree data set.We noticed that execution time increases with the increasing of the data set token rank and the decreasing of token name's value (see section 3.1.4) due to increasing the tokens those correspond the query which increase the execution time. More precisely, in test y1 the relationship between the execution time(y) and data set token rank (x) is y = (2.2712 -0.0022 * x)2 . In test y2 the relation is: y = (14.5450 -0.0029 * x) 2 . While for the test y3 it is: y = (33.8034 -0.0034 * x)2 . Therefore, we conclude that execution time is negative-quadratic proportional to the data set token rank in the deep tree data set. The time-rank relationship should normally be negative-linear and its quadratic behavior in our tests is due to a naive list implementation of one primitive. This will be changed in a future version and does not affect our conclusion in section 4.

Figure 9 :

 9 Figure 9: Deep tree data set -Memory.

Figure 11 :

 11 Figure 11: Wide tree data set -Memory (negative queries).

Figure 13 :

 13 Figure 13: Deep tree data set -Memory (negative queries).

Figure 14 :

 14 Figure 14: Document Information Order.

Figure 15 :

 15 Figure 15: Meta data in the wide tree data set.

Figure 16 :

 16 Figure 16: Meta data in the deep tree data set.

Table 1 :

 1 Specifications of the test machine 3.1.3 Test measurements • Time: to measure execution time, we use the following function Sys.time();;. This function exists in the module Sys 3 of Ocaml. It has a type:unit -> float, and it returns the processor time (in seconds) used by the program since the beginning of execution. To return the time of generating (for example) a wide tree data set, we use the following code:

	let temp=ref (Sys.time()) ;;
	generateWideTree "inputFile.txt" n ;;
	print_float (Sys.time()-. !temp);;
	print_string " Second\n"; temp:=Sys.time();;

To return the total time of a specific test (for example: getSubStreamsForElement), we use the following code: let temp=ref (Sys.time());; getSubStreamsForElement <token name>(generateDeepTree "inputFile.txt" <Data set token rank>) "outputFile.txt" ;; print_float (Sys.time()-. !temp); print_string " Second\n"; temp:=Sys.time();;

Table 2 :

 2 Wide tree data set -time and memory tests

	Test type Token name	Data set	Input tree	T(total)	T(data set)	T(total-data set)	Stack max. depth
			token rank size(tokens)	In second	In second	In second	In (tokens)
	y1	A1	100000	1000004	2,42	0,61	1,81	3
	y1	A50000	100000	1000004	2,41	0,61	1,8	3
	y1	A100000	100000	1000004	2,42	0,61	1,81	3
	y2	A1	500000	5000004	12,42	3,12	9,3	3
	y2	A250000	500000	5000004	12,41	3,12	9,29	3
	y2	A500000	500000	5000004	12,49	3,12	9,36	3
	y3	A1	1000000	10000004	24,89	6,24	18,65	3
	y3	A500000	1000000	10000004	24,92	6,24	18,67	3
	y3	A1000000	1000000	10000004	26,17	6,24	19,92	3
	3.1.5 Compiler

Table 3 :

 3 Deep tree data set -time and memory tests 3.2.2 Deep tree data set (Positive queries)

	Test type Token name	Data set	Input tree	T(total)	T(data set)	T(total-data set)	Stack max. depth
			token rank size(tokens)	In second	In second	In second	In (tokens)
	y1	A1	1000	10004	5,73	0,01	5,72	3999
	y1	A500	1000	10004	0,82	0,01	0,81	2003
	y1	A1000	1000	10004	0,03	0,01	0,02	3
	y2	A1	5000	50004	223,37	0,04	223,33	19999
	y2	A2500	5000	50004	41,47 1	0,04	41,43	10003
	y2	A5000	5000	50004	0,12	0,04	0,08	3
	y3	A1	10000	100004	1193,32	0,07	1193,26	39999
	y3	A5000	10000	100004	232,42	0,07	232,35	20003
	y3	A10000	10000	100004	0,23	0,07	0,16	3

Table 4 :

 4

	Test type Token name	Data set	Input tree	T(total)	T(data set)	T(total-data set)	Stack max. depth
			token rank size(tokens)	In second	In second	In second	In (tokens)
	y1	A1000001	1000000	10000004	25,16	6,69	18,47	0
	y1	A5000001	5000000	50000004	131,87	34,84	97,02	0
	y1	A10000001	10000000	100000004	263,97	67,68	196,29	0

Wide tree data set -time and memory tests (negative queries)

Table 5 :

 5 Deep tree data set -time and memory tests (negative queries)

	Test type Token name	Data set	Input tree	T(total)	T(data set)	T(total-data set)	Stack max. depth
			token rank size(tokens)	In second	In second	In second	In(tokens)
	y1	A1000001	1000000	10000004	24,79	6,73	18,06	0
	y1	A5000001	5000000	50000004	129,17	34,66	94,51	0
	y1	A10000001	10000000	100000004	260,4	68,69	191,71	0

An XPath predicate is contained with-in square brackets [], and comes after the parent element of what will be tested. It filters a node-set with respect to an axis to produce a new node-set.

Ocaml is a language of the ML family. It is well adapted to tree processing and its optimizing compiler ocamlopt produces fast executables