Beakal Gizachew

Belgin Ergenc
email: belginergenc@iyte.edu.tr

OrderBased Labeling Scheme for Dynamic XML Query Processing

Keywords: XML Query Processing, Dynamic Labeling Scheme, OrderBased Labeling Scheme

Need for robust and high performance XML database systems increased due to growing XML data produced by today's applications. Like indexes in relational databases, XML labeling is the key to XML querying. Assigning unique labels to nodes of a dynamic XML tree in which the labels encode all structural relationships between the nodes is a challenging problem. Early labeling schemes designed for static XML document generate short labels; however, their performance degrades in update intensive environments due to the need for relabeling. On the other hand, dynamic labeling schemes achieve dynamicity at the cost of large label size or complexity which results in poor query performance. This paper presents OrderBased labeling scheme which is dynamic, simple and compact yet able to identify structural relationships among nodes. A set of performance tests show promising labeling, querying, update performance and optimum label size.

Introduction

The fact that XML has become the standard format for structuring, storing, and transmitting information has attracted many researchers in the area of XML query processing. XPath and XQuery are languages for retrieving both structural and full text search queries from XML documents [1 and 2]. XML labeling is the basis for structural query processing where the idea is to assign unique labels to the nodes of an XML document that form a tree structure. Label of each node is formed in a way to convey the position of the node in XML tree and its relationship with neighbor nodes. These relationships are Ancestor-Descendent (AD), Parent-Child (PC), Sibling and Ordering [START_REF] Clarke | XML Path Language (XPath) version 1.0,W3C recommendation[END_REF].

There are basically two approaches to store XML document. The first one is to shred the XML document to some database model. The XML document is mapped to the destination data model example, relational, object oriented, object relational, and hierarchical. The second approach is to use native XML Database (NXD) [27, 28, 29, 30 and 31]. Native XML database (NXD) is described as a database that has an XML document as its fundamental unit of storage and defines a model for an XML docu-

Related Work

Labeling schemes can be defined as a systematic way of assigning values or labels to the nodes of an XML tree in order to speed up querying. The problem of finding a labeling scheme that generates concise, persistent labels, supporting updates without the need of relabeling, and ease of understanding and implementation dates back to 1982 [START_REF] Diets | Maintaining Order in a Linked Lists[END_REF]. In the pursuit of solving the labeling scheme problem, a number of approaches have been proposed. These labeling approaches can be grouped in four major categories: Range based, Prefix based, Multiplication based and Vector based.

Range based labels for a node X has a general form of <start-position, end-position>, where start-position and end-position are numbers such that for all nodes Y in the sub tree of X, start_position(Y)> start-position(X) and end-position (Y) < endposition(X). The variations among range based labeling schemes are due to the definition of start-position and end-position. For instance, [3, 4 and 5] define the startposition as pre-order traversal of a tree. Traversal Order, Dynamic Range Based labeling schemes take the end-position as post traversal order of a tree, Extended Traversal Order [START_REF] Li | Indexing and Querying XML Data for Regular Path Expressions[END_REF] consider it as the size of the sub tree which is greater than or equal to the total number of nodes in the sub tree. On the other hand, SL (Sector based Labeling scheme) [START_REF] Fomichev | Sedna: A Native XML DBMS[END_REF] defines the ranges as angles. The sectors are allocated to nodes in such a way that the angle formed by a parent's sector at the origin completely encloses that of all its children. Range based labeling schemes generally produce concise labels and are fast in determining ancestor descendant relationships; however, except for Sector Based labeling scheme, they do not provide sufficient information to determine parent-child and sibling-previous/following relationships. In addition, even the dynamic labeling schemes do not avoid relabeling completely, they only support updates to some extent.

In Prefix based labeling schemes, node X is an ancestor of node Y if the label of node X is the prefix of node Y. The main advantage of Prefix based labeling approach is that all structural relationships can be determined by just looking at the labels. The main critics about prefix based labeling schemes is its large storage requirement. Simple Prefix labeling scheme [START_REF] Cohen | Labeling Dynamic XML Trees[END_REF] and Dewey ID [START_REF] Tatarinov | Storing and Querying Ordered XML Using a Relational Database System[END_REF] are not efficient for dynamic document since insertion needs relabeling of nodes. ORDPATH [START_REF] Oneil | ORDPATHs: Insert-Friendly XML Node Labels[END_REF] supports updates without relabeling by reserving even and negative integer. However, after the reserved spaces are used up, relabeling is unavoidable. LSDX -Labeling Scheme for Dynamic XML documents [START_REF] Duong | LSDX: New Labeling Scheme for Dynamically Updating XML Data[END_REF] is a fully dynamic prefix labeling scheme. Nonetheless, it generates huge sized labels and does not guarantee unique labels. Com-D -Compact Labeling Scheme [START_REF] Duong | Dynamic Labeling Scheme for XML Data Processing[END_REF] reasonably reduces the size of labels through compression. However, compression while labeling and decompression while querying dramatically degrades its efficiency. Whereas LSDX avoids relabeling after updates at the cost of storage, Com-D achieves reasonably small storage requirement at the cost of labeling and querying time.

Multiplicative labeling schemes use atomic numbers to identify nodes. Relationships between nodes can be computed, based on some arithmetic properties of the node labels. The main limitations of this approach lies in its expensive computation and large size. Hence, it is unsuitable for labeling a large-scale XML document. Prime Number labeling scheme [START_REF] Wu | A Prime Number Labeling Scheme for Dynamic Ordered XML Trees[END_REF] and Unique Identifier labeling scheme [START_REF] Kha | A Structural Numbering Scheme for XML Data[END_REF] are examples of a multiplication based labeling schemes.

The other groups of labeling scheme that are seen in literature are based on vector order. A vector code is a binary tuple of the form (x, y) where x > 0. Given two vector codes A: (x1, y1) and B: (x2, y2), vector a precedes vector B in vector order if and only if

. If we want to add a new vector C between vector A and B, the vector code of C is computed as x1+x2 , y1 +y2).The vector order of A<B<C because holds true [START_REF] Xu | A Dynamic Labeling Scheme Using Vectors[END_REF]. It is demonstrated that the vector based approach can be applied to both range based and prefix based labeling schemes [START_REF] Xu | Labeling dynamic XML Documents: An Order-centric Approach[END_REF]. DDE and CDDE are application of vector order approach to Dewey ID [START_REF] Xu | DDE: From Dewey to a Fully Dynamic XML Labeling Scheme[END_REF] whereas Vcontainment its application to range containment labeling scheme [START_REF] Xu | DDE: From Dewey to a Fully Dynamic XML Labeling Scheme[END_REF]. Vector based labeling schemes avoid relabeling in update intensive environment and can be applied to any other labeling schemes, however, there is always a computation overhead to determine relationship among nodes.

Recently it is common to see a hybrid labeling schemes which balances the weakness of one approach with the strength of another approach [25 and 26]. There are also labeling schemes that capitalize on the characteristics of data structures [START_REF] Silberstein | BOXes: Efficient Maintenance of Order-Based Labeling for Dynamic XML Data[END_REF], or make use of the type information or DTD [START_REF] Damien | Dynamic Labeling Schemes for Ordered XML Based on Type Information[END_REF]. Moreover, Twig pattern matching algorithms has been researched for fast xml query processing [32, 33 and 34].

Generally, labeling schemes that generate small sized labels neither provide sufficient information to determine all structural relationships nor are efficient in a dynamic environment [3, 4 and 5]. On the other hand, labeling schemes that generate labels that provide enough structural relationship information and also support updates without relabeling either are large in size or are inefficient in query processing.

OrderBased Labeling Scheme

OrderBased labeling scheme presented in this paper is based on combination of letters and numbers. Each label contains level, order of the node in the level and the order of its parent. First part of the label is numeric and indicates the level information of a given node. The second part gives alphabetical order of the node relative to the left most node of the level. The last part is the order of the parent node. The order and the level information guarantee unique labels. The usage of characters enables it to generate a completely new order before and after the position of a given node, and also between two nodes without affecting existing order in case of insertions. For instance given two orders O1, and O2 where O1="abc" and O2= "bd", we can generate as many strings as we need which are between O1 and O2 in alphabetic order ("abcb", "abcd", "abce"..).

