T 1351/04 (File search method/FUJITSU) 18-04-2007
File search method and apparatus, and index file creation method and device
Method involving technical means (yes)
Novelty, inventive step (yes)
I. This appeal is against the decision of the examining division to refuse the European patent application No. 02 258 100.3, posted on 6 July 2004.
II. The Examining Division decided that the claimed invention was obvious having regard to document
D1: G.M. Famelis et al., "Triply chained tree: an enhancement of doubly chained tree", Angewandte Informatik 1/1989, pages 19 to 25.
III. The notice of appeal was received on 30 August 2004 and the appeal fee was paid on 31 August 2004. In the statement setting out the grounds of appeal, received on 16 November 2004, the appellants requested that the decision be set aside and a patent be granted on the basis of eight replacement claims.
IV. Oral proceedings before the Board were held on 18 April 2007. The appellants submitted a set of amended claims 1 to 7 as well as description pages.
V. Claims 1 and 2 filed on 18 April 2007 read:
"1. A computer-executable index file creation method for creating an index file (5) for searching a file to be searched (3), said file to be searched (3) including records having fields allocated to each of a plurality of hierarchical levels and being constructed so that records having the same key character string in a field at the same hierarchical level are arranged in series and wherein for each record, the first field is the top hierarchical level, and subsequent fields form lower hierarchical levels, said index file (5) containing management information for each of the nodes in a tree structure obtained by classifying the records in said file to be searched (3) by using said plurality of hierarchical levels, the management information including a title of a key character string contained in each node, said method comprising computer-executed steps of:
obtaining (S21) the number of hierarchical levels; and
executing (S23-S26), for each node of all of the recognised number of hierarchical levels, a node management information creation process to create node management information which is provided for each node;
said node management information creation process including obtaining a position of a top record among records containing a key character string included in the hierarchical level of each node on said file to be searched (3), detecting the number of records having the same key character string as in the top record by reading records following the top record, and writing information about the top record position and information about the number of the records in the node management information as start position information and number information together with a pointer indicating a position in the index file of the node management information of a lower hierarchical level.
2. A computer-executable file search method for searching a file to be searched (3), said file to be searched (3) including records having fields allocated to each of a plurality of hierarchical levels and being constructed so that records having the same key character string in a field at the same hierarchical level are arranged in series and wherein for each record, the first field is the top hierarchical level, and subsequent fields form lower hierarchical levels, the method comprising computer-executed steps of: creating (S3) an index file (5) using the method of claim 1;
accepting (S5, S6; Sl0, S1l)) [sic] an instruction to search for data relating to a specified key character string over said file to be searched (3), the instruction including selection of either a data extraction output or a drill-down business form output;
retrieving (S7; S12, S13) from said index file (5) management information about one or more records related to the specified key character string on said file to be searched;
extracting (S8; S14) data of the one or more records from said file to be searched (3); and
outputting (S9) the extracted data;
wherein the retrieving and extracting steps comprise
when the data extraction output is selected, retrieving (S7) start position information and number information as management information about records related to the specified key character string and extracting (S8) data of a number of records specified by the number information from a position specified by the start position information; and
when the drill-down business form output is selected, retrieving (S12, Sl3), based on the pointer, a start
position of a record of the node management information of the lower hierarchical level, and extracting (S14) data of the record based on the retrieved start position of the record."
Independent claims 3 and 5 define an index file creation device and computer program, respectively, the features of which essentially correspond to those of claim 1. Dependent claims 4 and 6 concern such a device and such a program essentially corresponding to claim 2. Claim 7 is directed to a computer-readable memory product storing a computer program according to claim 5 or 6.
VI. At the oral proceedings before the Board, the appellants argued that an important feature of the invention was the presence of management information, ie starting position information and number information, pertaining to the records of a file to be searched in each node of the index file, and not merely in the leaf nodes. The provision of this information in all nodes enabled a direct retrieval of records from any node. From D1 the skilled person was aware of several indexing schemes, all based on the use of various combinations of pointers and key character strings. But none of them involved the inclusion of management information in non-leaf nodes.
VII. The appellants requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 7 as filed during the oral proceedings on 18 April 2007; description pages 1, 2 and 14 as filed on 2 February 2004, page 3 as filed on 13 March 2007, pages 6 to 8, 10 to 13 and 15 as filed on 18 December 2002 and pages 9, 16 and 17 as filed during oral proceedings on 18 April 2007, there being no pages 4 and 5; and the drawings as originally filed.
VIII. At the end of the oral proceedings the Board announced its decision.
1. Admissibility of the appeal
The appeal complies with the requirements referred to in Rule 65(1) EPC and is therefore admissible.
The Board is satisfied that the amended claims are properly based on the original disclosure, so that Article 123(2) EPC is complied with.
3. The claimed subject-matter
The Board considers it useful first to deal with claim 2, which is dependent on claim 1 in the sense of Rule 29(4) EPC. It is directed to a computer-executable file search method comprising computer-executed steps. The method requires that the file to be searched be structured as records containing fields forming different hierarchical levels. First an index file is created. This file contains nodes in a tree structure which are used for searching for key character strings. At each node there is so-called management information, which includes information about the starting position and the number of corresponding records in the file to be searched. This information permits the desired records to be retrieved directly when the node having the desired key character string has been found (cf paragraph  of the description). When only keys of high-level nodes are used it is thus not necessary to follow the tree structure all the way down to the leaf nodes in order to retrieve the desired record information.
The claimed method requires the use of a computer. It has therefore technical character and constitutes an invention within the meaning of Article 52(1) EPC (cf T 258/03 - Auction method/HITACHI, OJ EPO 2004,575).
5. The prior art
The Board agrees with the appellants and the examining division that D1 is the closest prior art document. According to D1 (cf Table 1), the file to be searched ("primary file") is divided into records (r1 to r14). Each record comprises values for attributes Ai (p.19, first paragraph). Records that have the same key character string in a field at the same hierarchical level (cf Table 1, eg string "18" at level A1) are arranged in series (eg r1 to r7, the records corresponding to the condition A1 = "18"). An index file having a tree structure is generated. As shown in fig.1, horizontal pointers connect all the son nodes of a parent node. Vertical pointers are used to change levels in the tree. The leaf nodes (the bottom row of nodes in fig.1) contain references to the primary file. There is no indication that non-leaf nodes also contain such references.
6.1 The examining division found the following differences between the invention and D1:
a) the method according to the invention is carried out on a more specific file structure; and
b) each node in the index includes the starting position information and number information used for retrieving records.
6.2 The Board is however not convinced that the allegedly distinguishing feature a) exists. As noted above, according to D1 a record (r) comprises values (Ai) allocated to each of a plurality of hierarchical levels. The location of these values may be termed fields (corresponding to the columns in Table 1). The file is constructed in such a way that records having the same key character string in a field at the same hierarchical level are arranged in series (cf Table 1). Moreover, for each record the first field is the top hierarchical level (A1), and subsequent fields (A2, A3) form lower hierarchical levels (cf fig.1). Hence, the file structure appears to be identical in the terms of the claim.
6.3 On the other hand, in D1 the non-leaf nodes are not said to contain references to the primary file. Thus, due to distinguishing feature b), or at least its implementation, the subject-matter of claim 2 is new (Article 54 EPC).
7. Inventive step
7.1 To assess the inventive step it must first be considered in how far the features of the claim, and in particular distinguishing feature b) (cf point 6.1), contribute to the solution of a technical problem.
7.2 According to the description of the present application, the invention relates to a method for "promptly searching for and extracting data from a file" (cf paragraph ). The data searched for can be of any kind, eg of a commercial nature as in the described embodiment, and thus have no technical relevance in themselves. They are stored as records having certain "start positions", ie memory addresses in the file to be searched. The computer reads these addresses in the form of "management information" in the index file and retrieves the associated data from the file to be searched. The management information thus controls the computer by directing it to a certain memory location. Functional data, intended for controlling a technical device, are normally regarded as having technical character. One example of this is decision T 110/90 - Editable document form/IBM (OJ EPO 1994,557), in which "control items" (eg "carriage return") were regarded as having a technical effect due to their being capable of controlling hardware such as a printer. It therefore appears that the management information contained in the present claims should be regarded as contributing to the technical character of the search method. The technical effect is the control of the computer along the path leading to the desired data. The path itself, which is determined by the search strategy as reflected by the management information, has technical character for the same reason. Obviously the choice of path will determine the searching characteristics, such as the speed, something which can constitute an additional indication of technicality.
7.3 The above conclusion is also consistent with decision T 52/85 - Listing of semantically related linguistic expressions/IBM (not published in the OJ EPO). That case concerned a method for displaying a list of expressions semantically related to an input linguistic expression (cf point IV of the decision). The method comprised looking up addresses for accessing memories. These features were said to be conventional (point 5.3) but not nontechnical. The decision points out that "internally a computer functions technically" (point 5.8). Decision T 52/85 seems to suggest that as long as a claimed method for searching a data file is concerned with the way a computer performs the search, it may be technical. If however the kind of data is decisive, the method's contribution is nontechnical (cf T 52/85, point 5.2). As already noted, in the present case the kind of data searched for is of no importance.
7.4 It follows that all features of claim 2 that have a direct bearing on how the search is conducted should be considered for inventive step. This includes distinguishing feature b). Their effect is to speed up searches that involve only keys of high-level nodes. The technical problem when starting out from D1 can thus be seen as devising a search method that is particularly efficient for searching a data file using mainly keys of high-level nodes.
7.5 The examining division held that adding starting position information and number information to non-leaf nodes was obvious if the doubly-chained tree indexing scheme described in D1 were applied to the same file content as in the present application (cf the decision, p.2, last complete paragraph). However, as already noted (point 6.2), the file structure shown in D1 and the one according to the claim appear to be identical. Moreover, the examining division failed to indicate why the skilled person would make this change, ie what technical problem he expected it to solve. It is naturally always possible to allege that the skilled person would have foreseen any advantages an invention achieves, especially when the differences between the invention and the prior art are small, but in the absence of any hint in the prior art such an argument is indistinguishable from hindsight and thus inherently weak.
7.6 The Board has also considered the fact that the index according to the invention occupies more memory because of the extra record information stored. It could therefore be argued that the invention simply defines a new trade-off point at which searching speed is valued higher and memory cost lower than in the prior art. However, nothing proves that the skilled person was aware that such a trade-off existed since, again, in the prior art the record information is always located in the leaf nodes.
7.7 A final point is that D1 does not stress the importance of the structure of the primary file. Only the present application has demonstrated that this structure enables the direct access from a high-level (non-leaf) node to all the records associated with this node. This can be regarded as a non-obvious insight.
7.8 It follows that the subject-matter of claim 2 must be regarded as involving an inventive step over the available prior art (Article 56 EPC).
8. Claim 1, on which claim 2 is dependent, is directed to a computer-executable index file creation method. It also comprises distinguishing feature b) (cf point 6.1 above). However, it contains no searching steps but only steps of establishing an index to be used for searching a file. The question therefore arises whether the features of claim 1 contribute to a technical character in the same way as in claim 2.
9. Since the claimed method does not comprise the search, the computer does not read the management information. The claim is instead concerned with the automatic collection and storage of this information (cf the last feature of claim 1). The method results in the creation of an index file. This file is a technical means since it determines the way the computer searches information, held above (cf point 7.2) to be a technical task. The subject-matter of claim 1 can thus be regarded as a method of manufacturing a technical means. Normally, such a method has technical character. The Board is of the opinion that the present case is no exception since the claimed method, although involving only the recognition and storage of information, requires virtually no human intervention and is independent of the kind of information involved.
10. It follows that distinguishing feature b) in claim 1 contributes to a technical solution of a technical problem. For the reasons given in connection with claim 2, the method of claim 1 is new and involves an inventive step (Articles 54 and 56 EPC).
Claims 3 and 4
11. The index file creation device according to claim 3, realised by a computer program installed in hardware, is a physical entity comprising processing units which, by their nature, have technical character. Thus it is an invention within the meaning of Article 52(2) EPC. Furthermore, it is new and involves an inventive step for the reasons given above in connection with claims 1 and 2.
12. The same applies to claim 4, which is dependent on claim 3.
Claims 5 to 7
13. The computer program of claim 5 is defined in the same terms as method claim 1. When run, it controls the computer in a way which the Board holds to have technical character. This means that it produces a "further technical effect" in the sense of decision T 1173/97 - Computer program product/IBM (OJ EPO 1999, 609). Thus, it is not excluded from patentability under Article 52(2),(3) EPC. Furthermore, it is new and involves an inventive step for the reasons given above in connection with claims 1 and 2.
14. The same applies to claim 6, which is dependent on claim 5. The memory product of claim 7, which includes the features of claim 5 or 6, is also patentable.
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the department of the first instance with the order to grant a patent in the following version:
pages 1, 2, 14 as filed on 2 February 2004
page 3 as filed on 13 March 2007
pages 6-8, 10-13, 15 as filed on 18 December 2002
pages 9, 16, 17 as filed during oral proceedings on 18 April 2007.
There are no pages 4 and 5.
1-7 as filed during oral proceedings on 18 April 2007
as originally filed