Lingbo Kong

Rémi Gilleron
email: remi.gilleron@univ-lille3.fr

Aurélien Lemay Mostrare
email: aurelien.lemay@univ-lille3.fr

Retrieving Meaningful Relaxed Tightest Fragments for XML Keyword Search *

Adapting keyword search to XML data has been attractive recently, generalized as XML keyword search (XKS). One of its key tasks is to return the meaningful fragments as the result. [1] is the latest work following this trend, and it focuses on returning the fragments rooted at SLCA (Smallest LCA -Lowest Common Ancestor) nodes. To guarantee that the fragments only contain interesting nodes, [1] proposes a contributor-based filtering mechanism in its MaxMatch algorithm. However, the filtering mechanism is not sufficient. It will commit the false positive problem (discarding interesting nodes) and the redundancy problem (keeping uninteresting nodes).

In this paper, our interest is to propose a framework of retrieving meaningful fragments rooted at not only the SLCA nodes, but all LCA nodes. We begin by introducing the concept of Relaxed Tightest Fragment (RTF) as the basic result type. Then we propose a new filtering mechanism to overcome those two problems in Max-Match. Its kernel is the concept of valid contributor, which helps to distinguish the interesting children of a node. The new filtering mechanism is then to prune the nodes in a RTF which are not valid contributors to their parents. Based on the valid contributor concept, our ValidRTF algorithm not only overcomes those two problems in MaxMatch, but also satisfies the axiomatic properties deduced in [1] that an XKS technique should satisfy. We compare ValidRTF with MaxMatch on real and synthetic XML data. The result verifies our claims, and shows the effectiveness of our validcontributor-based filtering mechanism.

INTRODUCTION

XML is rapidly emerging as the de facto standard for data representation and exchange of Web applications, such as Digital Library, Web service, and Electronic business. An XML data is usually modeled as an XML tree T = (r, V, E, Σ, λ), where V is the node set, r is a special node in V as the root, and E is the edge set. For each node v ∈ V , λ is the function to assign a "label" l in the string set Σ to v, that is λ : v ∈ V → l ∈ Σ. There are two kinds of nodes in V according to the fact whether the node contains "value" or not. Figure 1(a) is an XML instance, in which every node has a node name (label), and every leaf node also contains the value (text) 1 . The integer sequence beside each node is the Dewey code [2], such as "0.2.0.1". For an XML tree T , the content C v of a node v is the word set implied in v's label, text and attributes. Given a keyword query Q ={w 1 , . . ., w k }, the node v is a keyword node if Cv ∩ Q = ∅ where ∅ is the empty set.

With the widespread use of XML, adapting keyword search to XML data has become attractive, generalized as XML keyword search (XKS), because keyword search provides a simple and user-friendly query interface to access XML data in web and scientific applications. As a result, XKS has recently attracted more and more research interests [START_REF] Florescu | Integrating keyword search into xml query processing[END_REF]4,5,[START_REF] Li | Schema-free xquery[END_REF]7,[START_REF] Hristidis | Keyword proximity search in xml trees[END_REF][START_REF] Sun | Multiway slca-based keyword search in xml data[END_REF][START_REF] Liu | Identifying meaningful return information for xml keyword search[END_REF][START_REF] Li | Effective keyword search for valuable lcas over xml documents[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]. Its basic task is to return meaningful fragments, each of which contains all the interesting keywords.

Based on the LCA concept from graph theory [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF][START_REF] Schieber | On finding lowest common ancestors: simplification and parallelization[END_REF]15,16], the popular solution for this task is to first locate the LCA nodes (including the popular SLCA nodes), and then retrieve the fragments rooted at those LCA nodes. The semantics of LCA here is to return the special nodes in the given XML tree T . The subtrees rooted at those special nodes contain all the keywords in the keyword query Q = {w 1 , . . . , w k } after excluding the LCA nodes and their keyword nodes which are descendants of those special nodes (refer to [4] for more details). As for the SLCA nodes, they are part of those LCA nodes, however, they have no descendant node which also contains all keywords (refer to [7] for more details). Following the above consideration, the fragment related to a SLCA node u can be described as the SLCA-based fragment, which consists of all the keyword nodes v1, . . . , vm of the query Q, and all the nodes on every path from u to v i (1 ≤ i ≤ m). However, there is at least one explicit weakness for the above methods, that is, the nodes in a fragment corresponding to a LCA node may not be all interesting. We use Example 1 to illustrate this.

Example 1 (Illustration for LCA related concepts) The illustration is based on two XML instances in Figure 1(a) and Figure 1(b):(1) (derived from [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]). Figure 1(b):(2) presents several keyword queries. We first demonstrate the concepts of LCA and SLCA. Then we illustrate the deficiency of returning only the LCA nodes as result. [SLCA v.s LCA] When running Q 2 on Figure 1(a), the SLCA node is "0.2.0.3.0 (ref)"2 according to [7]. Figure 2(a) illustrates the SLCA-based fragment (similar with the match concept in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]) corresponding to the node "0.2.0.3.0 (ref)".

According to [4,[START_REF] Li | Effective keyword search for valuable lcas over xml documents[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF], the LCA node "0.2.0 (article)" is also interesting for Q 2 , because its related fragment shown in Figure 2(b) also contains all the keywords in Q 2 . However, this LCA node is discarded by the SLCA concept because it is an ancestor of the SLCA node "0.2.0.2.0 (ref)".

The query result proposed by [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] has the same semantics as the SLCA-based fragment here, which is only applicable to the SLCA related fragments. It is not applicable to the more general LCA related fragments.

[Returning only LCA/SLCA nodes] When running Q 3 on Figure 1(a), the only LCA node (also the SLCA node) is the root of the XML data -"0 (Publications)". It is clear that returning the whole subtree rooted at "0 (Publications)" is redundant. Sometimes, it is redundant too even we only return the LCA node and the related nodes. Figure 2(c) demonstrates the fragment rooted at the LCA node "0 (Publications)" for Q3. We can see that the keyword node "0.2.1.1 (title)" is not interesting to the keyword query Q 3 , because it is not about the research on XML keyword search.

Different from the above work, several methods [5,[START_REF] Hristidis | Keyword proximity search in xml trees[END_REF][START_REF] Liu | Identifying meaningful return information for xml keyword search[END_REF][START_REF] Li | Effective keyword search for valuable lcas over xml documents[END_REF][START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] are proposed recently to return the meaningful fragments with in-teresting nodes, instead of only the LCA/SLCA nodes. And how to prune the redundant nodes in the fragments becomes a challenge for XKS. Among those proposals, [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] deserves attention, because it not only deduces the properties that an XKS technique should satisfy, but also proposes a concrete algorithm following those properties. The intuitive and non-trivial axiomatic properties are (1) data monotonicity: if a new node is added to the data, the number of query results should be (non-strictly) monotonically increasing; (2) query monotonicity: if a keyword is added to the keyword query, the number of query results should be (non-strictly) monotonically decreasing; (3) data consistency: after a data insertion, each additional subtree which becomes (part of) a query result should contain the newly inserted node; (4) query consistency: if a new keyword is added to the query, each additional subtree which becomes (part of) a query result should contain at least one match to this keyword.

After the axiomatic work, [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] further proposes the MaxMatch algorithm, which satisfies all those properties, and returns the filtered fragments rooted at the SLCA nodes after pruning the uninteresting nodes. Its kernel is the filtering mechanism based on the concept of contributor, which helps to filter the nodes in each SLCA-based fragment. The contributor filtering mechanism requires that every node n in the SLCA-based fragment should satisfy the following condition: n does not have a sibling n2 satisfying dM atch(n) ⊂ dM atch(n 2 ), where the function dM atch(n) represents all the keywords contained in the subtree rooted at the node n.

Even though the contributor-based MaxMatch satisfies all those four properties, however, it has the false positive problem which When using contributor concept to filter the nodes in Figure 3(b), it is clear that the node "0.2.1.1 (title") is a sibling of the node "0.2.1.2 (abstract)", and its keyword set {Skyline, Query} is covered by the latter's keyword set {Dynamic, Skyline, Query}.

Consequently the keyword node "0.2.1.1 (title)" is discarded, since it is not a contributor to Q 1 . So the final result of Q 1 on the XML instance of Figure 1(a) is the fragment shown in Figure 3(c).
However, intuitively, the keyword node "0.2.1.1 (title)" and its value "Efficient Skyline Querying with Variable User Preferences on Nominal Attributes" should not be discarded, because it is the "title" of the corresponding paper.

[Redundancy problem] Here we directly borrow the XML instance used in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], shown in Figure 1(b): [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]. The keyword query is "Grizzlies position" (Q4 in Figure 1(b):(2)), which is used to collect all the positions in the team "Grizzlies". Now the dM atchs of the three nodes "0.1.0", "0.1.1" and "0.1.2" are the same as {posi-tion}. Consequently the fragment retrieved by MaxMatch based on contributor contains all the position nodes, even the values of some of them are same. The fragment is shown in Figure 3(d). We can see that there are two position nodes which have the same value -"forward".