In OrderBased labeling scheme each label is a triple <level, order, parentorder>, where level is an integer that represents the distance of the node from the root node, order is a character that represents the level based horizontal distance of the node from the left most node at each level, parentorder is the parent's order of a given node .The level of the root node is 0, and the level of the children of the root node is 1. Likewise, the levels of other nodes can be computed as the distance of the node from the root node as seen in Fig 1.

Fig. 1. OrderBased labeling scheme

An OrderBased label provides the information of the parent-child, and siblingsfollowing/previous in a direct way, and ancestor-descendant relationships in recursive manner. For example in Fig 1, the node with label "1e, a" is the parent of the nodes with labels "2g, e", "2h,e", and "2i,e". This parent to child relationship is provided because the parent order of the three nodes is "e", and presumably their level is 1+1=2. Moreover, nodes that have the same level information and with the same parent order are siblings. However, to find the ancestors /descendants of a given node, first there is a need to move to the parent/children, and then the parent of the parent/children recursively till the intended level is reached.

Optimizing the Size

To address the problem of large storage size, OrderBased labeling scheme has a routine which optimizes the label size of every level. Small label sizes enhance query, update and labeling performances. Before labeling or making any insertions, the Or-derBased labeling scheme computes the optimal number of characters needed to label the nodes at every level. To illustrate the need of optimizing the size, we will give a brief description of the size requirement in terms of number of characters.

Assume the total number of nodes at a given level is M. If we start labeling order of the first node in the level by 'b', the labeling continues with 'c', accordingly the orders of the 25th and 26th nodes will be 'z' and 'zb' respectively. Since there is a need of concatenating extra 'b' after reaching the letter 'z' in ever 26th node, the size of the order increases dramatically. If the total number of nodes at a given level M is not greater than 25, we can generate M unique one character length orders using al The total size requirement for orders at a given level with a total number of nodes M can be generalized as, + M mod 25*(w+1) [START_REF] Boag | XQuery 1.0: An XML Query Language[END_REF] where w=floor (M/25). In order to have an optimal size of orders, the OrderBased labeling first calculates the number of characters needed to label M number of nodes. The function Ceil returns the smallest integer that is greater than or equal to the given expression. For example, ceiling (1.45) =2, ceiling (9.8) =10.

By this approach the first child is labeled with X number of b's. For example if M is 625, X computed to be 2 , the order of the 1st ,2nd , 26th, 624th , and 625th is 'bb','bc','cb','zy', and 'zz' respectively. By this approach, the total size of orders for all nodes of a given level is (2) Table 1 shows a comparison of the total number of characters needed to label the order of nodes using optimized and un-optimized approaches. For M<=25 both approaches need same storage requirement, while the number of nodes M is from 26 to 99, storage requirement for the un-optimized approaches is slightly smaller. Generally, for the number of nodes M>100, the storage requirement for the optimized approach is always smaller than the storage requirement of the un-optimized approach. The difference of the storage requirements for the two approaches considerably increases as the number of nodes M increases. This makes the optimized approach to be preferred to the un-optimized approach.

In OrderBased labeling scheme, optimizing the size is a prior operation before labeling and inserting a sub tree. The Determine-size routine seen in Fig 2, takes the XML tree to be labeled or inserted as input computes the number of nodes at every level, then returns a string array.

For example , if a given XML document has 500, 3000, 9000 , 1000000, and 2000000 number of nodes at 1st, 2nd ,3rd, 4th and 5th level respectively, the above routine returns Y, where Y

3.2

Generating the Order of a Node

Rule 1

Label the order nodes of a given level starting by the concatenation of b's returned by the Determine-size routine. For the second, third, and forth node, increment the last character to 'c','d', and 'e' respectively. Accordingly for the rest of the nodes, increment the orders alphabetically.

For example if 'bbb' is the string returned for a given level, the order of the 1st, 2nd , 25th , 26th , an 15625th node are labeled as 'bbb', 'bbc',' bbz', 'bcb',and 'zzz' respectively.

Generating Orders for New Inserted Nodes

Rule 2

To insert a node before the first node of a given level, get the order of the node then count down to the preceding alphabet, if all characters are "b", insert "a" before the last "b". Here Rule 2 is applied to insert a node before "1b,a". Because there is no node before it we add 'a' before 'b' then we will have "1ab,a". At the second level, there are two nodes to be inserted before "2b,b". Thus, applying Rule 2, the labels of the inserted nodes will be "2,ab,ab", and "2aab,ab". Similarly, the labels of the two nodes at level 3 will be "3ab,ab" and "3aab,ab". Insertions before the first node of a given level can be handled by applying Rule 2 without the need of relabeling.

Rule 3

To insert a node between two nodes, keep counting from the code standing before it so that the code for the new node will be greater than the code of its previous sibling and less than the code of its next sibling.

It can be seen from Fig 3 that, insertion between two nodes can be made without affecting the order of the existing nodes. Applying Rule 3 at the first level a unique label "1bb,a" is generated between "1b,a" and "1c,a". Likewise at level 3 and level "2cb,bb" , "2cc,bb", and "3cb,cc", "3cc,cc" respectively are unique labels generated between two nodes without the need or relabeling.

Rule 4

To insert a node after the last node of a level, increment the order of the last order alphabetically.

Fig 3 shows how insertion after the left most node of a tree is handled. Rule 4 states that insertion after the last node of a given node is handled by incrementing the order of the last node alphabetically. That is after "1d,a" is "1e,a", likewise, "2g,e" , "2h,e" and "3f,k","3g,k' are after "2i,h" and "3e,e" respectively.

Fig 3 demonstrates that inserting a sub tree at any arbitrary position does not need any relabeling of nodes. Rules 2, 3 and 4 guarantee unique labels are given to the newly inserted nodes or sub tree with regardless of the point of insertion. OrderBased labeling scheme is persistent in that it insures a uniqueness of labels in a dynamic environment.

Performance Evaluation

In this performance evaluation part of the study, OrderBased labeling scheme is compared with the LSDX and Com-D (Compressed LSDX) labeling schemes. These labeling schemes are chosen because they share main feature and design goals. Using combinations of letter and numbers, including the level information of a node in every label, and avoiding relabeling when update occurs are the common feature and design goals of the three schemes. Moreover, because three of them contain the information about the label of the parent node, they can be grouped under prefix based labeling scheme.

There are four sets of tests in this performance evaluation: the first set compares the storage requirement of three schemes. The second set analyzes labeling time. The third set examines the query performance and the last set investigates update performance. Fig. 6. Time required for retrieving all descendants of a given node OrderBased labeling scheme is superior to LSDX and Com-D with respect to querying time. Such a performance hit is due to its optimized size of labels.

Updates

In this update performance evaluation of the study, the time needed to insert a sub tree, and delete a sub tree for the three schemes is analyzed. The most profound problem with most XML labeling schemes is that they are designed with an assumption of static document. Whenever a deletion or an insertion is done on the XML document, relabeling of all or part of the XML tree is inevitable. However, in real world applications, updating an XML document is an important and necessary operation.

Inserting a Sub Tree

In this performance evaluation part of the study, the time to insert a sub tree which is an XML by itself is seen. For this study, an XML dataset D01 of 11.3 MB is generated by giving 0.01 to the factor parameter of the xmlgen generator. Inserting D01 at different part of the XML tree produces same time. Thus, for convenience for all the datasets the D01 is inserted as the child of the root node. Com-D takes more than two times and four times longer time than that of LSDX and OrderBased labeling schemes. These performances degrade is resulted from the time needed for compression, since all labels have to be compressed. that OrderBased is superior to the rest of the schemes with respect to insertion time in that it is twice faster than LSDX and four times faster than Com-D. OrderBased insertion time performance hit is due to its reasonable small size.

Deleting a Sub Tree

In this part of the performance evaluation, the time needed to delete a sub tree is studied. All the three schemes avoid relabeling after deletion. spaces and the labels deleted can be used for future insertions.

For the B+ tree used to store the labels of XML tree nodes, a mechanism of lazy deletion is employed. Lazy deletion does not rebalance the B+ tree on deletion. Avoiding rebalancing on deletion has been justified empirically [12, 13 and 14].

Delete site/closed_auctions: delete the node with name closed_auctions. This is because decompressing is necessary to determine whether the nodes are descendants of the deleted node. OrderBased labeling scheme deletion is 1.5 to 2.33 faster than LSDX.

Discussion on Results

In this performance evaluation study we have seen the storage requirement, labeling time, querying time, insertion time and deletion time for OrderBased, LSDX, and Com-D labeling schemes.

