T 1523/11 (Metadata index structure/SAMSUNG ELECTRONICS) 17-01-2017

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. The application

2.1 The application relates to index structures for use in searching metadata, in particular XML metadata on digital content as defined by the TV-Anytime Forum. Such metadata is transmitted as independently transmittable and individually accessible fragments (see page 2, line 28, to page 3, line 10, of the application as filed).

2.2 The application refers on page 1, line 30, to page 2, line 2, and on page 4, lines 1 to 4, to a document titled "1st Draft of Metadata Specification SP003v1.3" (TV-Anytime Forum 17th meeting, Montreal, Canada), published in June 2002. This document is said to propose a "single key" index structure for a metadata fragment index. This structure is composed of a "key index list" section 10, "key index" sections 20 and "sub key index" sections 30 as shown in Figure 6 and described in particular on page 5, line 19, to page 7, line 20, of the application.

The "key index list" section 10 provides a list of all the single keys transmitted. It includes "single key information" defining each single key and "identification information" on the key index section 20 of the key (page 5, lines 27 to 30).

For each single key, the "key index" section 20 provides a list of "sub key index" sections 30. This list includes information "representing the range of values of the key included in the respective sub key index (sub_key_index) sections 30" in the form of a "representative key value" which is "the highest value of the key among the values of the key within the respective range". It also includes "identification information on the sub key index (sub_key_index) section 30 relevant to each representative key value" (page 6, lines 20 to 28).

Each "sub key index" section 30 includes inter alia 'key_value' segments 14 for storing "the respective ranges of values of the key" and 'target_container' and 'target_handle' segments for storing "respective" container identifier and fragment data identifier information. The latter two segments form identification information on the metadata fragments corresponding to the values of the key (page 7, lines 9 to 20).

2.3 This prior-art index structure works as follows. The purpose of the index structure is to efficiently find, on the basis of a key and a value of the key, the metadata fragments that "correspond" to that key value. For this purpose, the "sub key index" includes the possible values of the keys together with the identification information of the corresponding metadata fragments.

Since the number of possible values of a key may be large, a "key index" is provided on top of the "sub key index". Given a value of the key, this key index is used to quickly find the relevant portion of the sub- key index. For this purpose, the key index contains a subset of "representative values". Each of these values is the highest value of a range of values. The key index works as follows. Given an arbitrary value of the key, first the "representative value" is determined for the range to which the key belongs (i.e. the smallest of the representative values that is equal to or higher than that given value). The key index then provides the location of the corresponding range of values in the sub-key index.

Finally, since it may be useful if multiple indexes are available for searching the database, a "key index list" section is provided, listing the keys for which a key index section and corresponding sub-key index sections are provided.

2.4 The application stresses that the prior-art index structure is a "single key" index structure "which allows only one single key to be used for an access to the metadata" (page 4, lines 5 to 10). A single key index structure is said to be inefficient when performing a "compound condition search", i.e. a search on two or more fields (page 8, lines 8 to 14). As the application explains, in case of two conditions either each condition is independently searched by means of single key indexes and the intermediate results are intersected to obtain the final result (page 8, line 29, to page 10, line 16) or one condition is searched by means of a single key index and from the intermediate result those fragments are selected that satisfy the other condition (page 10, lines 17 to 22).

To improve the efficiency of compound condition searches the application proposes a "multi-key index structure".

3. Document D1

3.1 Document D1 bears the heading "SP003 V1.3 part B - System issues" but mentions neither an author nor a date. The Examining Division cited it as "1st Draft of Metadata Specification SP003v1.3", authored by "EVAIN J P" and published on 11 June 2002. It apparently assumed that it corresponded to the document cited in the application as disclosing a single key index structure (see point 2.2 above).

3.2 In the EPO's database, the Board has located document D13, which is another copy of the same document. Its bibliographic details suggest that document D1/D13 is indeed the document cited in the application and was published in June 2002 in connection with the 17th TV-Anytime Forum meeting (see document D17). These details are consistent with the information on "SP003v13" given on page 2 of document D14, which reports on the meeting.

3.3 The Board further notes that document D18 confirms that TV-Anytime Forum specifications at all stages of their development have been publicly available from the Internet address "ftp://tva:tva@ftp.bbc.co.uk/Specifications/" (page 2, section "Relevant ancillary documentation"). The Board notes that document D17 mentions the same address.

3.4 In view of these findings, the Board considers the content of document D1 to be part of the prior art under Article 54(2) EPC. The appellant has not contested this and in its letter of 16 December 2016 in fact stressed that it accepts the document's publication date to be 11 June 2002.

4. Main request - inventive step

4.1 It is undisputed that document D1 discloses the "single key index structure" for searching TV-Anytime metadata which is discussed in the application and summarised in point 2.2. 2 above. Document D1 indeed discloses in section 2.3 an index structure comprising a "key index list" (section 2.3.2), a "key index" (section 2.3.3) and a "sub key index" (section 2.3.4). The metadata is provided as an XML document (see section 2.3.1) and hence is "arranged in a semistructured schema".

4.2 The subject-matter of claim 1 of the main request differs from this prior-art single key index structure in that

- the keys are not single-attribute keys ("single keys") but multi-attribute keys ("multi-keys"); and

- values of a multi-key are compared by prioritising the fields (or attributes) making up the multi-key and comparing the fields in sequence starting from the field having the highest order of priority, wherein the values of a field are compared on an arithmetic basis if the field has numerical values or on a lexicographic basis if the field has alphabetical values.

4.3 The objective problem addressed by these features may be regarded as providing an efficient index structure for compound condition searches, i.e. searches on two or more fields.