From Example 2 we can see that the contributor-based filtering mechanism is not sufficient to filter out all the uninteresting nodes in a SLCA-based fragment. Besides, only focusing on the SLCA related fragments is not enough for XKS either. The papers [4,[START_REF] Xu | Effective keyword search in xml documents based on miu[END_REF][START_REF] Hristidis | Keyword proximity search in xml trees[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Li | Effective keyword search for valuable lcas over xml documents[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF] confirm that the LCA nodes other than the SLCA nodes are also significant to XKS. Thus, our interest in this paper is to improve the filtering mechanism in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], and then to extend the work to all the interesting LCA-based fragments, not just the SLCA-based fragments. The first task in this paper is to formalize the description of the basic interesting fragments for the given keyword query. We propose the Relaxed Tightest Fragment (RTF) concept to represent the basic result for the XML keyword search, which considers the interesting LCA node and all its related keyword nodes together. Then we propose a new filtering mechanism in order to overcome the false positive problem and the redundancy problem in the contributorbased filtering mechanism in MaxMatch. The kernel of our filtering mechanism is the concept of valid contributor, which filters the children of a node by taking into account not only the children's labels but also their contents. The contributions of this paper can be concluded as follows:

• We propose the Relaxed Tightest Fragment (RTF) concept to represent the basic result for the XML keyword search. A RFT in an XML data for the given keyword query encloses the basic interesting information with respect to the query.

• We propose the concept of valid contributor to filter the nodes in a RTF so as to overcome the false positive problem and the redundancy problem in contributor concept. By taking into account the label and the content of a node, the children of a node could be classified as valid contributors and non-contributors. The filtering mechanism is to make sure that all the nodes in the RTF are valid contributors to their parents. After the filtering, we get a more concise and reasonable RTF.

• We implement the valid-contributor-based filtering mechanism in ValidRTF, and compare it with MaxMatch on both real and synthetic datasets. The results verify the efficiency and effectiveness of our proposal.

The rest of this paper is organized as follows. Section 2 presents the formal description of the RTF. The idea of our valid contributor is discussed in Section 3. Section 4 illustrates the ValidRTF algorithm, which returns the meaningful RTFs for the given keyword query after filtering the nodes based on the valid contributor concept. Section 5 illustrates the experimental result. Section 6 briefly reviews the related work of XML keyword search. Section 7 is the conclusion.

RELAXED TIGHTEST FRAGMENT

In this section, we introduce the concept of Relaxed Tightest Fragment (RTF), which is used in this paper as the basic result type for XKS. It is also based on the LCA concept, but a RTF can also determine all the related nodes (no more and no less) in the XML data.

Following the examples in Section 1, we can learn that the essence behind retrieving the fragments for the given keyword query is a partitioning mechanism of the keyword nodes with the help of LCA concept, so that each partition satisfies the following conditions.

(1) each partition covers all the keywords; (2) the LCA node of a partition is unique among the LCA nodes of all the partitions;

(3) the intersection of any two partitions is empty; (4) if there is a subset of a partition that also covers the query, its LCA node should be the same as that of the whole partition; (5) any keyword node in a partition with LCA node a can not compose a partition with any other keyword nodes so that the new LCA node of the new partition is lower than a in the XML tree; (6) there is no other keyword node outside a partition p so that the LCA node of the combination of p and that node is the same as the LCA node of p.

For example, the fragments in Figure 2(a), 2(b), 2(c), 3(b) and 3(d) are ideal basic results for corresponding keyword queries, each of which contains all the interesting nodes related to the corresponding keyword query. They all satisfy the above six requirements. As for Figure 2(d), it is not an ideal basic result for Q 3 according to [START_REF] Li | Schema-free xquery[END_REF]. The reason is that after integrating the outside node "0. The above conditions can be categorized into three kinds of requirements for the basic result of XKS: the keyword requirement [(1)], the uniqueness requirement [(2), (3)] and the completeness requirement [(4), ( 5), [START_REF] Li | Schema-free xquery[END_REF]]. It is straightforward to understand the first two requirements. As for the third, it requires that a valid partition should contain all the related keyword nodes, no more and no less. However, it is not convenient to express them in words.

It is necessary to formalize them in a more precise manner. This is the motivation of our RTF here. Our first step is to enumerate all the partitions of the keyword nodes, each of which contains all the given keywords. This is the concept of extended keyword node combination set (EC T Q ) in Definition 1. Then we confine them by adding additional conditions to get the RTF concept which satisfies the above requirements. The RTF concept is shown in Definition 2.

Definition 1 (Extended Keyword Node Combination Set) Given an XML tree T , and the keyword query Q = {w 1 , . . ., w k }, D i records all the keyword nodes with respect to the keyword w i . The set V i contains all the valid keyword node subsets of D i , which means Vi = 2 D i -{∅}, where 2 D i is the power set of Di, and ∅ is the empty set.

The extended keyword node combination set EC

T Q on all D i (1 ≤ i ≤ k) is defined as {V |V = k i=1 v i where v i ∈ V i }. Without loss generality, EC T Q,j represents an element of EC T Q , where 1 ≤ j ≤ k i=1 2 |D i | -1 if k i=1 D i = ∅. EC T Q,j | i is the keyword node set in EC T Q,j corresponding to the keyword w i .
The basic idea of EC T Q is to enumerate all the partitions of the corresponding keyword node sets. Each partition EC T Q,j naturally satisfies the keyword requirement, namely

C EC T Q,j ∩ Q = Q where C EC T Q,j = v∈EC T Q,j
Cv. Besides, the definition of EC T Q also covers the situation that many keyword nodes containing the same keyword occur in some EC T Q,j . This property provides a platform for the later RTF concept that we can filter EC T Q so that the related nodes with respect to a LCA node can be retrieved totally. Example 3 expresses these properties.

Example 3 (Illustration of EC

T Q )
We run the keyword query Q = "Liu Keyword" on the XML data in Figure 1(a). We take "Liu" as w1, and "keyword" as w2. The keyword node set corresponding to w 1 is D 1 = {"name (0.2.0.0.0.0)", "ref (0.2.0.3.0)"}; while D 2 = {"title (0.2.0.1)", "ref (0.2.0.3.0)", "abstract (0.2.0.2)"} is the keyword node set for w 2 . We use "r" to stand for the node "ref (0.2.0.3.0)", "n" for "name (0.2.0.0.0.0)", "a" for "abstract (0.2.0.2)", and "t" for "title (0.2.0.1)" respectively, so as to keep the following descriptions simple.

To achieve EC T Q , we should first compute the valid keyword node subsets from D 1 and D 2 . Following Definition 1, they are V 1 = {{n}, {r}, {n, r}}; while V2 = {{t}, {r}, {a}, {t, r}, {t, a}, {r, a}, {t, r, a} } respectively.

Based on V 1 and V 2 , we can get the EC T Q as {{r}, {n, t}, {n, r}, {n, a}, {r, a}, {r, t}, {n, t, r}, {n, t, a}, {r, t, a}, {n, r, a}, {n, t, r, a}}. The number of subsets is 11

(not (2 2 -1) × (2 3 -1) = 21), because D1 D2 = {r} = ∅.
From Example 3 it is clear that each partition in EC T Q naturally contains all the given keywords in Q. Now the next task is to filter the partitions in EC T Q so that the residual partitions satisfy the other two requirements -the uniqueness requirement and the completeness requirement, that is the LCA nodes of the residual partitions are the same as those LCA nodes computed according to [4,[START_REF] Xu | Efficient lca based keyword search in xml data[END_REF], and each partition contains all the related keyword nodes. We present the RTF concept in Definition 2 for this task, which provides the rules to filter EC T Q .

Definition 2 (Relaxed Tightest Fragment) Given an XML tree T , and the keyword query Q = {w 1 , . . ., w k }, D i records all the keyword nodes with respect to the keyword wi, Vi is the set of the valid keyword node subsets of Di, and

EC T Q is the extended keyword node combination set on all D i (1 ≤ i ≤ k). For each element EC T Q,j in EC T Q , LCA(EC T Q,j
) is the unique LCA node based on all the nodes in EC T Q,j , and I(EC T Q,j ) records all the nodes determined by the keyword node set EC T Q,j and its LCA node, which is defined as

I(EC T Q,j ) = I(LCA(EC T Q,j ), EC T Q,j ) = v∈EC T Q,j I(LCA(EC T Q,j ), v) 3 . Vj|i stands for the valid subsets of EC T Q,j | i , namely V j | i = 2 EC T Q,j | i -{∅}. The I(EC T Q,j ) is a RTF if the EC T Q,j and its LCA(EC T Q,j
) satisfy all the following three conditions:

• S i ∈ V j | i (1 ≤ i ≤ k), LCA EC T Q,j = LCA k i=1 S i . • ∀EC T Q,j | i ∈ EC T Q,j , V ∈ (V i -EC T Q,j | i ) ∧ EC T Q,j | i ⊂ V , LCA EC T Q,j = LCA EC T Q,j |1, . . . V . . . , EC T Q,j | k . • V ∈ V j | i , LCA(EC T Q,j ) ≺ a LCA(S 1 , . . . , V , . . . , S k ) where S i ∈ V i (1 ≤ i ≤ k),
and u ≺ a v represents that the node u is an ancestor of the node v in the XML tree.

The first rule is used to ensure that there is no other keyword node subset in EC T Q,j , which also covers the given keyword query, but whose LCA node is different from LCA(EC T Q,j ). The second rule is to make sure that the keyword node set

EC T Q,j is the maximum set in EC T Q whose LCA node is LCA(EC T Q,j
). These two rules guarantee that the RTFs satisfying them conform to the completeness requirement, because they imply that the RTF corresponding to a LCA node contains all the related keyword nodes, no more and no less. As for the third rule, it means that any keyword node in EC T Q,j can not be included in other keyword node set whose LCA node is a descendant of LCA(EC T Q,j ). This rule helps to ensure that the RTF is unique, because it implies that any keyword node should belong to a unique partition. Together with Definition 1, we can see that the RTFs determined by Definition 2 satisfy not only the keyword requirement but also the uniqueness and the completeness requirements. Besides, it is easy to further distinguish the SLCA-related RTFs. We use Example 4 to illustrate the concept of RTF.

Example 4 (Illustration of RTF concept) Following Example 3, there are only two keyword combination sets in EC T Q satisfying the RTF concept, {r} and {n, t, a}. All the other partitions do not satisfy all those three conditions.

For the partitions of {n, r}, {r, a}, {r, t}, {r, t, a}, {n, r, a} and {n, t, r, a}, they could not be RTFs because they conflict both the first and the third conditions. It is clear that their LCA nodes are all the node "0.2.0 (article)", and {r} is their common subset. Based on Figure 1(a) we can see that the node r "0.2.0.3.0 (ref)" itself contains all the keywords and is a LCA node. It is clear that it is a descendant of the node "0.2.0 (article)" -the common LCA node of those partitions.

As for the partitions of {n, t} and {n, a}, they are not RTFs either because they do not satisfy the second condition of Definition 2. From Figure 1(a) we can see that they both cover all the keywords and their LCA nodes are same -the node "0.2.0 (article)". When adding the node a to {n, t}, and the node t to {n, a}, the new partition is {n, t, a}, which also covers all the keyword nodes and whose LCA node is also the node "0.2.0 (article)". We can see that the RTF concept is applied uniformly across the SLCA and the LCA semantics, and it is easy to distinguish the SLCA related RTFs from the total RTFs for the given keyword query. All these properties guarantee that the RTF concept is appropriate to represent the basic result for XKS.

After retrieving the RTFs for the given keyword query, the next task is to prune the uninteresting nodes in a RTF so as to make sure that all the residual nodes are meaningful to the query. We denote the pruned RTF as meaningful RTF. For instance, we should find an appropriate filtering mechanism so as to get the meaningful RTF of Figure 2(d) from the raw RTF of Figure 2(c), keep the RTF of Figure 3(b) as the final RTF, and prune the duplicate forward "position" node in the RTF of Figure 3(d). From the discussion in Section 1 we have learnt that the contributor-based filtering mechanism could not be used for these RTFs of Figure 2(c), 3(b) and 3(d). In view of this, we further propose the concept of valid contributor to cope with this problem.

VALID CONTRIBUTOR FOR MEANING-FUL RTF

In this section, we introduce the concept of valid contributor. which can overcome the false positive problem and the redundancy problem of the contributor function in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF].

From Example 2 we learn that both the false positive problem and the redundancy problem are caused by the insufficient contributor function for MaxMatch algorithm in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]. The key to overcome the two problems is to ameliorate the filtering condition to cope with the following two questions: (1) how to keep interesting node n when dM atch(n) ⊂ dM atch(n 2 ), and (2) how to filter out the uninteresting node n when dM atch(n) = dM atch(n 2 ).