The first test set for storage requirement, LSDX labels need the largest storage requirement .Com-D labels need the least space. The storage requirement for Order-Based labels is nearly as good as the storage requirement for Com-D labels (2.34% to 7.7% greater than Com-D).

The second test set for labeling time requirement shows that OrderBased needs the least labeling time whereas Com-D takes the longest labeling time because of compression overhead. From this result it can be concluded that the larger the label size, the faster the labeling is. On the other hand, the compression reduces the label size; it degrades labeling time more than large label size does.

For querying performance, for small data sets, it seems LSDX and OrderBased take equal time. However, as the data size increases, it becomes clear that Order-Based needs the least time. Com-D has the least performance because of the need of decompression.

In the fourth test, update performance (insertion and deletion) time requirement is studied. With regard to insertion, OrderBased needs the least time. Again Com-D needs the longest time because of compression overhead. For deletion time requirement test, OrderBased needs the least time.

Conclusion

This paper pointed out the challenges of dynamic labeling scheme for XML documents. Large storage requirement, inefficient labeling or querying time and complexi-ty are challenges of dynamic labeling schemes. To address these problems, a fully dynamic labeling scheme called OrderBased labeling scheme is proposed. Performance evaluation studies show that OrderBased labeling scheme outperforms LSDX and Com-D with respect to labeling time, query performance, and update performance. It is also shown that the total label size for OrderBased labels from 91.1% to 91.95% smaller than label size of LSDX. Even though OrderBased label size is from 2.4% to 7.1% greater than that of Com-D, its efficient querying, labeling and update performance makes it preferable.

  phabets from b to z. If M is between 26 and 50 inclusive, we use 25 single character alphabets and (M-25) double character length. For example If M= 10, 40, 66, and 90, then size requirement is then 1(10) =10, 1(25) + 2(40-25) =55, 1(25) + 2(25) + 3(66-50) = 123, and 1(25) +2(25) + 3(25) + 4(90-75) = 210 number of characters respectively.

  [1]='bb', Y[2]='bbb', Y[3]='bbb', Y[4]='bbbbb', and Y[5]=' bbbbb'.

Fig. 2 .

 2 Fig. 2. Determine-size routine

Fig. 3 .Fig 3

 33 Fig.3. Sub tree insertion before the first node of a given level, between two nodes and after the last node of a given level

Fig 7 .

 7 Fig 7. Insertion time (sec).Fig 8. Deletion time (ms)

Fig 8 .

 8 Fig 7. Insertion time (sec).Fig 8. Deletion time (ms) Fig 7 shows that the time of insertion of DO1 to the six datasets is nearly constant irrespective of their size. Moreover, insertion time mainly depends on the size of the inserted sub tree.Com-D takes more than two times and four times longer time than that of LSDX and OrderBased labeling schemes. These performances degrade is resulted from the time needed for compression, since all labels have to be compressed. Fig 7 illustrates

  Fig 7 shows that the time of insertion of DO1 to the six datasets is nearly constant irrespective of their size. Moreover, insertion time mainly depends on the size of the inserted sub tree.Com-D takes more than two times and four times longer time than that of LSDX and OrderBased labeling schemes. These performances degrade is resulted from the time needed for compression, since all labels have to be compressed. Fig 7 illustrates

Fig 8

 8 Fig 8 depicts that Com-D takes the longest time to delete in all the six datasets.This is because decompressing is necessary to determine whether the nodes are descendants of the deleted node. OrderBased labeling scheme deletion is 1.5 to 2.33 faster than LSDX.

Table 1 .

 1 Analytical storage requirement

	M	Optimized	Un-optimized
	24	24	24
	50	100	75
	75	150	75
	100	200	250
	1000	3000	20500
	2000	6000	81000
	1000000	5000000	20000500000

Experimental Setting

The performance evaluation is conducted on an Intel(R) Core™2Duo CPU E8400 @3GHz.27 GHz and 2.00 GB of RAM Windows 7 Professional computer. All schemes are implemented using Visual Basic .net 2010. So as to avoid discrepancy, each querying and labeling time performance test is run 5 times and the average is taken.

A B+ tree is used to store the labels. In the non-leaf nodes of the B+ tree, only labels are stored. In addition to labels, the leaf nodes contain the name of nodes of the XML tree or attributes with their corresponding values [15 and 22].

Characteristics of Datasets

The datasets used in this performance evaluation are generated using xmlgen of the XMark: Benchmark Standard for XML Database Management [START_REF] Schmidt | XMark: A Benchmark for XML Data Management[END_REF]. The xmlgen produces XML documents modeling an auction website, a typical e-commerce application. It generates a well-formed, valid and meaningful XML data. Xmlgen is well known for its efficient and scalable generation of XML documents of several GBs.

Number and type of elements are chosen according to a template and parameterized with certain probability distributions. The words for text paragraphs are taken from Shakespeare's plays. The generator is deliberately designed to have only a single parameter: factor. The factor parameter determines the size of the document generated. It accepts float number from 0 to any number. Zero value for the factor generates the minimum document. By giving values from 0.5 to 1.0 to the factor parameter of the xmlgen, six datasets with size of 56.2 to 113 MB, with number of nodes ranging from 832,911 to 1666315 and maximum fan-out starting 12750 to 25,500 are generated. The characteristics of the datasets are seen in Table 2.

Storage Requirement

In this performance evaluation test set, the storage requirement for the three schemes is studied. For the six datasets introduced in the previous section, the sizes of labels in MB are shown in Fig 4.

The storage requirement of LSDX labels is the largest as compared to the rest of the two. This resulted from the fact that LSDX label size depends on fan-outs and the height of the tree. To illustrate: for the first 25 children the size of a LSDX label is 25 characters (letter b to z) plus the label of the all its ancestors. Since after every 25th children we reach at letter z, there is a need to concatenate b. This makes the label size to increase by one character. The storage requirement for LSDX labels depend on the fan-outs and the height of the tree (since each label contains the label of its ancestor nodes). The more the number of fan-outs and the taller the tree, the larger is the label size. Com-D is a compressed version of LSDX. The compression is done by counting the number of times a letter is consecutively repeated. For example if the LSDX label of an XML node is abzzzzzzrr.dd, its equivalent Com-D label is ab6z2r.2d [START_REF] Duong | Dynamic Labeling Scheme for XML Data Processing[END_REF].

As it can be seen from Fig 6, for all the datasets used in this performance analysis, Com-D needs the least storage requirement. Com-D label size is from 91% to 95% smaller than LSDX label size. The figure also demonstrates that the storage requirement for OrderBased labels is from 91.11% to 94.94 % smaller than the storage requirement of LSDX labels. For dataset D05, OrderBased label size is the same as that of Com-D. However, for the rest of the datasets, the storage requirements are from 2.4% to 7.7% greater than the label size of Com-D.

Collision is one of the drawbacks of the LSDX and Com-D labeling scheme. For every dataset used in this performance evaluation, the two schemes give the same label for more than one XML nodes. Table 3 demonstrates the number of collisions detected while labeling using the LSDX and Com-D labeling schemes. For this reason, both LSDX and Com-D are impractical. In OrderBased labeling scheme, there is no collision. It avoids collision by keeping a global level based horizontal order and parent order. Both LSDX and Com-D are impractical due to the existence of collision. OrderBased is superior to the two labeling schemes for its persistence and optimal storage requirement.

Labeling Time

In this sub section, the time required to label a given XML document is studied. The time required for labeling that is seen on Fig 5 above is the average labeling time taken from five tests done on each dataset. The labels are generated by a depth first traversal for the three labeling schemes.

Fig 5 stipulates that for all the six datasets, LSDX is at 7.99 to 15.74 times faster than Com-D. With regard to labeling time, OrderBased labeling scheme is approximately 2.2 to 3.9 and 17.28 to 51.8 times faster than LSDX and Com-D labeling schemes respectively.

The labeling time performance hit of OrderBased over LSDX is due to LSDX's larger label size (Fig 4 : the total label size of LSDX is more than 100 to 400 times larger than the total label size of OrderBased). Even though Com-D labels need the minimum storage requirement, it takes the longest labeling time. This decrease in labeling performance results from compression overhead.

The labeling time test set shows that OrderBased labeling scheme takes the least labeling time compared to LSDX and Com-D labeling schemes. This labeling time performance hit of OrderBased is because of the optimal label size. From this result it can be concluded that compression degrades labeling time performance more than large label size does.

Query