4.4 According to the appellant, the skilled person starting from document D1 would not look for a solution to this problem in the technical field of database searching. The Board considers, however, that if the technical problem relates to index structures for searches, then the skilled person on the basis of whose knowledge and ability the obviousness of the solution is to be assessed is a person with knowledge of index structures, i.e. a person skilled in the field of database management systems (cf. decision T 26/98 of 30 April 2002, reasons 6.2 and 6.3). For the problem posed it is irrelevant that the metadata was retrieved in the form of a segmented stream.

4.5 The skilled person in the field of database management systems is well aware of the possibility of creating an index on a combination of multiple fields and he knows that such an index will speed up compound condition searches on those fields. Indeed, document D19, which is a textbook on database management systems and is illustrative of the common general knowledge of the skilled person, discusses in section 8.4.4 indexes for "composite" or "concatenated" search keys which contain several fields. The value of such a search key is a tuple of values of the combined fields.

The skilled person would therefore, on the basis of his common general knowledge, consider adapting the prior-art single-key index structure to work with such composite keys, i.e. multi-keys.

4.6 In doing so, the skilled person would realise that an order has to be defined on the values of multi-keys. Indeed, section 2.3.3 of document D1 explains that the key index structure lists the values of the highest key of each of the ranges of key values sorted by increasing key value, which means that it must be possible to say for any two key values which value is "higher". In the case of multi-keys these key values are tuples of values.

A well-known order on tuples of values is given by what is known in the computer-science literature as the "lexicographic order". This order is a generalisation of the alphabetic or lexicographic order on strings of characters (i.e. sort first on the first character, then on the second character, and so on). According to the lexicographic order on tuples of values, first the tuples are ordered by the value of their first ("highest priority") component; in case of a tie they are ordered by the value of the second component, and so on. In this comparison process, values of tuple components are compared in the normal way: if they are numerical values, they are typically compared on an arithmetic basis; if they are alphabetical values, they are typically compared lexicographically (i.e. alphabetically).

The examples given in section 8.4.4 of document D19 in fact silently use the lexicographic order on tuples: the values of the "" composite key are ordered (11, 80), (12, 10), (12, 20), (13, 75), i.e. first by age, then by salary ("sal"), and the values of the "" composite key are ordered (10, 12), (20, 12), (75, 13), (80, 11), i.e. first by salary, then by age. While the appellant is correct that document D19 does not "hand" the lexicographic order to the reader, the point is that document D19 presupposes that its skilled reader is well aware of the lexicographic order on tuples of values.

The order on multi-key values specified in claim 1 is in fact this lexicographic order on tuples.

4.7 Hence, the skilled person would adapt the prior-art single-key index structure to work with composite keys. In doing so, he would apply the lexicographic order when comparing values of multi-keys. He would thereby arrive at the subject-matter of claim 1 without the exercise of inventive skill.

4.8 In the statement of grounds of appeal, the appellant submitted that it is "precisely the prioritized arrangement of the metadata in the fields [that] allows an improvement in the search efficiency and speed" and that the prioritised order "allows a sequential search to yield results sooner (earlier in the sequence than half-way)".

However, in the application and in the claims the term "prioritization" refers merely to a ranking or ordering of the attributes that make up the multi-key. Such a ranking is necessary to define the lexicographic order on tuples of attribute values. The "prioritization" feature is thus part of the well-known "multi-key index" solution for speeding up compound condition searches.

4.9 Hence, the subject-matter of claim 1 lacks inventive step (Article 56 EPC).

5. First auxiliary request - inventive step

Since the features added to claim 1 of the auxiliary request merely repeat the definition of the order on multi-key values, the subject-matter of claim 1 likewise lacks inventive step (Article 56 EPC).

6. Second and third auxiliary requests - inventive step

6.1 Compared to claim 1 of the main request, claim 1 of the second auxiliary request adds that "the list of the multi-keys includes a location information of the fragment to which the field constituting the multi-key belong [sic] and location information of the field in the fragment". The same feature was added to claim 1 of the first auxiliary request to obtain claim 1 of the third auxiliary request.

Since the "key index list" section of the index structure of claim 1 comprises a "list of multi-keys" rather than "a multi-key", and since a multi-key corresponds to "a combination of fields" rather than "a field", the Board considers that the added feature is to be understood as meaning that the list of multi-keys includes location information for each field of each multi-key.

6.2 According to the background section of the application on page 5, line 27, to page 6, line 11, the "key index list" of the prior-art single key index structure includes "single key information" defining each single key. This single key information comprises "location information of the metadata fragment relevant to the single key" and "location information of the single key within the metadata fragment", corresponding to the "fragment_xpath_ptr" and "key_xpath_ptr" segments 11 and 12 shown in Figure 6.

The "key index list" described in section 2.3.2 of document D1 indeed includes, for each (single) key, such "fragment_xpath_ptr" and "key_xpath_ptr" information. Section 2.3.1.1 explains the meaning of the fragment Xpath and key Xpath information and confirms that the fragment Xpath locates the fragments of a particular type, whereas the key Xpath locates, relative to the node referred to by the fragment Xpath, the node corresponding to the field or attribute making up the "single key".

6.3 When adapting the single key index structure disclosed in document D1 to work with composite keys, the skilled person would adapt the location information accordingly and provide location information identifying the fragment and the field within the fragment for each field of each multi-key. He would thereby arrive at the subject-matter of claim 1 of the second and third auxiliary requests without the exercise of inventive skill.

6.4 Thus, the subject-matter of claim 1 of the second and third auxiliary requests lacks inventive step (Article 56 EPC).

7. Conclusion

Since none of the requests on file is allowable, the appeal is to be dismissed.