Fortunately, Example 2 also reminds us of some hints to cope with those problems, i.e., the label and the content information of the keyword node can help to overcome those problems. For instance in Figure 3(b) for the query Q 1 , the node "0.2.1.1" should not be discarded even though for Q 1 dM atch(0.2.1.1) = {query, sky-line} ⊂ dM atch(0.2.1.2) = {dynamic, query, skyline}, because its label "title" is different from the label "abstract" of the node "0.2.1.2". For Figure 3 The above observations remind us that, intuitively, the label and the content information of the keyword nodes can help to overcome the two problems. That is, if the label of a child is unique among its siblings, this child should not be discarded even though its dM atch is a subset of one of its siblings' dM atchs. And when two siblings have same label, if their values are same, one of them should be discarded even though their dM atchs are same. To formalize the above observations, we first present the concepts of tree content set and tree keyword set of a node in Definition 3, which collect the interesting words and the keywords contained in the subtree rooted at a node.

Definition 3 (Tree Content Set and Tree Keyword Set of a node)

Given an XML tree T , and the keyword query Q = {w1, . . ., w k }, R is a RTF in T , which contains all the keywords in Q. The tree content set T C v of a node v in R is the content union of all the keyword nodes rooted at the node v, that is

T C v = v ∈Tv C v , where
T v represents the subtree rooted at the node v, and v ∈ T v stands for a keyword node in T v . The tree keyword set of the node v is defined simply as

T C v ∩ Q, denoted as T K v 4 .
Based on Definition 3, we further present the concept of valid con-tributor in Definition 4, which helps to distinguish the valid contributors from the children of a node. Our filtering mechanism for a RTF then can be described as following: every node in a RTF (except for its root) should be a valid contributor to its parent.

Definition 4 (Valid Contributor) Given an XML tree T , and the keyword query Q = {w 1 , . . ., w k }, R is a RTF in T . u, v are two nodes in R, and u is the parent of v. The child v is a valid contributor of u if either of the following two conditions holds:

1. v is the unique child of u with label λ(v);

2. v has several siblings v 1 , . . . , v m (m ≥ 1) with same label as λ(v), but the following conditions hold:

(a) v i , T K v ⊂ T K v i ; (b) ∀v i ∧ T K v = T K v i , T C v = T C v i .
From Definition 4, the rule 1 aims to overcome the false positive problem. As for the rule 2, there are two subrules, in which 2. , we can see that the node "0.2.1 (article)" has three children -"0.2.1.0 (authors)", "0.2.1.1 (title)", "0.2.1.2 (abstract)".

Since their labels are different from each other, all of them are valid contributors to their parent "0.2.1 (article)". So all of them are kept in the final meaningful RTF, even though the tree keyword set {query, skyline} of the node "0.2.1.0 (authors)" is a subset of the tree keyword set {dynamic, query, skyline} of its sibling "0.2.1.2".

So, for Q 1 on the XML instance of [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], in which the MaxMatch will commit the redundancy problem. When using our valid contributor to filter those nodes, however, the final result will only contain one "forward" position node.

According to Definition 3, the tree keyword sets of the three nodes -"0.1.0 (player)", "0.1.1 (player)" and "0.1.2 (player)" are all {position}. While their tree content sets are T C0.1.0 = {position, forward}, T C 0.1.1 = {position, guard} and T C 0.1.2 = {position, forward} respectively. Since there are only two distinct valid contents -{position, forward} and {position, guard}, the filtering mechanism based on the valid contributor will discard one of the nodes with valid content {position, forward}. Consequently the final result contains all the position information -{forward, guard}, and keeps itself concise without the redundant nodes. When using our valid contributor to prune it, there are two nodes that we should pay attention to, i.e., "0.2 (Articles)" and "0.2.0 (article)". The former has two children -"0.2.0 (article)" and "0.2.1 (article)", whose tree keyword sets are {title, XML, keyword, search} and {title} respectively. According to the rule 2.(a) of Definition 4, only the node "0.2.0 (article)" is the valid contributor of its parent "0.2 (Articles)". As for the node "0.2.0 (article)", its three children -"0.2.0.1 (title)", "0.2.0.2 (abstract)" and "0.2.0.3 (references)", are all valid contributors following the rule 1 of Definition 4, because their labels are different. So, for Q 3 , the result by our valid-contributorbased filtering mechanism is the fragment in Figure 2(d).

Finally, we briefly illustrate how to get the meaningful RTF in

From Example 5 we can see that the valid contributor not only inherits the good property of the contributor, but also can overcome both the false positive problem and the redundancy problem of the contributor. These properties of our valid contributor guarantee that it has better capability than the contributor to filter the RTFs. This is also verified by the later experiments in Section 5.

VALIDRTF

In this section, we introduce the algorithm of ValidRTF. We first describe the data structure of a node in Section 4.1, which facilitates the required computations. Then we demonstrate the ValidRTF algorithm in Section 4.2 following a running example. Finally the analysis of ValidRTF is concluded in Section 4.3.

The node data structure

The basis of our ValidRTF is the data structure of a node designed here. From Definition 4 and Example 5, there are three requirements we should take into account to design the node data structure, namely (1) we need a label item to store the children with the same label; for each label item, (2) how to examine if there is a superset for the given keyword set in a set of keyword sets, and (3) how to check if there is an equal set for the given word set in a set of word sets. Clearly (2) corresponds to the condition 2.(a), and (3) corresponds to the condition 2.(b) in Definition 4 respectively.

To support all of them, we design the data structure of a node as shown in Figure 4(a), which comprises two parts: (1) the information of the node itself in "Self Info" frame; and (2) the information of its children in "Children Info" frame. The former stores the basic information of the node itself, including its Dewey code(dewey), label (label), keyword list (kList, which corresponds to the tree keyword set of the node, and is the same as the list used in MaxMatch) and the content ID (cID, which represents the tree content set, and only records the word pair (min, max) of the tree content set of the node. The min and max are the smallest and the largest word in the tree content set according to the lexical order.). The latter stores the information of a node's children, maintained in a list chlList according to their distinct labels. For each distinct label, there is an item, which stores counter (the number of the children with that distinct label), chkList (records the sorted distinct keyword list numbers), chcIDList (stores the cIDs of the children), and chList (records the references to those children).

From the above description we can see that the requirement ( 1) is supported by storing the children in chlList according to their labels.

As for the requirement (2), it is supported by kList in "Self Info" and chkList in a label item together. The computation for requirement ( 2) is the same as that of dM atch(n) ⊂ dM atch(n 2 ) in MaxMatch. For example, if the query Q 3 = "VLDB title XML keyword search", and the kList of a node v is 0 1 1 1 1 , it means the tree keyword set of the node v contains the keyword "title XML keyword search". We can infer that its key number is then