In this performance evaluation part, a query which returns all descendants of the root node is run. Finding descendant of a given node depends on the time required for Parent-Child, and Sibling-Order queries.

Given an ancestor finding its descendants is one of the structural queries found in XML querying. These types of queries are usually seen in XPath statements. The query for retrieving all descendant of a root node is equivalent to the XPath expression Site/*(since the root node of the data sets used in this performance evaluation is site).

For a reasonably small size and small number of nodes of a given XML data set, LSDX and OrderBased take nearly the same time. However, OrderBased executes faster as the data size and the number of nodes increase. In addition, both LSDX and OrderBased labeling scheme are incomparably faster than Com-D. This performance variation comes from decompressing overhead for Com-D. Com-D querying involves decompressing of each label. It can be seen from Fig 6 that decompressing degrades query performance than label size does.


Louis De

Author Louis De Mesnard
email: louis.de-mesnard@u-bourgogne.fr

Keywords: ■TEL classification. C67, D46, D57. KEYWORDS. Input-Output, Supply-driven, Ghosh, Latent prices

The Ghosh model, a supply-driven input-output model, uses money terms rather than physical terms for all flows or outputs, "latent prices" (or price indexes) rather than true prices, and "demand prices" rather than "supply prices" (or "production prices"). This paper explores the consequences of these substitutions by comparison with the traditional Leontief demand-driven model. In conclusion, the Ghosh model (particularly because of its latent demand prices), is not as credible as the other version, while itself offers very limited results.

Introduction

The Ghosh model (1958) assumes that, in an input-output framework, each commodity is sold to each sector in fixed proportions. It is a view that has its critics and its supporters (Bon, 1986(Bon, , 2000;;Chen, 1986Chen, , 1991;;Davar, 1989;[START_REF] De | A biproportional filter to compare technical and allocation coefficient variations[END_REF][START_REF] Deman | Stability of Supply Coefficients and Consistency of Supply-Driven and Demand-Driven Input-Output Models[END_REF]Deman, , 1991;;[START_REF] Dietzenbacher | On the relationship between the supply-driven and the demand-driven input-output model[END_REF]Dietzenbacher, , 1997;;Helsmstadter and Richtering, 1982;[START_REF] Gruver | A comment on the plausibility of supply-driven input-output models[END_REF][START_REF] Miller | Stability of supply coefficients and consistency of supply-driven and demand-driven input-output models: a comment[END_REF][START_REF] Oosterhaven | On the plausibility of the supply-driven input-output model[END_REF]Oosterhaven, , 1989Oosterhaven, , 1996;;[START_REF] Rose | On the plausibility of the supply-driven input-output model: empirical evidence on joint stability[END_REF]Allison, 1989, Sonis and[START_REF] Sonis | Coefficient Change in Input-Output Models: Theory and Applications[END_REF]. The model has a number of other special features: 1) all flows or outputs are in money terms and not in physical terms, 2) as a corollary, "latent" prices (i.e. price indexes) are used instead of true prices, and 3) demand prices (i.e. prices that affect a whole column of the exchange table) replace supply prices (i.e. "production prices" in the Classical sense, affecting a whole row of the exchange table, that is prices of commodities sold by sector; for a review, see [START_REF] Seton | Price models based on input-output analysis: East and West[END_REF]. Money terms and latent demand prices are not the only way to develop the model: physical quantities, true prices and supply prices could also have been introduced. In this paper, a near-complete typology of the possible models will be presented, reasoning both in physical terms and in money terms, both with true and latent prices, and both with demand and supply prices, through comparison with the traditional demand-driven model. It will be shown that the "Ghoshian version" of the supply-driven model with its demand prices is not as credible as the supply-price version, which in turn offers very limited results.

A. The hypothesis of the simple linear model of production and exchange

In this section I follow [START_REF] Gale | The Theory of Linear Economic Models[END_REF]

B. The demand-driven model

In the demand-driven model, it is assumed that each sector buys each commodity in fixed proportions, but there are two possibilities: coefficients may be defined in physical terms or in value terms.

-

Z ii

If coefficients are defined in physical terms, it is assumed that the ratios ay = -are stable for all i xj and j. Note that nothing prevents the coefficients from being greater than 1, their magnitude depends on the chosen scale but the determinant is scale-independent, as is the result, after the appropriate conversion of scale. In matrix terms, this can be written: Â = Z (x)_1 .The economy must be at equilibrium by row and by column. By rows (I call this the primal), the accounting identity ( 1) becomes 2 , a i} xj + / , = x ,, that is:

(3) Âx + f = x « ^I -Â j x = f

C. The supply-driven model

the supply-driven model with demand prices.

Supply prices

Supply prices are also demand prices: they are used above for the demand-driven model.

Homogeneity by columns is not assumed. It is assumed that each commodity is sold in fixed proportions to each sector. Again there are two possibilities.

-Zy . In physical terms, by = -is assumed to be stable for all i,j; in matrix form, this can be written When computed in money terms, the stable coefficients are defined as follows:

bn --= Z J ^1 ==r-= bu for all i, as they are equal to the coefficients in quantities, the model

,J X i X i p i X i
is exactly the same as above, either by rows or by columns.

Dichotomy is not guaranteed with either type of coefficient: in the primal, nothing is obtained, while in the dual, only values in money terms are found, so there is no way of telling whether it is prices or physical quantities that have varied.

Note that as

Demand prices

Although the following formula appears to lack credibility, it is introduced at this point as it will be useful for what follows. The supply-driven model can be written by considering "demand prices", that is prices affecting a column of the exchange table, as in:

(9) 'Lz,JP j + f , P f = XiPi j but the product of a quantity zy of commodity i sent to j multiplied by the price pj is simply meaningless in economics. In column j, the agent j is assumed to buy all commodities at the same price, whatever the nature of this commodity. For example, what could be the meaning of the product of 1) a quantity zy of steel (/) sold to the automobile industry (/) by the steel industry, multiplied by 2) a price pj of automobiles, even if this price is a "demand price"? It contradicts the hypotheses of the linear models of exchange and production. The same holds for the final demands / , for commodities i to which the same price pf is assigned.

Zi j

With coefficients of money terms, the "economic allocation coefficients" are again by = -but what must be chosen for zyl Is it zy = zyp, or zy = zypp. The answer is unclear: it seems logical enough to multiply z.y by pt but this is in contradiction with the philosophy of the Ghosh model, while to multiply it by pj invites the same criticisms as for demand prices above.

III. Latent prices

The above reasoning explains what happens with true prices, particularly for the supply-driven model. This leaves the question of what happens with latent prices. Many authors (e.g., Davar, 1989;Oosterhaven, 1996;Dietzenbacher, 1997) have touched upon the plausibility of latent prices, or price indexes. Latent prices, denoted it, are not incorrect per se: they are introduced as the ratio of the prices of the current year to those of the base-year; the models are formally unchanged, except that latent prices replace true prices.

A. The demand-driven model

The demand-driven model is not radically changed when latent prices are substituted for true prices, except that latent prices are applied to values in money terms, not to physical quantities.

For the primal, formula (1) is unchanged, that is 2y zij ni + ft = x> 71 < <=> 2y zy +fi = */ > which implies that 2 7 oy Xj +/} = xt, that is A x + f = x: the outputs, x, in money terms are formed from final demands, f, in money terms.

In the dual, equation ( 2) transforms into:

(10) 2 z ,j Tli + Vj 1ZW = Xj Tlj i which implies that 2 , ay xj 71/ + vyn w = X j K j <=> 2,-ay%i + n w = Kj-> where lj = \^ is the coefficient of value added measured as a ratio of money terms, that is it' A + nw \J = %': the latent prices, it, are formed from L, the vector of value-added coefficients.

As in the base year, K, = 1 for all i, which does not affect (1), while (2) becomes 2 , zy + vj = xj, which is exactly the same as (2). Homogeneity by rows and columns is required for this model:

there is only one commodity, in money terms, that is distributed from sectors and factors to sectors and final demand.

B. The supply-driven model

With the supply-driven model things are more complicated. When latent prices are applied to values in money terms, two categories can again be considered, namely supply prices and demand prices.

For the primal, formula (1) transforms into Again dichotomy is not guaranteed either in the primal or in the dual. From (11), outputs in money terms are found, so there is no way of saying whether it is the quantities in physical terms or the prices that have changed. In ( 12) or ( 13), things are worse still: it cannot be determined whether it is the latent prices or the values in money terms that have varied, but it is certain that a variation in a latent price obviously implies a variation in a true price, and probably a variation in the corresponding value in money terms...