0 * 2 4 + 1 * 2 3 + 1 * 2 2 + 1 * 2 1 + 1 * 2 0 = 15.
If the node u is the parent of v, v 1 is u's another child with same label λ(v) as v, and its kList is like 0 0 1 1 1 (its key number is then 7), which means v 1 contains keywords "XML keyword search". Then the item in chlList corresponding to λ(v) has chkList as 7 15 . If we want to check if there is a sibling of the node v 1 whose keyword set covers v1's, we only need to compare v1's key number 7 with those numbers that are larger than 7. Since 15 > 7 and (7 AND 15) = true, we can directly infer that there is a sibling of v 1 , which has same label as v 1 's and whose keyword set covers v 1 's.

As for the computation for requirement (3), generally we need to compare all the tree content sets of a node's children to find out if a child's content is duplicate or not. However, from our knowledge the computation following this idea is expensive. Hence, we take an approximate method, i.e., we construct a feature for each content set, and compare the features to find if there is duplicate content or not. We choose a word pair cID =(min, max) as the feature for a tree content set of a node, which corresponds to the smallest and the largest word in the set (sorted according to the lexical order). For instance, the sorted tree content set of the node "0.2.0.1" in Figure 1(a) could be {keyword, match, relevant, search, XML}, therefore, its cId is (keyword, XML). Once all the cIds of the children with same label are sorted in chcIDList of their parent's label item, it is easy to find out if there is any duplicate content by comparing the cIDs. If two children have the same cID, we conceive that their corresponding content sets are same.

ValidRTF algorithm

The pseudo code of ValidRTF is shown in Algorithm 1 with four stages like MaxMatch. The first is getKeywordNodes, which retrieves all the keyword nodes in the XML data, and dispatches them into corresponding node set D i according to the keyword w i in Q. The retrieved keyword node sets are transferred to the second stage -getLCA, which is directly the Indexed Stack algorithm of [START_REF] Xu | Efficient lca based keyword search in xml data[END_REF], and returns all the LCA nodes in LCAs. The LCA nodes in LCAs are stored following the pre-order relationship of their Dewey codes 5 . The third stage is getRTF, which takes the LCA nodes and the keyword nodes as input, and collects all the related keyword nodes for each LCA node. The retrieved Dewey codes of the keyword nodes for each LCA node are sorted based on the pre-order relationship. Finally, the pruneRTF procedure filters out the uninteresting nodes of each RTF based on our valid contributor.

Next we illustrate each stage of the algorithm using Q3 as a running example on the XML instance of Figure 1 GETLCA computes the LCA nodes based on the above five keyword node sets, and there is only one LCA node ( also the SLCA node) -"0 (Publications)".

When running GETRTF, the related keyword nodes of each LCA node are collected, and stored using RTF data structure. For instance, the RTF R for LCA node "0 (Publications)" comprises three parts. R.a records the Dewey code of the LCA node, and here it is 0. R.knodes = {0.0, 0.2.0.1, 0.2.0.2, 0.2.0.3.0, 0.2.1.1} stores all the keyword nodes, and each of them is filled with necessary information following the discussion in Section 4.1. The elements in R.knodes are sorted according to the pre-order relationship of their Dewey codes. R.r is a node filled only with dewey = 0, which is used to store the root of the tree that corresponds to the RTF.

After collecting all the related nodes for each RTF, the next stage is PRUNERTF, which has two steps -the constructing step and the pruning step. The former is to construct a tree, in which each node is filled following the node data structure defined in Section 4.1. The latter is to prune the tree by using our valid-contributor-based mechanism so as to filter out the uninteresting nodes in each RTF.

Example 1 demonstrates this procedure.

Example 7 (pruneRTF)

There are two steps in PRUNERTF.

[Constructing step] In essence, the task of the constructing step in

PRUNERTF is to collect the information of the nodes in a RTF, and keep the relations among them for the later pruning step. It begins with each keyword node. After collecting the necessary information following the definition of the node data structure in Section 4.1, it then transfers the information of the keyword node to its ancestors. We use Figure 4(b) to demonstrate this.

Compared with the RTF in Figure 2(c), the sketch keeps the label and Dewey code for each node, and collects the necessary information from its children. The information contains three fields, which correspond to its kList, key number and cID. The kList and cID of a node absorb the kLists and cIDs of its children (if it has). For instance, the kList information of the node "0.2 (Articles)" is 0 1 1 1 1 , which means the subtree rooted at "0.2" contains the keywords "title XML keyword search". Its key number is then 15 , and its cID = (attribute, XML).

Figure 4(c) illustrates two concrete nodes -"0.2 (Articles)"

[top] and "0 (Publications)" [bottom], which are filled with the data according to the description of the node data structure. Since there are only two distinct labels among its children, the node "0" has two label items as shown in the bottom of Figure 4(c). Besides, since its children's cIDs satisfy "attribute" ≺ "title" ≺ "VLDB" ≺ "XML" according to the lexical order, the cID of "0" is (attribute, XML), which, we conceive, covers the content of its children 6 . As for the node "0.2", it has only one label item even though it has two children, because their labels are same -"article". Its cID is (attribute, XML) too, as its children's cIDs satisfy "attribute" ≺ "Chen" ≺ "skyline" ≺ "XML".

[Pruning step] After collecting the necessary information for each node in a RTF, the pruning is relatively simpler. According to Algorithm 1, the pruning step visits each node during the breadth-first traversing of the RTF, and distinguishes the valid contributors from its children following the rules defined in Definition 4.

The node "0" is the first. From the bottom of Figure 4(c), we can see that the two labels of its two children "0.0" and "0.2" are distinct. Consequently they are both valid contributors of their parent "0", and are kept in the result according to line 26.

For the node "0.2", we can see from the top of Figure 4(c) that its two children have same label -"article". Since the counter of the corresponding label item is 2, we continue to check each child according to line 21.

(1) For the child "0.2.0", the usedKN ums is empty and we continue to check if its kList is covered by other child (line 24). Its kList is 0 1 1 1 1 , and the key number is 15. Since 15 is the largest in chkList, the child "0.2.0" is a valid contributor of its parent "0.2". Now the usedKN ums is {15}, and the usedCIDs is {(Chen, XML)} according to line 25.

(2) As for the child "0.2.1", its kList is 0 1 0 0 0 . From [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] we can see that usedKN ums does not contain its key number 8. Similarly we continue to check if its kList is covered by other child or not. From the top of Figure 4(c), we can see that 15 in chkList is larger than 8 and covers the latter. Therefore the child "0.2.1" is not a valid contributor of its parent "0.2".

Analysis

Now we present the analysis of our ValidRTF algorithm. There are four aspects we are interested in.

(1). After getting all the interesting LCA nodes by using the Indexed Stack algorithm of [START_REF] Xu | Efficient lca based keyword search in xml data[END_REF], the getRTF procedure can retrieve all the basic RTFs.

Since the Indexed Stack algorithm from [START_REF] Xu | Efficient lca based keyword search in xml data[END_REF] returns all the interesting LCA nodes in an XML data for the given keyword query, we only need to illustrate that the nodes collected by getRTF for each LCA node satisfy the requirements of a RTF determined by Definition 2.

Following the description of getRTF, it is clear that each keyword node is dispatched to the last LCA node in the sorted LCA node set, which is the ancestor of or equal to the keyword node. Consequently, after getRTF, each keyword node set corresponding to an interesting LCA node a satisfies the following conditions: (a) the content union of the keyword nodes with regard to a covers all the keywords in the query 7 , (b) the node a is the unique common LCA node of those keyword nodes 8 , and (c) there is no subset of those keyword nodes whose content union covers the keyword query, and whose LCA node a is not a 9 . We can see that the keyword nodes for each LCA node satisfy the keyword requirement, the uniqueness requirement and the completeness requirement together. Therefore, each keyword node set collected by getRTF corresponds to a basic RTF with respect to that LCA node.

(2). Our valid-contributor-based ValidRTF algorithm satisfies the four required properties for an XKS technique deduced by [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF].

According to Section 1, the essence of those requirements is that an XKS technique should be able to control the result when changing the XML data or the keyword query. Following the description of the Algorithm 1 and the discussion in the above (1), the getLCA and the getRTF guarantee that the changes of the XML data and the keyword query can be caught by our ValidRTF. This is because getLCA retrieves all the LCA nodes, and getRTF collects all the related keyword nodes for each LCA node once the keyword query and the XML data are fixed.

(3). The concept of our valid contributor can overcome the false positive problem and the redundancy problem committed by the contributor in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF]. This is intuitively expressed in Example 5.

(4). Our ValidRTF has competent performance as the revised Max-Match for RTFs 10 . 7 This is guaranteed by the semantics of the LCA node computation by the Indexed Stack algorithm, and the collecting mechanism of getRTF which is based on the sorted LCA node set. The former implies that there is a keyword node set that covers the keyword query. While the latter ensures that its computed node set contains all those keyword nodes used to compute the corresponding LCA node. 8 Guaranteed by the property of the Indexed Stack algorithm. 9 If there is a subset like that, its LCA node must have been figured out by the Indexed Stack algorithm, and the getRTF can dispatch those keyword nodes to that LCA node accordingly. 10 Except for the node data structure, there are mainly two modifications in MaxMatch. [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] The findSLCA procedure for SLCA nodes is substituted with the Indexed Stack algorithm for LCA nodes;