Latent supply prices

With demand prices, by rows (1) becomes:

(1 3 ) 2 Z y T l j + f i = X / Ttj j f .
that is Xy by xt Kj +fi nf =x, %, <=> 2 , by Ttj + di # = 7i,, where = j; is the coefficient of final demand measured as a ratio of money terms, that is B n + d n/ = n : latent prices n are found from the latent price of final demand v/.

By columns, (2) changes into: an output in money terms is found from the compensated value added. If all latent prices are set to one, in the base year, then (14) changes into 2 , Z(/ + y/ =jc/ and the result becomes 2 , by Xj + Vj = Xj (Oosterhaven, 1996, p. 753), a correct result but valid only for the base year, while ( 14) and ( 15) are more complicated but valid for all years.

Discussion

Formulas ( 13) and ( 14) correspond to what is known as the Ghosh model: as pointed out by Oosterhaven (1996), it is assumed that input is now homogenous by columns. However,

Latent demand prices

homogeneity is required by rows also: for the base year, all latent prices are equal to 1, and ( 13) becomes zu + ft =*/, which is nothing other than (1). So, homogeneity is guaranteed in rows and columns alike, i.e. there is only one input commodity and one output commodity, composed of money, and distributed from value added and sectors to sectors and final demand, as in the demand-driven model. This is why homogeneity can be assumed for columns, even if the flows zy in physical terms are not homogeneous. The flows zy in money terms are homogenous, but this homogeneity is fictitious; it is the homogeneity of money, not of the real world of terms zy.

Equation ( 13) or ( 14) could imply two alternative consequences.

1) True demand prices are combined with latent demand prices, multiplying zy = zypj by w Pi %j = -j-(considering the most simple type of price index; Laspeyres or Paasche are more Pi sophisticated, taking into account not only the evolution of true prices but also of physical quantities). That is agent j increases (or decreases) its true demand prices for a same column by the same percentage (which might be an acceptable hypothesis but true demand prices have no meaning as demonstrated above).

2) Alternatively, true supply prices are combined with latent demand prices: zy = z y pt is U ) Pj multiplied by n j = --r r . This hypothesis is rather difficult to justify because how could an agent j Pj exert a uniform action over the prices controlled by all producers i? This leads then to the concept of personalized prices and even to bilateral prices, formed by a bilateral monopoly, by mutual agreement, which can be written py. In this last case, it is obvious that these n2 prices cannot be computed. Finally, demand latent prices lack consistency, although they seem to convert the Ghosh model into the dual of the Leontief model.

Moreover, for the Ghosh model as for the Leontief model, the fact that latent prices are not equal to 1 violates the hypothesis of stability of technico-economic coefficients.

Remark. The above reasoning is unchanged when multiple categories of final uses and multiple factors are considered.

IV. Conclusion

This paper has examined the consistency of one of the two main input-output models, the supply-driven model developed by Ghosh, with emphasis on the question of the treatment of quantities and prices. In the Ghosh model, all flows or outputs are generally expressed in money terms rather than in physical terms, "latent" prices (price indexes) are used instead of true prices and demand prices replace supply prices (production prices). By comparing this model with the traditional Leontief demand-driven model, this paper has explored the consequences of replacing quantities in money terms by physical terms, latent prices by true prices, and demand prices by supply prices.

It has been demonstrated that a supply-driven model with true prices is consistent only with supply prices, but these true prices cannot be determined by the model. True demand prices are not economically well founded.

The demand-driven model is compatible with latent prices. However, for the supply-driven model with latent supply prices, it becomes possible to determine only "super values" (that is the product of a value in money terms by a latent price), but never latent prices themselves. Latent demand prices in the supply-driven model seem to be acceptable at first glance, but 1) latent demand prices rely on complete homogeneity by rows and columns which can be considered only in money terms, and 2) demand latent prices remain difficult to interpret because they entail the assumption that true demand prices exist, which has been ruled out.

Finally, the supply driven model in its "Ghoshian version" (latent demand prices) is less credible than the other versions (latent supply prices, but also true prices), which themselves offer very limited results. Should we abandon the Ghosh model? Probably not, for at least two reasons.

First, technical coefficients are not much more stable than allocation coefficients over time (Bon 1986(Bon , 2000)), [START_REF] De | A biproportional filter to compare technical and allocation coefficient variations[END_REF], so the Ghosh hypothesis does not seem any less reliable than the Leontief hypothesis. Second, the supply-driven model is acceptable in its supply-price version, even if values can only be computed in money terms.

  , leaving aside die more complicated cases such as the "von Neumann model". Consider n sectors, producing n commodities, and a set of final consumers. Each sector produces one and only one commodity and each commodity is produced by one and only one sector. The physical quantity bought by sector j from sector i when j produces commodity j is denoted zy. By hypothesis z ,y > 0. The model is closed: for each commodity i, the total sold is equal to the total produced and is denoted 3c,, with 3c, = z ¡j + / , , where / , > 0 denotes the final demand. Note that if the rows of matrix X are accepted as homogeneous, columns cannot be summed. Commodities i have a price p \ : these prices are true prices in the usual economic sense of the word. Initially, the value of each commodity / is equal to 3c, /?, and each sector j has in hand Xj of money. The model is monetarily closed: agents have the same quantity of money before and after an exchange, i.e. the model is at equilibrium sector by sector, that is XiPi = Xj for all i. So, after an exchange, the value of each product i is disposed in both sides of the equation, where zy = zy pi is the value of the flow from i to j and ft = f i pi is the final demand in value; and each sector j spends all of the money w is the value added measured in money terms, while vj is the amount of labor employed by sector j, and w is the wage rate (profits are taken as the owner's remuneration). To shift to a linear model of exchange, it is sufficient to posit / , = 0 and v, = 0. Then, two main hypotheses about behavior can be made: either demand drives the model or supply does.

  the sake of convenience. In particular, value coefficients allow aggregation of the very large number of elementary commodities (e.g. the numerous types and grades of steel) into the small number of commodities usually chosen (e.g. "Steel"). However, these coefficients defined in money terms are only a stopgap. They should be called "technico-economic coefficients" rather than "technical coefficients" because their stability implies stable prices (in fact, the stability of the ratio as soon as a,j is assumed to be fixed). Technico-economic coefficients should not be considered as the normal case. The normal case remains that of coefficients defined in physical terms with commodities and flows expressed in physical units, driven model in quantity (3) will likewise always have a non-trivial solution unless prices are null. Moreover, if f > 0 and as f = x -A x , then x > A x : matrix A is always productive; the demonstration of the condition of productivity x > A x can be found in (Gale, 1989, p. 296-...).

  x)-1 Z. By rows, (1) becomes 2 , by + di = 1 for all i where d t = -=L, that is: Xi (7) Bs + d = s « ^I -B j s = d Again, this imposes 11 -B | ^ 0 to be always true. Note that this equation never provides prices as it might be expected to do at first glance. By columns, (2) is transformed into 2 , by Xi + Vj = ^» 2 ( by Xi p i + v j w -Xjpj for all i, that is: Two variants of the model can be explored: the supply-driven model with production prices and (8) Note that this expression is in money terms, not in quantities as might be expected at first sight. It always has a solution x' = \ ' (i -B j since | l - § | * 0 . As can be seen, prices (of commodities) are undetermined: neither (7) nor (8) provide prices.

For

  be simplified on both sides of this equation. Mutatis mutandis the same reasoning as above applies: latent prices are undetermined. The rest is as in the demand driven model: outputs in money terms, x, are formed from final demands in money terms, f. b y x, 71/ + y, nw = Xj %j => 2 , b y 3c, + = Xj or x/ B + v/ = x/ , where x i = x, 71, and v j = v,-could be called "super values", that is values formed by the product of a value (i.e. a quantity in money terms) by a latent price. This dual allows only the super values x to be determined from the super value of value added v, but never values or latent prices.

  Zij Kj+ vj = xj jij i which implies that nj 2,-byXi + nw vj =xj Uj <^> 2 , b,j x, + wj = Xj, where wj = v, may be termed "compensated value added", that is (15) x' B + w' = x'

  . 1986. "Comparative stability analysis of demand-side and supply-side input-output models," International Journal o f Forecasting 2: 231-235. _______2000. Economic Structure and Maturity. Collected Papers in Input-Output Modelling and Applications, Ashgate, Adelshot. CHEN, Chia-Yon and Adam ROSE. 1986. "The Joint Stability of Input-Output Production and Allocation Coefficients," Modeling and Simulation 17: 251-255.


Omar Boussaid
email: omar.boussaid@univ-lyon2.fr

Rachid Aknouche
email: rachid.aknouche@univ-lyon2.fr

Ounas Asfari
email: ounas.asfari@univ-lyon2.fr

Fadila Bentayeb
email: fadila.bentayeb@univ-lyon2.fr

Integrating Query Context and User Context in an Information Retrieval Model Based on Expanded Language Modeling

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Most existing Information retrieval systems depend, in their retrieval decision, only on queries and documents collections; information about actual users and search context is largely ignored, and consequently great numbers of irrelevant results occur. Towards the optimal retrieval system, the system should exploit as much additional contextual information as possible to improve the retrieval accuracy, whenever this is available.

Context is a broad notion in many ways. For instance, [START_REF] Dey | Toward a better understanding of context and contextawareness[END_REF] define context as any information that can be used to characterize the situation of an entity. An entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and applications themselves. The effective use of contextual information in computing applications still remains an open and challenging problem. Several researchers have tried over the years to apply the context notion in information retrieval area; this will lead to the so-called contextual information retrieval systems which combine a set of technologies and knowledge on the query and the user, in order to deliver the most appropriate answers according to the user's information needs.

As information needs are generally expressed via queries and the query is always formulated in a search context, contextual factors (such as the user's domain of interest, preferences, knowledge level, user task, etc.) have a strong influence on relevance judgments [START_REF] Ingwersen | Information retrieval in context[END_REF]. But it is difficult to find a contextual information retrieval system that takes into account all the available contextual factors at the same time. Thus the context can be defined as the combination of some contextual factors which may be more or less relevant according to the actual performed research. Indeed, in this paper, we try to consider two types of context, user context and query context. We think that these two contextual factors can improve the information retrieval model.

In this paper, the user context is defined by the user's domain of interest or the interesting topic. We propose a thematic algorithm to describe the predefined user's topics which are characterized by a set of documents. Considering the user's interested topics allows providing more relevant results. The second considered contextual factor is the query context, which includes a linguistic and a semantic knowledge about the user query in order to explore the most exact understanding of user's information needs. Thus, we extend the user query by related terms automatically by using the linguistic and semantic knowledge. Also, we propose a framework based on language modeling approach in order to integrate the two contextual factors.

For instance, if a user submits the query "apple" into a Web search engine, knowing that user queries are generally shorts and contain words with several meanings, there are different topics in the top 20 documents selected by the search engine. Some users may be interested in documents dealing with "apple" as "fruit", while other users may want documents related to Apple computers. In order to disambiguate this query, we can assign a set of topics with this query. For example, we can assign the topics "cooking", "fruit" or "computer " with the query "apple". This is the user's domain of interest. In addition, to extend the query "apple" with the so-called query context, we can add concepts to this query like: "Computers", "Systems", "Macintosh", etc.

The language models in information retrieval (IR) are used to compute the probability of generating query q given a document D (i.e. compute: P (q|D)); and the documents in the collection C are ranked in descending order of this probability. Several methods have been applied to compute this probability as [START_REF] Lafferty | Language models, query models, and risk minimization for information retrieval[END_REF]. In most approaches, the computation is conceptually decomposed into two distinct steps: Estimating the document model and computing the query likelihood using the estimated document model, as in [START_REF] Liu | Statistical language modeling for information retrieval[END_REF].

In this paper, we propose an approach to build a statistical language model that extends the classic language modeling approach for information retrieval in order to integrate the two contextual factors. The extended model has been tested based on one of the common IR test collections; 20 Newsgroup corpus. The results show that our contextual approach improves significantly the retrieval effectiveness compared to the basic approach, which does not consider contextual factors. The rest of this paper is organized as follows: Section 2 introduces the state of the art and some related works; Section 3 introduces our contextual information retrieval model based on language modeling; Section 4 shows the experimental study and the evaluation of our approach. Finally, Section 5 gives the conclusion and future work.

Related Works

Context in Information Retrieval

Several contextual factors can be considered in Information Retrieval (IR) area in order to improve the information retrieval systems. In this section we review some of studies in IR concerning the user context and query context, as long as we take them into consideration to extend the language modeling approach for IR [START_REF] Asfari | Personnalisation et Adaptation de L'accs L'information Contextuelle en utilisant un Assistant Intelligent[END_REF].

User context. The user context can be assimilated to all factors that can describe his/her intentions and perceptions of his/her surroundings [START_REF] Mylonas | Personalized information retrieval based on context and ontological knowledge[END_REF]. These factors may cover various aspects: physical, social, personal, professional, technical, task etc. Figure 1 shows these factors and examples for each one [START_REF] Kofod-Petersen | Using Activity Theory to Model Context Awareness[END_REF].

However, the problems to be addressed include how to represent the context, how to determine it at runtime, and how to use it to influence the activation of user preferences. It is very difficult to modeling all the contextual factors in one system, so the researchers often take into account some factors, as in [START_REF] Asfari | Personalized Access to Contextual Information by using an Assistant for Query Reformulation[END_REF], they defined the user context as the user's current task together with his/her profile. In the contextual information retrieval, user context has a wide meaning based on the user behavior; we can mention some of them in the following:

-Visited Web pages [START_REF] Sugiyama | Adaptive Web Search Based on User Profile Constructed without Any Effort from Users[END_REF]: Here, the user context is defined as the information extracted by using the full browsing history of the user. -Recently accessed documents [START_REF] Bauer | Real time user context modeling for information retrieval agents[END_REF]: In this case, the user context is defined as words which indicate a shift in context; these words are identified by information about the sequence of accessed documents. This is carried out by monitoring a user's document access, generating a representation of the user's task context, indexing the consulted resources, and by presenting recommendations for other resources that were consulted in similar prior contexts.

-Past queries and click-through data [START_REF] Shen | Context-sensitive information retrieval using implicit feedback[END_REF]: Several context-sensitive retrieval algorithms are proposed based on statistical language models to combine the preceding queries and clicked document summaries with the current query for better ranking of documents. -Recent selected items or purchases on proactive information systems [START_REF] Billsus | Improving proactive information systems[END_REF].

-Information that is previously processed or accessed by the user via various forms: email, web page, desktop document, etc. Stuff I've Seen SIS, [START_REF] Dumais | Stuff I've Seen) : A system for personal information retrieval and re-use[END_REF]. -Implicit feedback: Implicit feedback techniques often rely on monitoring the user interaction with the retrieval system, and extract the apparently most representative information related to what the user is aiming at [START_REF] Kelly | Implicit Feedback for Inferring User Preference: A Bibliography[END_REF]. Query Context. The notion of query context has been widely mentioned in many studies of information retrieval like [4][9]. The objective is to use a variety of knowledge involving query to explore the most exact understanding of user's information needs. A query context will minimize the distance between the information need, I, and the query q, [START_REF] Asfari | A Context-Based Model for Web Query Reformulation[END_REF]. Distance (I to q) is minimized by minimizing:

-The lack of precision in the language used in the query terms. Lexicons which comprise the general vocabulary of a language can minimize this lack of precision in the language by identifying terms with minimal ambiguity. -The use of the wrong concepts in the query to represent the information needs. Prior research suggests Ontology's for doing that. -The lack of preferences in the query to constrain the concepts requested.

This lack can be minimized by using user profiles.

The query context, in other studies, is defined as the elements that surround the query, such as:

-Text surrounding a query, Text highlighted by a user [START_REF] Finkelstein | Placing search in context: the concept revisited[END_REF].

-Surrounding elements in an XML retrieval application [START_REF] Hlaoua | Towards Contextual and Structural Relevance Feedback in XML Retrieval[END_REF] [START_REF] Sauvagnat | Answering content and structurebased queries on XML documents using relevance propagation[END_REF].

-Broadcast news text for query-less systems [START_REF] Henzinger | Query-free news search[END_REF].

[10] exploit the query context for predicting the user intent as being informational related to the content retrieval, navigational related to the web site retrieval or transactional related to the online service retrieval. They construct the query context by associating it with ontology concepts from the ODP (Open Directory Project) taxonomy.

Statistical Language models

A statistical language model is a probability distribution over word sequences, using language models for information retrieval has been studied extensively, like in [START_REF] Lafferty | Language models, query models, and risk minimization for information retrieval[END_REF][21] [START_REF] Zhai | Model-based feedback in the language modeling approach to information retrieval[END_REF], because of its solid theoretical background as well as its good empirical performance. The main idea of language models in IR is to order each document D in the collection C according to their ability to generate the query q. Thus, it is the estimation of the generation probability P (q|D); Probability of a query q given a document D. Several different methods have been applied to compute this conditional probability, such as the works of [START_REF] Liu | Statistical language modeling for information retrieval[END_REF][8].

Discussion

User query is an element that specifies an information need, but the majorities of these queries are short and ambiguous, and often fail to represent the information need. Many relevant terms can be absent from queries and terms included may be ambiguous, thus, queries must be processed to address more of the user's intended requirements [START_REF] Asfari | Personalized Access to Contextual Information by using an Assistant for Query Reformulation[END_REF]. Typical solution includes expanding the initial user query by adding relevant terms. In this study we will expand the query representation by the query context which is defined above.

As we mentioned previously, it is difficult to consider all the available contextual factors. Thus, in this study, our definition of the user context is the user's interesting topic. Consequently, when we talk about the user context we talk about the user's interesting topics and taking into consideration the query context.

The language models for information retrieval have some limitations to capture the underlying semantics in a document due to their inability to handle the long distance dependencies. Also queries are typically too short to provide enough contexts to precisely translate into a different language. Thus, many irrelevant documents will be returned by using the standard language model approach for IR without integrating contextual factors.

In this paper, we will integrate the above two types of context within one framework based on language modeling. Each component contextual factor will determines a different ranking score, and the final document ranking combines all of them. This will be described in Section 3.

Contextual Information Retrieval Model Based on Language Modeling

In this section, we present our approach to construct a statistical language model given user's interested topics, user context, and considering the query expansion by using the linguistic and semantic processing.

Language models for IR

Let us consider a query q = t 1 t 2 ...t n , the generation probability is estimated as follows:

P (q | D) = t∈q P (t | θ D ) c(t;q) = P (t 1 | θ D )P (t 2 | θ D )...P (t n | θ D ) (1)
where: c(t; q) Frequency of term t in query q. θ D is a language model created for a document D. P (t | θ D ): The probability of term t in the document model. In order to avoid zero probability by assigning a low probability to query terms ti which are not observed in the documents of corpus, smoothing on document model is needed. The smoothing in IR is generally done by combining documents with the corpus [START_REF] Zhai | Model-based feedback in the language modeling approach to information retrieval[END_REF], thus:

P (t i | θ D ) = λP (t i | θ D ) + (1 -λ)P (t i | θ C ) (2)
where: λ is an interpolation parameter and θ C the collection model. In the language modeling framework the similarity between a document D and a query q (a typical score function) can be also defined by measuring the Kullback-Leibler (KL-divergence) [START_REF] Lafferty | Language models, query models, and risk minimization for information retrieval[END_REF] as follows:

Score(q, D) = -KL(θ q θ D ) = t∈V P (t | θ q ) log P (t | θ D ) P (t | θ q ) = t∈V P (t | θ q ) log P (t | θ D ) - t∈V P (t | θ q ) log P (t | θ q ) ∝ t∈V P (t | θ q ) log P (t | θ D ) (3)
Where: θ q is a language model for the query q, generally estimated by relative frequency of keywords in the query, and V the vocabulary. In the basic language modeling approaches, the query model is estimated by Maximum Likelihood Estimation (MLE) without any smoothing [START_REF] Bouchard | Modles de langue appliqus la recherche d'information contextuelle[END_REF]. P (t | θ q ): The probability of term t in the query model. Note that the last simplification is done because P (t | θ q ) log P (t | θ D ) depends only on the query, and does not affect the documents ranking.

General IR Model

The classic information retrieval systems (Non-context model) generate query directly based on similarity function or matching between the query and the documents, according to a few terms in the query. In fact, query is always formulated in a search context; contextual factors have a strong influence on relevance judgments. To improve retrieval effectiveness, it is important to create a more complete query model that represents better the information need. In particular, all the related and presumed terms should be included in the query model. In these cases, we construct the initial query model containing only the original terms, and a new contextual model containing the added terms. We generalize this approach and integrate more models for the query.

Let us use θ 0 q to denote the original query model, θ s q to denote the query context model and θ u q to denote the user context model. θ 0 q can be created by MLE (Maximum Likelihood Estimation), as in [START_REF] Bai | Using Query Contexts in Information Retrieval[END_REF]. We will describe the details to construct θ s q and θ u q in the following sections.

Given these models, we create the following final query model by interpolation:

P (t | θ q ) = i∈X a i P (t | θ i q ) (4)
where: X = {0, u, s} is the set of all component models. a i (With i∈X a i = 1) are their mixture weights.

Thus formula (3) becomes:

Score(q, D) = t∈V i∈X a i P (t | θ i q ) log P (t | θ D ) = i∈X a i Score i (q, D) (5)
Where the score according to each component model is:

Score i (q, D) = t∈V P (t | θ i q ) log P (t | θ D ) (6)
Like that, the query model is enhanced by contextual factors. Now we have to construct both query context model and user context model and combine all models. We will describe that in the following sections.

Constructing query context model

We will use both a linguistic knowledge and a semantic knowledge to parse the user query. Because linguistic knowledge does not capture the semantic relationships between terms and semantic knowledge does not represent linguistic relationships of the terms [START_REF] Asfari | A Context-Based Model for Web Query Reformulation[END_REF]. We use WordNet as the base of a linguistic knowledge. For the semantic knowledge we depend on ODP1 (Open Directory Project) Taxonomy, it is one type of ontology.

The integration of linguistic and semantic knowledge about the user query into one repository will produce the query context which can help to understand the user query more accurately.

Thus the initial query q = t 1 t 2 ...t n is parsed using WordNet in order to identify the synonymous for each query term {t w1 , t w2 , ..., t wk }.

The query and its synonyms q w are queried against the ODP taxonomy in order to extract a set of concepts {c 1 c 2 ...c n } (with m ≥ n) that reflect the semantic knowledge of the user query. The concepts of the terms set q w and their sub-concepts produce the query-context C q = {c 1 c 2 ...c n } . Thus the elements of C q are the concepts extracted from the ODP taxonomy by querying the initial query and its synonyms against it. For each term t, we select the concepts of only first five categories issued from ODP taxonomy.

Among the concepts of query context C q , We consider only the shared concepts between at least two query terms, that means, a concept C i ∈ C q the context of the query q if one of the following holds:

-C i and t ∈ q are the same, i.e. a direct relation.

-C i is a common concept between the concepts of at least two query terms or their synonymous.

For instance, if a user query is "Java Language", the query context C q , in this case, will be: < computers, programming, languages, Java, JavaScript >. Thus, the corresponding query context model θ s q is then defined as follows:

P (t | θ s q ) = Ci∈Cq p(t | C i )p(C i | θ 0 q ) (7)
Accordingly, the score according to the query context model is defined as follows:

Score s (q, D)

= t∈V P (t | θ s q ) log P (t | θ D ) (8)

Constructing user context model

As we previously mentioned, in this paper, the user context is defined as the user's domain of interest or the interesting topic. We will depend on predefined topics, which are derived from the used corpus. To define these topics, we can use our thematic algorithm, which will be discussed in the following (see Fig. 2).

We suppose that the user can select his own topic from these predefined topics by assigning one topic to his query.

We exploit a set of documents already classified in each topic. The documents of each topic can be identified using same thematic algorithm. Thus a language model, for each topic, can be extracted from the documents of this topic. To extract only the specific part of the topic and avoid the general terms in the topic language model, we apply our thematic algorithm as follows (see Fig. 2).

A thematic unit refers to a fragment of a document D referring to one topic. The steps are based on a thesaurus that includes all lexical indicators which are considered important for this segmentation process. They are created, in this study, manually but to extend the thematic units coverage in a document, we added synonyms and lexical forms that may have these units in the corpus.

The obtained text fragments are then grouped by the thematic unity. Seeking information related to the user context (term context) will be done from these fragments.

Fig. 2. A thematic algorithm

Next maximum likelihood estimation is used on the documents of each topic to extract the topic language model.

We suppose that we have the following predefined topics: T C 1 , T C 2 , ..., T C j , and the user assign the topic T C j to his query. We can extract the user context language model which is extracted from the documents of the topic T C j , as follows (considering the smoothing):

θ u = arg max D∈T Cj t∈D µP t | θ T Cj + (1 -µ) P (t | θ C ) c(t;D) (9)
Where: c(t; D) is the occurrence of the term t in document D.µ is a smoothing parameter. µ is fixed to 0.5 in the experimentation, because, in our dataset, we have considered the middle point as a smoothing parameter. T C j is the set of documents in the topic j. In the same method we can compute the set of user context models for all predefined topics. When the user assigns one topic to his query q manually, the related user context model θ s q has to be assigned to this query q, and the score depending on this user context model (represented by the related topic) will be:

Score u (q, D) = t∈V P (t | θ u q ) log P (t | θ D ) (10)

Experiments

To validate our approach, we will present an experimental study which is done by using a test collection, 20 Newsgroups2 corpus. The objective of this experimental study is to compare the results provided by using an information retrieval model on the dataset without considering the contextual factors with those provided by a general information retrieval model considering the contextual factors.

Our approach (including steps) is implemented in Java by using Eclipse environment. The prototype use JWNL3 (Java WordNet Library), which is an API that allows the access to the thesaurus WordNet to find synonyms of query terms. For the semantic knowledge we depend on ODP Taxonomy which is free and open, everybody can contribute or re-use the dataset, which is available in RDF (structure and content are available separately), i.e., it can be re-used in other directory services. Also we used the Oracle RDBMS database to host: (1) the thesaurus for terms synonyms, (2) the topics which are generated during the process of identification and extraction, and (3) the relevance scores of returned documents. In order to facilitate the evaluation, we developed an interface that helps users to enter their queries, to compute the evaluation criteria, and then to display the results which are ranked according to the degrees of relevance.

Newsgroup Data Sets

The 20 Newsgroup data set is a common benchmark collection of approximately 20,000 newsgroup documents, partitioned nearly evenly across 20 different newsgroups. This dataset was introduced by [START_REF] Lang | NewsWeeder: learning to filter net news[END_REF]. It has become a popular data set for experiments in text applications of machine learning techniques, such as text classification. Over a period of time, 1000 articles were taken from each of the newsgroups, which make this collection. The 20 topics are organized into broader categories: computers, recreation, religion, science, for-sale and politics. Some of the newsgroups are considered to have similar topics, such as the rec.sport.baseball and rec.sport.hockey which both contain messages about sports, while others are highly unrelated (e.g misc.forsale/ soc.religion.christian) newsgroups. Table 1 shows the list of the 20 newsgroups, partitioned (more or less) according to subject matter. This dataset is also used by [START_REF] Ratinov | Conceptual search and text categorization[END_REF].

Moreover, we preprocessed the data by removing stop words and all documents are stemmed using the Porter algorithm. The document-terms matrix is based on language models and each document is represented as a vector of occurrence numbers of the terms within it. The results of this preprocessing phase for the dataset before and after the classification topics are presented in Table2.

The query execution phase, in our approach, returns a ranked list of documents that match the query. The experimentation on the 20 Newsgroups collection doesn't provide the ability to compute the precision and recall metrics. In this way our experiments were conducted with the Lemur Toolkit4 , which is a standard platform to conduct experiments in information retrieval. The toolkit has been used to carry out experiments on several different aspects of language modeling for ad-hoc retrieval. For example, it has been used to compare smoothing strategies for document models, and query expansion methods to estimate query models on standard TREC5 collections. We used the language models for all our retrieval tasks. All the other parameters were set at their default values. We remove all UseNet headers from the Newsgroup articles and we used 20 queries, which are listed in Table 3, to retrieve results from this documents dataset. The queries vary from 1 term to 7 terms.

Baseline

Classic IR Baseline. As a baseline for comparison, for each dataset, we created an index of all the documents using Lemur's indexer. Figure 3 shows the indexation interface. Also we used Lemur's retrieval engine to return a list of relevant documents using the queries which are described above. This is the standard information retrieval setting. For instance, Figure 4 shows the document's ranking for the query "athletics play". Contextual information retrieval Baseline. We expanded the query with both user context and query context. In the 20 Newsgroup dataset, the topics names are considered as a user context. The documents are indexed with Lemur's indexer. Lemur's retrieval engine was used to perform information retrieval using the expanded query.

Results

To evaluate the performance of our approach we use the TREC evaluation software to calculate the metrics. We use ireval.pl Perl script which comes with the Lemur toolkit distribution for interpreting the results of the program trec eval. Figure 5 illustrates the precision/recall curves of the IR classic and of our contextual retrieval model on the 20 Newsgroup dataset. The results of our approach, presented by the curves, show significantly improvement in measure of Precision/Recall compared to the classical model. The improvement is precisely in the accuracy rate. It is obtained by using the contextual model which expands the original query model and re-rank the returned documents. Search engines involve query expansion to increase the quality of user search results. It is assumed that users do not always formulate their queries using the best terms. Using the general model which expands the user query with the contextual factors will increase the recall at the expense of the precision. This explains our motivation to consider the contextual factors and topic units in our approach.

Conclusion

In order to improve the information retrieval, we considered, in this paper, two types of context, user context and query context. We proposed an approach based on query expansion to provide a more efficient retrieval process. The initial query, the user context and the query context are integrated to create a new query. A thematic algorithm is proposed to describe the user context and both linguistic knowledge (WordNet) and semantic knowledge (ODP taxonomy) are used to represent the query context. The two contextual factors are integrated in one framework based on language modeling. We proposed a new language modeling approach for information retrieval that extends the existing language modeling approach to build a language model in which various terms relationships can be integrated. The integrated model has been tested on the 20 Newsgroup corpus. The results show that our contextual approach improves the retrieval effectiveness compared to the basic approach, which does not consider contextual factors. In the future, we plan to consider more contextual factors. The future objective is to combine our approach with the On-line Analytical Processing (OLAP) systems.

Fig. 1 .

 1 Fig. 1. Context Model.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Lemur's indexer

Fig. 5 .

 5 Fig. 5. Precision/recall curves for 20 Newsgroup corpus

Table 1 .

 1 A list of the 20 Topics

		20 Newsgroups dataset
	comp.graphics	rec.autos	talk.politics.misc soc.religion.christia
	comp.os.ms-windows.misc rec.motorcycles talk.politics.guns	sci.crypt
	comp.sys.ibm.pc.hardware rec.sport.baseball talk.politics.mideast	sci.electronics
	comp.sys.mac.hardware rec.sport.hockey talk.religion.misc	sci.med
	comp.windows.x	misc.forsale	alt.atheism	sci.space

Table 2 .

 2 Pre-processing phase applied on the dataset

	Corpus	docs stems Corpus	docs stems
	20 news group	20017 192375 ec.sport.baseball	1001 14000
	alt.atheism	1001 15618 rec.sport.hockey	1001 15610
	ccomp.graphics	1001 17731 sci.crypt	1001 17436
	comp.os.ms-windows.misc	1001 54511 sci.electronics	1001 15622
	comp.sys.ibm.pc.hardware 1001 16575 sci.med	1001 19963
	comp.sys.mac.hardware	1001 15011 sci.space	1001 18432
	comp.windows.x	1001 24915 soc.religion.christian	1001 13915
	misc.forsale	1001 17518 talk.politics.guns	1001 20258
	rec.autos	1001 15415 talk.politics.mideast	1001 20546
	rec.motorcycles	1001 15108 talk.politics.misc	1001 17782

Table 3 .

 3 The experimented queries list

	N Query	N Query
	1 Sport	11 Logitech Bus Mouse adapter
	2 athletics play	12 Division Champions
	3 Stanley Cup Champion: Vancouver Canucks 13 baseball fan
	4 ordinary ISA card	14 HD drive
	5 East Timor	15 System requirement
	6 High speed analog-digital pc-board	16 memory controller pc
	7 Chicago Blackhawks	17 league teams
	8 Kevin Dineen play for the Miami Colons	18 macintosh apple hardware
	9 National league pitchers	19 science cryptography
	10 good defensive catcher	20 society religion

ODP: Open Directory Project: www.dmoz.org

http://people.csail.mit.edu/jrennie/20Newsgroups/

http://jwordnet.sourceforge.net/handbook.html

http://www.lemurproject.com

http://trec.nist.gov/

R. Aknouche, O. Asfari, F. Bentayeb, and O. Boussaid