(2) The codes of line 11 and 12 in pruneRTF are added into prune-Following the description of the Algorithm 1 we can see that the first three stages in our ValidRTF and the revised MaxMatch are similar. As for the pruning stage, the pruneRTF in our ValidRTF first dispatches the children of a node according to their unique labels. Since the processing for the children with unique labels is simple, the performance of pruneRTF is mainly determined by the processing for the children with the same label. There are two situations -checking if a child's keyword set is covered and if there is duplicate content among its siblings. From Example 7 we can see that the former is more complex. Consequently the complexity of pruneRTF can be represented by the cost of checking if a child's keyword set is covered. However, this part in pruneRTF is similar to n2, dM atch(n) ⊂ dM atch(n2) in pruneMatches. Therefore our ValidRTF has competent performance as that of the revised Maxmatch. This is also verified by our experiments shown in Section 5.

EXPERIMENTS

In this section, we present the experimental result to illustrate the efficiency and the effectiveness of our ValidRTF. We implement our ValidRTF and the revised MaxMatch, then compare them on both real (DBLP[19]) and synthetic datasets (generated by XMark [START_REF]usedKN ums ← {}, usedCIDs ← {}[END_REF]). We only choose MaxMatch (we still keep MaxMatch as the name of its revised version for simplicity) in our experiments, because it is the only algorithm which satisfies the axiomatic properties according to [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF].

Configurations

The DBLP dataset is "dblp20040213" (197.6MB) from [19]. The three XMark datasets are standard (111.1MB), data1 (334.9MB) and data2 (669.6MB). The XMark standard data is directly downloaded from [START_REF]usedKN ums ← {}, usedCIDs ← {}[END_REF], while the other two XMark data are generated by XMark with the size limitations. When shredding XML data into the relational tables (refer to Section 5.2), we record the frequency of the interesting words, and choose the following keywords to compose our keyword queries.

• Keywords for DBLP: keyword (90), similarity (1242), recognition (6447), algorithm (14181), data (25840), probabilistic (2284), xml (2121), dynamic (7281), sigmod (3983), tree (3549), query (3560), automata (3337), pattern (6513), retrieval (5111), efficient (8279), understanding (1450), searching (4618), vldb (2313), henry (1322), semantics (3694)

• Keywords for XMark series: particle [START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Bao | Effective xml keyword search with relevance oriented ranking[END_REF]69) The integer(s) behind each keyword is(are) the frequency(ies) of corresponding keyword in the XML data. For example, "keyword (90)"s means that there are 90 "keyword" words in DBLP. While "particle [START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Bao | Effective xml keyword search with relevance oriented ranking[END_REF]69)" means that there are 12, 33 and 69 "particle" words in XMark standard, data1 and data2 respectively.

The underlined letter in each keyword is used as the abbreviation of that keyword in the keyword queries. For instance, the "vdo" for XMark series in Figure 5(b)∼5(d) means that the keyword query is "preventions description order". By randomly combining these Matches of MaxMatch to guarantee that the information of the keyword nodes can be correctly transferred to all its ancestors. To accomplish the performance comparison, we run those keyword queries composed by the above selected keywords in ValidRTF and MaxMatch. The efficiency is illustrated by recording the elapsed time of a keyword query on a dataset. For each dataset, we run ValidRTF and MaxMatch 6 times, and record the average time after discarding the first processing.

As far as the effectiveness is concerned, we use two ratios to illustrate it, namely the common fragment ratio (CFR) and the average pruning ratio (APR). They both can reflect the capability of our valid-contributor-based filtering mechanism. We first present several notions, and then give out the definitions of those two ratios. For a given keyword query Q, the sets A, V and X stand for respectively the LCA nodes computed by getLCA, the meaningful RTFs computed by our ValidRTF, and the fragments computed by MaxMatch. It is clear that the LCA node sets of V and X are the same as A. For a LCA node a ∈ A, we use v a and x a to represent the corresponding meaningful RTF in V and the fragment in X. va -xa stands for the nodes further discarded by our ValidRTF. The two ratios are defined as follows.

(1).

[CFR] If the node sets in va and xa are same, we conceive that the two fragments are same. We define V ∩ X standing for the same fragments in V and X. The CFR for a query Q is defined as CF R = |V ∩X| |A| , which records the ratio of the same result computed by ValidRTF and MaxMatch for the given query. If CFR=1, it means that our ValidRTF and the MaxMatch return same result for that query. (2) [APR] As for the average pruning ratio, it is defined as

AP R = a∈A |x a -v a | |x a | |V -V ∩X| . It is clear that |x a -v a | |x a |
records the ratio of the discarded nodes in xa, and |V -V ∩ X| corresponds to the number of the RTFs which our ValidRTF can further prune. If AP R = 0, it means that there is no need for our ValidRTF to prune the RTFs computed by MaxMatch.

In short, for a given query, if the CFR is smaller than 1, it means that there exist RTFs in the result computed by MaxMatch, which still contain uninteresting nodes and can be filtered by our ValidRTF. The smaller the CFR for a query is, the more RTFs our ValidRTF needs to prune in the result retrieved by MaxMatch for that query. As for the APR, the larger the APR for a query is, the more uninteresting nodes our ValidRTF discards from the RTFs retrieved by MaxMatch.

Platform

Our experiments are run on a Dell OPTIPLEX 745, with two Intel Core CPUs (2.4GHz), 2GB memory and 160GB hard disk. The OS is Ubuntu 7.0.4. The algorithms are implemented in Java using Eclipse 3.2. We use Xerces 2.9.0 to parse the XML documents, and it is the stop-word filtering function in Lucence [21]to filter the stop-words [22].

The shredded records are stored in PostgreSQL 8.2.4 with three simple tables -"label (label, ID)", "element (node's label, Dewey, level, label number sequence, content feature)" and "value (node's label, Dewey, attribute, keyword)". The label table records all the distinct labels in the XML data, and their unique number (ID) assigned during the shredding. The element table stores the information of the nodes, in which the field "content feature" corresponds to the node's cID. As for the field "label number sequence", it is used to record the labels of a node's ancestors on the path from it to the root of the XML tree, which is useful to support the collection of the node's information in Algorithm 1 11 . As for the value table, it maintains the information of all the interesting keywords. When given a keyword query Q, we use SQL to search for the interesting keywords in the fields -"node's label", "attribute" and "keyword" of the value table, and collect the information of "label number sequence" from element table. Then our ValidRTF and MaxMatch are run on those keyword nodes.

Experiment Results

This section presents the result of our experiments.

• Performance: Figure 5 shows the performance of ValidRTF and MaxMatch. As described in Section 5.1 , we run the keyword queries on the datasets, and record the elapsed time after retrieving the Dewey codes of the keyword nodes. The results on the dblp, xmark's standard, data1 and data2 are shown as the bars in Figure 5(a)∼5(d) respectively. From those figures we can see that ValidRTF has competent performance as MaxMatch does on both real and synthetic data.

Besides, we also record the number of the RTFs for each query in those figures, shown as "RTFs" lines. They are recorded for the better understanding of the CFR lines in Figure 6. Based on the values of RTFs and CFR for a query, we can learn the number of the further pruned fragments by our ValidRTF after MaxMatch. For instance, the values of RTFs and CFR for the query "keyword recognition (kr)" in dblp data are 2 and 50% respectively. This means that one of the two fragments computed by MaxMatch still contains uninteresting nodes that are pruned further by our ValidRTF.

• Effectiveness: Figure 6 illustrates the effectiveness of our validcontributor-based ValidRTF algorithm. We take the same keyword queries used for the performance experiments, and record the ratios of the results retrieved by ValidRTF and MaxMatch following the description in Section 5.1. The CFR is shown as diamond line in each figure. As for the APR, we split it into two variations. One is the Max APR shown as nabla line, which records the maximum value of xv max = max

a∈A |x a -v a | |x a |
. The other is the APR' shown as bullet line, which corresponds to the APR values after discarding the xv max . The reason of this split is to highlight the pruning difference on the regular RTF and the extreme RTF. We find in our experiments that there is always an extreme RTF for each keyword 11 For instance in Figure 1(a), the numbers for the labels "Publications", "Articles" and "article" can be 0, 3 and 4 respectively. Then the "label number sequence" of the node "0.2.0" is "0.3.4".

query which usually collects many keyword nodes, and generally corresponds to the root of the XML tree. The xv a on it is commonly huge, which will mask the APR values for regular RTFs.

Figure 6(a) shows the result on dblp data, and Figure 6(b)∼6(d) correspond to the results on xmark series data -standard, data1 and data2. For dblp data, the values of APR' are all zero, which means either there is no other RTF except for the extreme, or our ValidRTF need not further prune the regular RTFs. The reason of this phenomenon is that the dblp data is generated from real applications, and the keywords in it implicitly obey some practical rule, which ensures that the regular RTFs are self-complete. As for the Max APR, all its values are larger than 20%. This means that the extreme fragment after MaxMatch still contains many uninteresting nodes (at least 20%). For CFR, all its values are smaller than 1, even though there are several nodes whose values are close to 1. According to the discussion in Section 5.1, we can see that our ValidRTF is more powerful than MaxMatch to filter out the uninteresting nodes.

As for Figure 6(b)∼6(d), their biggest differences from Figure 6(a) are that the values of their APR' lines are all larger than 0. This means, according to the description of APR' in Section 5.1, that all the fragments retrieved by MaxMatch still contain uninteresting nodes, which are filtered by our ValidRTF. This further verifies that our valid-contributor-based mechanism can prune more uninteresting nodes than the contributor-based mechanism does. As for their Max APR lines, they are all close to 1, which means that there are more uninteresting nodes in those extreme fragments. They all intuitively are caused by the fact that those data are synthetic, and the distribution of the keywords in them is less meaningful. For the CFR lines, they have similar situation like that in Figure 6(a).

In summary, in terms of efficiency, the experimental result shows that ValidRTF has competent performance like MaxMatch does. As far as the effectiveness is concerned, our valid-contributor-based ValidRTF is more effective in pruning the uninteresting nodes than the contributor-based MaxMatch is.

RELATED WORK

This section briefly reviews the related work on XML keyword search.

Following the knowledge of Information Retrieval on text data [START_REF] Baeza-Yates | Modern Information Retrieval[END_REF], the basic task of adapting keyword search over XML data is clear, i.e., retrieving meaningful fragments (instead of the whole document), each of which contains all the given keywords. To accomplish this task, many ideas are proposed, including the LCA variants [4,[START_REF] Li | Schema-free xquery[END_REF]7,[START_REF] Sun | Multiway slca-based keyword search in xml data[END_REF][START_REF] Liu | Identifying meaningful return information for xml keyword search[END_REF][START_REF] Liu | Answering keyword queries on xml using materialized views[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], interconnected pairs [5], GDMCT (Grouped Distance MCT -Minimum Connecting Tree) [START_REF] Hristidis | Keyword proximity search in xml trees[END_REF], MIU (Minimum Information Unit) [START_REF] Xu | Effective keyword search in xml documents based on miu[END_REF] and biased snippet [25].

Among them, [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] is worth attention. As illustrated in Section 1, it retrospects the related work and deduced several axiomatic properties that an XKS technique should satisfy, namely the consistency and monotonicity with regard to the query and the XML data. After that, [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] further proposes the MaxMatch algorithm, which uses the contributor-based filtering mechanism to prune the SLCA-based fragment to ensure that the filtered fragment is more meaningful. However, the contributor-based mechanism is not sufficient. It will commit the false positive problem and the redundancy problem. Besides, it is not adequate to focus only on the SLCA related fragments, because the LCA related fragments, whose roots are ances-tors of those SLCA nodes, could be still meaningful (conformed by [4,[START_REF] Li | Effective keyword search for valuable lcas over xml documents[END_REF][START_REF] Xu | Efficient lca based keyword search in xml data[END_REF][START_REF] Xu | Effective keyword search in xml documents based on miu[END_REF]).

Along with the work on retrieving meaningful fragments for XKS, the following three aspects are also interesting. The first is the extension of the keyword query so as to incorporate more information in the keywords, including [5,26,[START_REF] Chinenyanga | Expressive retrieval from xml documents[END_REF][START_REF] Theodoratos | An original semantics to keyword queries for xml using structural patterns[END_REF]. The second is about integrating keyword proximity search in a structural query language, such as [START_REF] Fuhr | Xirql: A query language for information retrieval in xml documents[END_REF][START_REF] Amer-Yahia | TexQuery: A fulltext search extension to XQuery[END_REF][START_REF] Theobald | An efficient and versatile query engine for topx search[END_REF][START_REF] Curtmola | Galatex: A conformant implementation of the xquery fulltext language[END_REF]. The third is the ranking of the retrieved fragments in [4,5,[START_REF] Bao | Effective xml keyword search with relevance oriented ranking[END_REF].

Besides the above research concentrating mainly on the XML data (semi-structured data), the research of using keyword search on other kinds of data, such as the structured data (relational data) and the graph data, is also becoming attractive. They usually take the data as a graph, and focus on returning Steiner trees. We refer readers to [START_REF] Li | Ease: Efficient and adaptive keyword search on unstructured, semi-structured and structured data[END_REF] for the related work. As for [START_REF] Li | Ease: Efficient and adaptive keyword search on unstructured, semi-structured and structured data[END_REF] itself, by modeling all the data as a graph, it proposes a framework for keyword search on that graph.

CONCLUSION

This paper revisits XML keyword search (XKS), and focuses on returning the meaningful fragments for the query. It begins by introducing the Relaxed Tightest Fragment (RTF) to represent the basic result for XKS, which is based on the partitioning of the keyword nodes and the LCA concept, and relates to all the LCA nodes.

Then we propose valid contributor concept to prune the basic RTFs to get the meaningful fragments. Compared with the contributor concept in [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], our valid contributor can overcome the false positive problem and the redundancy problem. Finally we implement the above concepts in the ValidRTF algorithm, and compare it with the MaxMatch algorithm after modifying MaxMatch for the RTFs. The experiments on real and synthetic data verify the efficiency and the effectiveness of our ValidRTF.

This work improves the research of [START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF] mainly in two aspects. First, it extends the processing to all LCA nodes after formalizing the RTF concept. Second, it ameliorates the filtering mechanism to get more meaningful result by the valid contributor concept. It can filter out more uninteresting nodes in the RTFs, while keeping the related interesting nodes. However, the ranking of the retrieved meaningful RTFs is still needed for carrying out the keyword search over XML data, and this is also a part of our future work.

Figure 1 :Figure 2 :

 12 Figure 1: (a): An XML instance; (b):(1) The XML segment used in [1]; (b):(2) Sample keyword queries

Figure 3 :

 3 Figure 3: (a): The MaxMatch result for Q 5 on the XML segment of Figure 1(b):(1); (b): The SLCA-based fragment for Q 1 on the XML instance in Figure 1(a); (c): The MaxMatch result for Q 1 after pruning the node "0.2.1.1 (title)" in Figure 3(b); (d): The MaxMatch result for Q4 on the XML segment of Figure 1(b):(1)

  2.1.1" into Figure 2(d), the LCA node does not change. The fragments in Figure 3(a) and 3(c) are not ideal either because of the similar reason.

Following the Definition 2 and

 2 Example 4, it is clear that the fragments in Figure2(a) and 2(b) are the RTFs for Q 2 , and Figure2(a) also satisfies the SLCA semantics.

  Figure 2(c) is the unique RTF for Q3.

  Figure 3(b) is the unique RTF for Q1, and Figure 3(d) is the unique RTF for Q 4 .

  (d) for Q 4 , we have dM atch(0.1.0) = dM atch(0.1.2) = {position}, but we should discard one of them because their position values are same -"forward".

  (a) inherits the positive property of the contributor mechanism, and 2.(b) is used to overcome the redundancy problem. We illustrate these in Example 5. Example 5 (Illustration for the valid contributor) We first illustrate that our valid-contributor-based filtering function also returns the positive example of contributor-based filtering illustrated in Example 2. Then we demonstrate how our proposal overcomes the false positive problem and the redundancy problem committed by the contributor-based filtering mechanism. [Covering the positive example] As running Q 5 on Figure 1(b):(1), the node "0.1 (players)" has three children with same label "player" -"0.1.0", "0.1.1" and "0.1.2". Their tree keyword sets are {Gassol, position} for "0.1.0", and {position} for "0.1.1" and "0.1.2". According to the rule 2.(a) in Definition 4, only the node "0.1.0" and its descendants are kept in the meaningful RTF, the same as the fragment in Figure3(a). [Overcoming the false positive problem] Back to the RTF in Figure 3(b)

Figure 1 (

 1 a), the result by our valid-contributor-based filtering mechanism is the fragment in Figure 3(b), not that in Figure 3(c) by the contributor-based mechanism. [Overcoming the redundancy problem] Now we continue our illustration based on the RTF in Figure 3(d) of doing Q 4 on the XML segment of Figure 1(b):

  Figure 2(d) for the query Q3. According to Definition 2, the RTF for Q 3 on Figure 1(a) is the fragment in Figure 2(c).

Figure 4 :

 4 Figure 4: (a): The node data structure designed for our ValidRTF algorithm; (b): The sketch of the RTF in Figure 2(c) after the constructing step in pruneRTF; (c): Two node instances filled according to the node data structure defined in Section 4.1.

Example 6 (

 6 (a). Its result is the whole fragment in Figure2(d), which lists all the papers published in "VLDB" 2008 on "XML keyword search". We briefly demonstrate the first three procedures in Example 6, because they are similar with those in MaxMatch except for the LCA nodes and the update of the node information. Then we pay much attention to the pruning procedure, especially the pruning based on the condition 1 and the condition 2.(b) in Definition 4. The first three procedures of ValidRTF) When processing the keyword query Q3 on the XML instance in Figure1(a), GETKEYWORDNODES returns three node sets -D1 = {0.0} for keyword "VLDB", D 2 = {0.0, 0.2.0.1, 0.2.1.1} for keyword "title" and D 3 = D 4 = D 5 = {0.2.0.1, 0.2.0.2, 0.2.0.3.0} for keywords "XML", "keyword" and "search" respectively.

Figure 6 :

 6 Figure 6: of the retrieved results by ValidRTF and MaxMatch

  Performance of ValidRTF and MaxMatch on the datasets with different keyword queries. .

																DBLP																												XMARK Standard
												MaxMatch		ValidRTF		RTFs																					MaxMatch	ValidRTF		RTFs
		1E+07																									100000		1E+07															100000
	Time (ms)	1E+01 1E+02 1E+03 1E+04 1E+05 1E+06																									10 100 1000 10000	Number of RTFs	Time (ms)	1E+01 1E+02 1E+03 1E+04 1E+05 1E+06															10 100 1000 10000	Number of RTFs
		1E+00	ks	kr	ka		dr	px	ay	gt	tqo	psx	tna Keyword queries xkl ypf	ypf l	xkl a	usc x	ftdr	xdk la	xay nv	fxd kl	ush ckp	gkc ms f	1			1E+00	at	ad	av	cm	do	vd	tcm	cm s	iel	sdc	vdo	atc m Keyword Queries cm su sui e iad m	vdo i	tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e dtc mv o	1
												(a) dblp20040213																						(b) xmark standard
																XMARK1																													XMARK2
												MaxMatch		ValidRTF		RTFs																					MaxMatch	ValidRTF		RTFs
		1E+07																									100000		1E+07															100000
	Time (ms)	1E+01 1E+02 1E+03 1E+04 1E+05 1E+06																									10 100 1000 10000	Number of RTFs	Time (ms)	1E+01 1E+02 1E+03 1E+04 1E+05 1E+06															10 100 1000 10000	Number of RTFs
		1E+00																									1			1E+00															1
				at	ad	av	cm	do	vd	tcm	cm s	iel	sdc	vdo		atc m Keyword Queries cm su sui e iad m	vdo i	tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e dtc mv o						at	ad	av	cm	do	vd	tcm	cm s	iel	sdc	vdo	atc m Keyword Queries cm su sui e iad m	vdo i	tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e dtc mv o
												(c) xmark data1																								(d) xmark data2
	Percentage (%)	0 0.2 0.4 0.6 0.8 1	kr Figure 5: ks ka dr px ay gt	tqo CFR	psx		tna Keyword queries xkl ypf DBLP APR'	ypf l	xkl a Max APR	usc x	ftd r		xdk la	xay nv	fxd kl	ush ckp	gkc ms f	Percentage (%)	0 0.2 0.4 0.6 0.8 1	at	ad	av	cm	do	vd	tcm	cm s	iel CFR	sdc XMARK Standard vdo atc m cm su sui e iad m Keyword queries APR'	vdo i Max APR tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e	dtc mv o
												(a) dblp20040213																						(b) xmark standard
														XMARK data1																											XMARK data2
												CFR			APR'			Max APR																					CFR			APR'		Max APR
	Percentage (%)	0.2 0.4 0.6 0.8 1																												Percentage (%)	0.2 0.4 0.6 0.8 1
		0																													0
			at	ad	av	cm		do	vd	tcm	cm s	iel	sdc		vdo	atc m Keyword queries cm su sui e	iad m	vdo i	tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e	dtc mv o			at	ad	av	cm	do	vd		tcm	cm s	iel	sdc	vdo	atc m Keyword queries cm su sui e	iad m	vdo i	tcm s	uie l	atc ms	atc md	atc mv	atc dv	atc dve	atc mv e	dtc mv o
												(c) xmark data1																						(d) xmark data2

This is different from the XML model in[START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF], in which there is an independent node for each text value.

Because of its uniqueness, the Dewey code is used to represent the corresponding node in this paper.

The function I(u, v) stands for the path node set from the node u to the node v if there exists a path between u and v in T .

Clearly the concept T Kv here is the same as the dM atch(v) in[START_REF] Liu | Reasoning and identifying relevant matches for xml keyword search[END_REF].

Similarly to[4, 7,[START_REF] Xu | Efficient lca based keyword search in xml data[END_REF], each node v in the XML tree T is assigned a Dewey code d v that is compatible with preorder numbering, in the sense that if a node v1 precedes a node v2 in the preorder leftto-right depth-first traversal of the tree then d v 1 < d v 2 . And the relationship between every two different Dewey code following that sense is denoted as the pre-order relation between those two Dewey codes.

As mentioned in Section 4.1, the cID of a node is an approximate representation of its tree content set. It is possible that two different content sets have the same cIDs. However, the well-performed property of the XML data guarantees that this is applicable.

* This work was partially supported by the Webcontent project ANR-05-RNTL02014 funded by french national research agency. † The work was done while the first author was visiting the mostrare INRIA project in Lille.


Loic Barrault

Driss Matrouf
email: driss.matrouf@univ-avignon.frroberto.gemello

Renato De Mori

Roberto Gemello

Franco Mana
email: franco.mana@loquendo.com

DYNAMIC SELECTION OF ACOUSTIC FEATURES IN AN AUTOMATIC SPEECH RECOGNITION SYSTEM

A general approach for integrating different acoustic feature sets and acoustic models is presented. A strategy for using a feature set as a reference and for scheduling the execution of other feature sets is introduced. The strategy is based on the introduction of feature variability states. Each phoneme of a word hypothesis is assigned one of such states. The probability that a word hypothesis is incorrect given the sequence of its variability states is computed and used for deciding the introduction of new features.

Significant WER reductions have been observed on the test sets of the AURORA3 corpus. Using the CH1 portions of the test sets of the Italian and Spanish corpora, word error rate reductions respectively of 16.42% for the Italian and 29.4% for Spanish were observed.

INTRODUCTION

It is known that Automatic Speech Recognition (ASR) systems make errors (see, for example, [START_REF] Sarikaya | Semantic Confidence Measurement for Spoken Dialog Systems[END_REF]). This is due to the imperfection of the various models used, on the limitations of the feature extracted and on the approximations of the recognition engines.

With the purpose of increasing robustness, recent ASR systems combine streams of different acoustic measurements, such as multi-resolution spectral/time correlates ( [START_REF] Bourlard | Sub-band based speech recognition[END_REF], [START_REF] Vaseghi | Multi resolution phonetic/segmental features and models for HMM-based speech recognition[END_REF], [START_REF] Pujol | Comparison and combination of features in a hybrid HMM/MLP and a HMM/GMM speech recognition system[END_REF], [START_REF] Hegde | Speech processing using joint features derived from the modified Group delay function[END_REF]).

Other approaches integrate some specific parameters into a single stream of features ( [START_REF] Thomson | Use of periodicity and jitter as speech recognition feature[END_REF], [START_REF] Zolnay | Robust speech recognition using a voiced-unvoiced feature[END_REF]). A generalization of this approach consists in concatenating different sets of acoustic features into a single stream. In order to reduce modelling complexity, algorithms have been described to select subsets of features in a long stream using a criterion that optimizes automatic classification of speech data into phonemes or phonetic features. Unfortunately, pertinent algorithms are computationally intractable with these types of classes as stated in [START_REF] Omar | Maximum Mutual Information Based Acoustic-Features Representation of Phonlogical Features For Speech Recognition[END_REF], where a sub-optimal solution is proposed. Such a solution consists in selecting a set of acoustic measurement that guarantees a high value of the mutual information between acoustic measurements and phonetic distinctive features.

The approach described in this paper consieders the possibility of dynamically combining different feature sets and acoustic models in an ASR system. Given a sampled input signal S = s(kτ ), where τ is the sampling period, let us consider the sequence of samples in a time window of length T and represent such a sequence for the n-th window as follows:

Y n = [s(kτ )] (n+1)T nT , n = 0, 1, ......, N
For each value of n, the window sequence [s(kτ )] (n+1)T nT of signal samples is transformed into a feature vector Y a (nT ) represented in a feature space a . Features have an intrinsic variability with respect to the symbols q ∈ Q which describe a spoken message. Variability may cause equivocation represented by the fact that different symbols of Q may be coded into signal segments leading to the same vector Y a (nT ). Equivocation varies from point to point of a given feature space. In order to reduce equivocation, it is thus interesting to vary the choice or the use of features depending on the sample sequence based on which symbol hypotheses are hypothesized.

USING DIFFERENT FEATURES AND MODELS

Given feature samples Y a (nT ), hypotheses about symbols q ∈ Q are generated by computing the posterior probabilities P µ [q|Y a (nT )]. Symbols may represent phonemes, phonemes in context, transients or other phonetic descriptors. Computation of these probabilities is performed using acoustic models µ. If different models and features are available, then posterior probabilities can be obtained with log-linear interpolation as follows:

log P [q|Y n ] = µ,a w a µ [Y r (nT )] log P µ [q|Y a (nT )] (1)
where w a µ [Y r (nT )] are weights depending on the feature sample in a reference space indicated by the super-script r. Initially, speech analysis is performed in the reference space r . The reference features can be the ones that produce the best ASR results or good results with minimal computation time.

Depending on the value of Y r (nT ), other feature sets can be used for performing a more accurate analysis and for reducing the equivocation on the generation of hypotheses about symbols q ∈ Q.

Equivocation between a channel source S which emits symbols f ∈ Q and the receiver R which hypothesizes symbols qg ∈ Q is defined as follows ( [START_REF] Shannon | A Mathematical Theory of Communication[END_REF]):

H R (S) = - f,g P [f, g] log P [g|f ] (2)
The ( 2) is an overall definition of equivocation over the entire acoustic space of one or more feature sets.

Given a specific window sequence of signal samples Y n and one or more sets of acoustic features, if f is the most likely phoneme hypothesis for the specific time frame, then the probability of equivocation for that frame is given by:

P eq (nT ) = g =f P [g|Y n ]
As an example of the application of the just introduced concepts, a short introduction of the system used for performing the experiments described in this paper is provided in the following.

Two versions of an hybrid system consisting of an Artificial Neural Network (ANN) and a set of Hidden Markov acoustic Models (HMM) are used. The two recognizers are fed by different sets of acoustic features, but have the same topology. The feature sets are those obtained by Multi Resolution Analysis (MRA) followed by Principal Component Analysis (PCA) and by Perceptual Linear Prediction (PLP) followed by RASTA filtering. The latter features will be indicated as JRASTAPLP. The same denoising technique is used for both feature sets (Gemello). The ANNs are trained to recognize phonemes and transitions using a corpus of phonetically balanced sentences which are completely independent from the test data.

It is important to notice that combining the scores of the two recognizers does not change the recognition results if their most likely hypotheses are the same. The ANNs have 636 outputs, one for each phoneme and each transition between two successive phonemes. Two streams of acoustic feature, namely Y m (nT ) and Y j (nT ) are generated. Indices m and j respectively refer to MRA features and JRASTAPLP features. The vectors Y m (nT ) and Y j (nT ) represent two different observations of a speech segment Y n centered on the same sample. From now on, these two indices will be used to indicate the two types of features. The value of T is 10 msecs and each feature set contains seven analysis frames centered on the frame at nT . The two recognizers have acoustic models which induce probability distributions in the acoustic spaces m and j of the two feature types. For each space, the distributions are posterior probabilities of a phoneme f or a diphone representing the transition between two phonemes given an observation in that space. The variability of the features extracted can be described using the osterior probabilities for phonemes and diphones in a point of an acoustic space. Vectors Y m (nT ) and Y j (nT ) may have similar or very different posterior probabilities for the same utterance of phoneme f . Let us consider, for the sake of simplicity, only phoneme symbols indicated by q. The 1 is rewritten making explicit reference to the features obtained with multi-resolution analysis, indicated as Y m (nT ) and two acoustic models, one based on an ANN, indicated by A, and one based on Gaussian mixtures, indicated by G.

The 1 can thus be written as follows:

log P [q|Y n ] = w m A [Y m (nT )] log P A [q|Y m (nT )] (3) + w m G [Y m (nT )] log P G [q|Y m (nT )] + m (nT ) m (
nT ) is a term that represents the introduction of additional features which can reduce the equivocation in the point of the acoustic space r = m corresponding to the n-th time frame. Different feature spaces or even different granularities in the same feature space can be used in m (nT ). The weights in the 4 depend on a specific time frame and can also be set to binary values allowing the system to switche between feature sets or acoustic models.

The contribution of m (nT ) can be neglected if, based on the available feature sets and models, this will have little effect on the equivocation of the phoneme hypothesization process. In other words, if the variability of feature Y m (nT ) is low and the feature corresponds almost always to the same phoneme.

In a previous paper [START_REF] Barrault | Characterizing Feature Variability in Automatic Speech Recognition Systems[END_REF], it is proposed to assign a reliability state σ to each vector Y m (nT ) in the reference space. The assignment is now described.

A comparison between phoneme posterior probability distributions obtained with ANN and GMM is performed on a segment SEG a (b, e, t). Symbol a describes the type of features, b indicates the beginning time of the segment, e indicates the end time and t the time at the middle. The discrepancy between the two posterior probability distributions P a A [q|SEG a (b, e, t)] and P a G [q|SEG a (b, e, t)] for q ∈ Q, is the Kullback-Leibler distance (KLD) indicated as:

The symbol with the highest posterior probability is considered as the hypothesis generated with each model in the given segment. These hypotheses are respectively indicated as g a A (b, e, t) and g a G (b, e, t). In principle, a low value of KLD a [SEG a (b, e, t)] does not necessarily indicate that the two probability distributions propose the same value of q with the highest posterior probability. For this reason, an indicator of good modeling and reliable decision is the truth of the predicate:

CON S a [SEG a (b, e, t)] = KLD a [SEG a (b, e, t)] < 0.4∧ ∧{g A [SEG a (b, e, t)] = g G [SEG a (b, e, t)]}
for which there is a high probability that the phoneme with the highest probability is correct. This is the condition in which the first contribution to equivocation is computed.

Let us define a variability/reliability state σ 1 corresponding to the case CON S a [SEG a (b, e, t)] = true. Given a corpus, characterizing an application domain, if it is observed that equivocation is low in σ 1 when a = m, then the term m (nT ) can be ignored in this state. When CON S a [SEG a (b, e, t)] is not true, either better models or other features should be considered. Assuming that the available models are already good and it is unlikely to observe a great improvement with new models, then it is worthwhile considering a new set of features. Other reliability states, motivated by experiments described in (icassp06), are defined as follows.

σ 2 : {g A [SEG a (b, e, t)] = g G [SEG a (b, e, t)]} ∧{KLD a [SEG a (b, e, t)] < 0.4} σ 3 : {g A [SEG a (b, e, t)] = g G [SEG a (b, e, t)]} ∧{KLD a [SEG a (b, e, t)] > 0.4} (5) σ 4 : {g A [SEG a (b, e, t)] = g G [SEG a (b, e, t)]} ∧{KLD a [SEG a (b, e, t)] > 0.4}
Other states can be defined corresponding to other conditions whose characterization is motivated by experimental evidence.

DYNAMIC SELECTION OF FEATURE SETS

A strategy is now described for dynamically selecting a feature set during recognition.

Let W = w 1 . . . w h . . . w H be the sequence of word and pause hypotheses generated by an initial decoder using features of r . Let w h = h 1 . . . h k . . . h K be the sequence of phonemes given in the lexicon of w h .

Let us associate to each phoneme h k a descriptor σ k belonging to the alphabet of the variability/reliability states. Let h = σ 1 . . . σ k . . . σ K(h) be the sequence of variability labels associated to the phonemes of w h .

The features of r are likely to be the cause of a wrong hypothesization of w h if the probability P [w h | h ] is not low. The symbol w h indicates the fact that hypothesis w h is not correct. If the probability P [w h | h ] is above a given threshold for one word or for time segment containing a sequence of words and pauses, then a new set of features is computed in that segment and recognition is also performed with the new set of features. The experimental results described below have been obtained by using feature vectors Y m (nT ) as reference and feature vectors Y j (nT ) as additional features used only when the reference ones are not reliable.

The following approximation is proposed for computing P [w h | h ]:

P [w h | h ] = 1 K(h) K(h) k=1 P (h k |σ k ) (6)
where P (h k |σ k ) indicates the probability that phoneme hypothesis h k is incorrect. Such a probability is computed as follows:

P (h k |σ k ) = 1 1 + P (σ k |h k ) P (σ k |h k ) P (h k ) P (h k ) (7)
which is computed by cumulating counts for each phoneme in all contexts. Other specific thresholds are used for dealing with the cases of word insertion and deletion.

As the ASR systems use acoustic models which are trained with a general telephone corpus without using any data of the application which is being tested, the training sets of AURORA3 have been used for tuning the just describes strategy.

When word hypotheses are generated with feature vectors Y j (nT ), it is possible that there is a word consensus with hypotheses generated with the reference features. It is possible to investigate whether or not there is a consensus on an error. This has not been done yet and the problem will be investigated in future work. In the absence of word consensus, a decision is made based on the hypothesis with the lowest probability of being wrong. Notice that AURORA3 is a corpus of connected digits in strings of variable and unknown length. The language models is just a simple finite state automaton with word models in parallel an feed-back from the final to the initial state.

EXPERIMENTS

Experiments have been performed with the Italian and Spanish components of the Aurora3 database (connected digits collected in car environment). The acoustic models employed were hybrid HMM-NN trained on large corpora completely disjoint from Aurora3 namely the domain independent, phonetically balanced SpeechDat1-2 corpora. The training corpora are made of telephonic read speech and were recorded in quiet environments. Different HMM-ANN models were trained, one for J-RASTA PLP and one for MRA, with the same training set for each language. The Aurora3 corpus contains a set of close-talking utterances indicated as CH0 and a set of hand-free utterances, indicated as CH1. Utterances of CH0 are nearly clean, as the close-talking microphone collects little environmental noise, while utterances of CH1 are quite noisy as the hand-free microphone gathers a lot of car noise. Aurora3 is divided into training and test components. The test corpus was used for producing the results, in terms of WER, reported in Table 1. Baseline results were obtained with MRA features which resulted to perform better than JRASTAPLP features for this task and with this setting (Gemello) With the proposed procedure, 339 (54%) sequences for the Italian and 309 (50.4%) for the Spanish where validated with the [START_REF] Pearce | The Aurora experimental framework for the performance evaluation of speech recognition for mobile application[END_REF]. The WER on the validated sequences were 4.8% for the Italian and 0.5% for Spanish. The percentage of words evaluated with the two feature streams for which there was consensus among the two recognizers was 11.5% for Italian and 18.3% for Spanish. Among these words, the WER was 33.7% for Italian and 12.8% for Spanish. The results show differences between the two languages, but a similar trend. The new feature set is applicable and provides different results in less than half of the word hypotheses. When it is applicable and the two recognizers do not provide the same result, the strategy leads to a significant WER reduction. The WER reduction is 16.42% for the Italian and 29.4% for Spanish.

CONCLUSIONS

A general approach for integrating different acoustic feature sets and acoustic models has been presented. A strategy for using a feature set as a reference and for scheduling the execution of other feature sets has been introduced. Additional features are computed and used only in case of high probability that the initial feature set has generated an incorrect word hypothesis. Experiments have been conducted using ANN and GMM acoustic models and features obtained with MRA and JRASTAPLP. Significant WER reductions have been observed on the test sets of the AURORA3 corpus.

ACKNOWLEDMENTS

  KLD a [SEG a (b, e, t)] = = D [P a A [q|SEG a (b, e, t)]||P a G [q|SEG a (b, e, t)]] = = g∈Q P a A [g|SEG a (b, e, t)] log P a A [g|SEG a (b, e, t)] P a G [g|SEG a (b, e, t)]

Table 1 :

 1 . Oracle results refer to what is obtained by comparing MRA and JRASTAPLP result with the reference and always deciding for the correct result if it is produced by at least one of the systems. This strategy results are the results obtained with the strategy proposed in this paper. Results in terms of WER with the baseline, the Oracle and the strategy proposed in this paper

	corpus	baseline this strategy oracle
	Italian CH1	21.13	17.66	15.03
	Spanish CH1	12.3	8.68	6.8

This work was supported by European Commission 6th

Framework Program project DIVINES under the contract number FP6-002034.