T 0058/11 (Reordering system/AOL) of 16.1.2015

European Case Law Identifier: ECLI:EP:BA:2015:T005811.20150116
Date of decision: 16 January 2015
Case number: T 0058/11
Application number: 03765738.4
IPC class: G06F 17/28
G06F 17/21
G06F 3/02
G06F 15/00
G09G 5/00
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 370.750K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Dynamic database reordering system
Applicant name: America Online Incorporated
Opponent name: -
Board: 3.5.07
Headnote: -
Relevant legal provisions:
European Patent Convention Art 56
Keywords: Inventive step (no) - mixture of technical and non-technical features
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The appeal lies from the decision of the Examining Division to refuse European patent application No. 03765738.4, which originated from the international application published as WO 2004/010326. The application concerns ordering displayed suggested words corresponding to user input from a keyboard.

II. The Examining Division held that the single request on file did not comply with the requirements of Article 123(2) EPC. In an obiter dictum it further commented that the application did not fulfill the requirements of Article 84 EPC in combination with Rule 43(2) EPC, and that the subject-matter of the independent claims did not appear to involve an inventive step over prior art document D1:

D1: WO 00/74240, published on 7 December 2000.

The following document was also cited:

D2: US 5 818 437, published on 6 October 1998.

III. In the statement of grounds of appeal, the appellant requested that the decision be set aside and that a patent be granted on the basis of a new main request, including claims 1 to 5 submitted with the grounds.

IV. In a communication accompanying a summons to oral proceedings, the Board gave its preliminary opinion that the claims were unclear and defined added subject-matter. As far as claim 1 could be understood in the light of the description, its subject-matter did not appear to involve an inventive step over the disclosure of document D2.

V. With a letter dated 18 December 2014, the appellant filed a new set of claims 1 to 12.

VI. Oral proceedings were held on 16 January 2015. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VII. The appellant's final request was that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 12 filed with the letter dated 18 December 2014.

VIII. Claim 1 of the sole request reads as follows:

"A process for reordering items retrieved from a database for display to a user, comprising the steps of:

accepting user input from a keyboard (102);

providing a linguistic database (401);

dynamically retrieving words from said linguistic database (401) that comprise letters formed by the user's keyboard input; and

displaying a list (105) of said retrieved words to the user;

characterized in that

the linguistic database (401) is pre-ordered before placement into a product, the words being ordered using a linguistic model that measures a commonality frequency value for each word in the database, the linguistic database (401) being assembled using the frequency ordering, and the commonality frequency values not being stored with the words in the database once it is compiled;

a user database (403) is provided which contains user defined words and a reorder database which is a region of the user database (403) that tracks the words that the user selects from said list (105) and their frequency values;

once a word not ordered first by the linguistics model in the linguistic database (401) has been selected from the list (105), a frequency value is applied to the selected word and the word ordered first by the linguistics model in the linguistic database (401), wherein a first time a word is selected by the user, the frequency value of the selected word is lower than the frequency value of the first ordered word in said list (105), wherein the frequency values are adjusted every time a word is selected, and wherein the next time the selected word is selected again, the frequency value of the selected word is increased relative to the frequency value of the first ordered word;

words in said list (105) are ordered using the linguistic database ordering and the frequency values in the reorder database, wherein the order identified by the frequency values in the reorder database takes priority over the order of words in the linguistics database."

Reasons for the Decision

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

Since the current set of claims was a response to the preliminary opinion of the Board and could be treated without adjournment of the oral proceedings, the Board admitted it into the appeal proceedings.

2. The invention

2.1 The present invention as described in the application relates to ordering displayed words associated with key presses in an electronic device. In order to better assist the user in entering text into the device, while the user is pressing keys the invention predicts the words that the user is trying to enter and displays them in a list. The words are displayed in an order which is influenced by the user's actual use of the words (page 2, lines 12 to 33, of the application as published). The invention may be applied both to devices with a full keyboard and to small-format personal electronic devices with reduced keyboard sizes where a single key may represent more than one character (page 1, lines 21 to 28, page 4, line 33, to page 5, line 3).

2.2 The invention uses a linguistic database and a user database. The linguistic database (LDB) is a fixed pre-compiled database containing words ordered by their frequency of use as measured by a linguistic model. The user database contains user defined words and a reordering database (RDB), referred to as a "reorder database" in claim 1, with information about the words selected by the user and the frequencies of use, or usage count, of each word (page 8, lines 7 to 11 and lines 17 to 23). The usage counts determine the relative position of a word in the displayed selection list and are also used for garbage collection and for ageing (page 9, lines 12 to 16).

2.3 When a user selects a word, the system determines which words to add to the RDB according to specific rules, including the so-called "non-aggressive learning principle" (page 9, line 21 to page 10, line 37). Those rules also determine how frequencies of use of words in the RDB are updated upon selection of a word on the basis of the type of the selected word, for example from which database it was read or how it was ordered in the displayed list (page 8, line 25 to page 9, line 10; page 10, line 28 to page 11, line 21). In order to limit the individual frequency values, they are occasionally decreased by an ageing process (page 11, line 23 to page 12, line 2).

Interpretation of claim 1

3. At the oral proceedings the Board discussed the interpretation of claim 1 with the appellant.

3.1 Claim 1 defines a process which provides three databases of words. The linguistic database or LDB organises words on the basis of their frequency of use according to a linguistic model. The user database stores user-defined words. The reorder database or RDB is a region of the user database that tracks the words input by the user and stores the corresponding frequency values.

3.2 According to claim 1, the LDB is pre-ordered before placement in the product. The words in the LDB are ordered using the linguistic model, which measures a "commonality frequency value" for each word in the database, and are stored in this order. This obviates the need to store the frequency values in the database.

3.3 The claimed process comprises the main steps of accepting user input from a keyboard, dynamically retrieving words from the LDB that comprise letters formed by the user's keyboard input, and displaying the list of said retrieved words to the user. The words in the list are ordered using the LDB ordering and the frequency values in the RDB, wherein the order identified by the RDB takes priority over that by the LDB.

3.4 The appellant stated at the oral proceedings that the "keyboard" feature of the claim covered both full-sized as well as reduced keyboards, so that the feature "words ... that comprise letters formed by the user's keyboard input" should be interpreted accordingly.

The Board therefore interprets the "keyboard input" as comprising the set of keys pressed by the user, each key corresponding to either one letter in a full keyboard, or more than one letter in a reduced keyboard. The "letters formed by the user's keyboard input" comprise all the letters that correspond to each of the pressed keys.

3.5 The claim defines the user database and specifies that the reorder database tracks the words that the user selects from the displayed list and their frequency values.

Since the steps of dynamically retrieving words and displaying the list to the user refer exclusively to the linguistic database, the claim does not define how the user database containing user-defined words is used for the purposes of the invention. However, it follows from original claim 3, or present claim 2, that the user database, which includes the RDB, is also consulted in the step of dynamically retrieving words in order to also take into account user words which are not found in the linguistic database.

Furthermore, according to the process defined by present claim 2, the user-defined words are stored in the reorder database once they are selected from the list.

3.6 The part of the claim describing the frequency values reads (underlining added):

"once a word not ordered first by the linguistics model in the linguistic database (401) has been selected from the list (105), a frequency value is applied to the selected word and the word ordered first by the linguistics model in the linguistic database (401), wherein a first time a word is selected by the user, the frequency value of the selected word is lower than the frequency value of the first ordered word in said list (105), wherein the frequency values are adjusted every time a word is selected, and wherein the next time the selected word is selected again, the frequency value of the selected word is increased relative to the frequency value of the first ordered word".

The appellant cited page 6, lines 6 to 18 of the description as a basis for these features.

Regarding the first underlined feature, since the claim mentions that the "word not ordered first by the linguistics model" has been selected from the list, it can be understood from the claim that the word is not ordered first by the linguistics model among the LDB words in the list of retrieved words comprising letters formed by the user's keyboard input. The Board hereinafter refers to such a word as "non-first LDB ordered word in the list".

Interpreting "the word ordered first by the linguistics model in the linguistic database" literally as the first word in the ordered LDB does not make sense, since the first word in the LDB may be completely unrelated to the keyboard input. In view of the description in the cited passage of page 6, the feature should be interpreted as the word ordered first by the linguistics model in the LDB "for that key sequence" (page 6, lines 8 and 9). In the following such a word is designated "the first LDB ordered word in the list".

According to page 6, lines 14 to 18, the third underlined feature, "the first ordered word", should be interpreted as referring to the first ordered word "in the displayed list", and is referred to as "the first word in the list" in the following.

The Board notes that, since the list reflects not only the frequency information of the LDB, but also that of the RDB, the first LDB ordered word in the list is not necessarily the first word in the list.

3.7 The feature "once a word not ordered first by the linguistics model in the linguistic database (401) has been selected from the list (105), a frequency value is applied to the selected word and the word ordered first by the linguistics model in the linguistic database (401)" describes what happens when a non-first LDB ordered word in the list has been selected from the displayed list.

The Board interprets this feature as corresponding to the features described on page 6, lines 6 to 18, in original claims 4 and 5, and on page 10, lines 5 to 7, according to which if a non-first LDB ordered word in the list is selected and the first LDB ordered word in the list does not yet exist in the RDB, the latter is inserted into the RDB and assigned a frequency value. In addition, if the selected word is selected for the first time, it is assigned an initial frequency value and added to the RDB. Otherwise, its frequency value is updated. This interpretation was also endorsed by the appellant in its letter dated 18 December 2014 (pages 4 and 6).

4. Inventive step

4.1 The application mentions on page 5, lines 16 to 18, that the invention uses a "T9**(®) linguistics database". The T9 technology, where T9 stands for "Text on 9 keys", is a well-known predictive text technology for mobile phones having a reduced keyboard, in particular for 3x4 numeric keypads including 9 text keys. It was originally developed by Tegic Communications, Inc.

4.2 Document D2 is a US patent assigned to Tegic Communications, Inc. and describes a process for reduced keyboard disambiguation where for each keystroke sequence a list of words which match the sequence of keystrokes is presented to the user for selection. The words are taken from a dictionary and listed in order of decreasing frequency of use (column 1, lines 51 to 58). Even though the approach of document D2 is especially adapted to reduced keyboards, it is not limited to T9 keyboards (column 1, lines 42 to 46). The suggested words are not restricted to words corresponding to the exact input key sequences in order to also take into account misspelling and typing errors (column 3, lines 15 to 19, column 7, lines 55 and 56).

4.3 The process of document D2 allows entry of words that are not in the dictionary. Such words are automatically added to the dictionary and subsequently also displayed in the list of suggested words corresponding to the keys entered by the user (column 2, lines 35 to 56).

4.4 The process of document D2 can use both a standard dictionary, also referred to as "standard English vocabulary" or "standard vocabulary", and additional vocabularies. It displays the words retrieved from the additional vocabularies together with those of the standard dictionary in the list of words suggested to the user (column 3, lines 1 to 11; column 11, lines 23 to 32 and figure 7a).

Document D2 also discloses that the process may keep track of the frequency of usage of words by a user in order to present the words most frequently used first (column 3, lines 11 to 14; column 4, lines 50 to 55). A custom vocabulary reflects the frequency of use of words by the user. Each word is assigned a frequency value, also named priority of the word, a number which is increased by one every time the word is selected (column 8, lines 1 to 7).

4.5 Therefore, document D2 discloses a process for reordering items retrieved for display to a user similar to that of the invention and constitutes an adequate starting point for assessing inventive step.

4.6 The appellant argued at the oral proceedings that document D2 did not disclose that tracking frequency of usage was accomplished using more than one database.

The Board disagrees since, as explained above, document D2 discloses that different vocabularies are used together to generate the selection list. The standard vocabulary of document D2 corresponds to the linguistic database of the claim. The custom vocabulary is described as storing information regarding frequency of word usage by the user and can be seen as a reorder database in the sense of the claim. It is clear from the passage in column 8, first paragraph, that the custom vocabulary includes words from the standard vocabulary which have been entered by the user. The same is true for the reorder database of the invention. According to document D2 newly defined words are stored in a "user's private vocabulary" (column 12, lines 10 to 21), similarly to the user database of the invention.

4.7 Word entry in the process of document D2 is performed in the same way as in the invention (see point 2.12.1 above) by means of accepting user input from a keyboard, retrieving matching words, displaying the list of matching words from the vocabularies including the standard and custom vocabularies, and enabling selection of a word by the user (column 7, line 46 to column 8, line 12; column 11, lines 23 to 32, and Figure 7a). The words are ordered for display on the basis of the frequency information stored in the vocabularies (column 7, line 46 to column 8, line 12).

4.8 As explained above, the selected words are added to the custom or user vocabulary, and assigned frequency values, in a similar way to that of the invention. In the custom vocabulary of D2, the frequency values are also adjusted every time a word is selected. In particular, the next time a word is selected again, the frequency value of the selected word is incremented by one, and hence "increased relative to the frequency value of the first ordered word" in the displayed list (column 8, lines 1 to 4). The Board also notes that since the frequency values stored in the custom vocabulary of document D2 reflect the number of times the word is used and the first word in the list has been used previously, the skilled person also assumes that in the process of document D2 the first time a word is selected by the user, the frequency value of the selected word is normally set to a value not higher than that of the first word in the list.

4.9 The custom vocabulary is described in document D2 as reflecting frequency of use by the user (column 8, lines 1 to 4), and the user-defined words are evidently words used by the user. In the Board's view the skilled person would therefore assume from that passage of D2, as well as from column 3, lines 11 to 14, that the custom vocabulary also includes information regarding user-defined words.

4.10 Document D2 discloses that the user may opt to get suggested words ordered according to the user's own frequency of use (column 8, lines 41 to 43). According to D2, column 8, lines 1 to 9, if two words of the custom vocabulary have the same frequency value based on usage, the relative frequency values of the standard vocabulary are used. Since in that case the standard vocabulary is only consulted in case of conflict, it is encompassed by the feature "the order identified by the frequency values in the reorder database takes priority over the order of words in the linguistics database".

It can also be concluded from that passage in column 8, as well as from the passages in column 7, line 65 to column 8, line 2, and column 8, lines 24 to 35, that the standard vocabulary also includes a frequency value, or "commonality frequency value", for each word. Document D2 discloses in column 3, lines 1 to 6 that the "computer includes a standard vocabulary" and that additional vocabulary modules can be enabled within the computer. The skilled person reading document D2 would therefore interpret the standard vocabulary as a standard feature, namely a pre-compiled vocabulary placed in the product.

4.11 From the above, the Board concludes that the subject-matter of claim 1 differs from the process of document D2 in that

(a) the words in the linguistic database are ordered according to the commonality frequency values, the linguistic database being assembled using the frequency ordering, the commonality frequency values not being stored with the words in the database once it is compiled;

(b) the reorder database is a region of the user database;

(c) when a word not ordered first by the linguistics model in the LDB is selected from the list, if the word ordered first by the linguistics model in the LDB does not already exist in the RDB, it is inserted into the RDB and assigned a frequency value; and

(d) the first time a word is selected by the user, the frequency value of the selected word is set to a value lower than the frequency value of the first ordered word in said list.

4.12 In the opinion of the Board, feature (b) is an obvious implementation detail. It is common practice to store related databases together. The claim does not describe any particular interaction between this and the other features of the invention bringing an additional advantage beyond the well known trade-offs of the feature. In its reasoning the appellant neither relied on feature (b) in support of inventive step nor contested the opinion of the Board with regard to that feature.

4.13 Regarding feature (a), the appellant argued in oral proceedings that the claimed invention solved the problem of efficiently storing the LDB and nevertheless allowing tracking of the frequency of usage of the words by the user and ordering of the words accordingly. The prior art provided no solution to this problem.

The Board, on the contrary, finds that feature (a) is disclosed in the further document D1 as being used in the same context of suggesting words corresponding to keyboard input to a user and for the same purpose of saving storage space as in the claimed process.

Since document D1 addresses the implementation of a text entry system with automatic word correction or disambiguation, the skilled person would take its teaching into consideration when looking for a solution to the above-mentioned problem.

In the system of document D1 a lexicon stores the words to be suggested to the user. Document D1 describes on page 34, line 29, to page 35, line 21, ways of promoting or demoting words in the lexicon when a word is selected by a user. The promotion or demotion consists of updating the frequency of a word. On page 34, lines 35 to 37, it states "For a lexicon in which relative frequency information is indicated by the sequential order in which words appear in a list, promotions are made by moving the selected word upward..." (emphasis added). On page 35, lines 5 to 7 and 10 to 12, document D1 reads "Conservation of the 'word list mass' is maintained, so that the information regarding the relative frequency of the words in the list is maintained and updated without increasing the storage required for the list" and "For example, in a lexicon in which relative frequency information is indicated by the sequential order in which words appear in a list, a selected word which appears at position IDX in the list is moved to position (IDX/2)" (underlining added).

In other words, D1 suggests ordering the words in the database in accordance with their relative frequencies, and using this ordering to derive frequency information without storing the frequency values. In the opinion of the Board the skilled person wishing to reduce the storage size of the standard vocabulary of the process of document D2 would consider storing that vocabulary without frequency values as taught in document D1.

4.14 The appellant disputed that the skilled person would modify the process of document D2 by not storing the frequencies in the standard vocabulary. It was an essential part of the solution of document D2 that the frequencies were stored in each database. The appellant also argued that the skilled person would only learn from document D1 that the standard vocabulary should be reordered after word selection to reflect the frequency of use of words by the user.

While it is true that document D1 teaches reordering the lexicon in order to adjust to the user's actual word use, the Board notes that document D2 already describes the use of different vocabularies, including the custom vocabulary separate from the standard vocabulary, where the custom vocabulary reflects the frequency of usage of the words by the user and the standard vocabulary is not modified. In the opinion of the Board the skilled person would consider that the storage of the standard database without frequencies could also be adopted in the process of document D2 and would hence arrive at feature (a) without inventive skills.

The Board recognises that, in order to use the linguistic database without frequencies in the process of document D2, the skilled person would have to decide how to compare frequencies of words from the standard vocabulary and from the custom vocabulary, and how to assign frequency values. However, the claim does not define how the frequency values are calculated, but merely gives some principles in features (c) and (d) related to the assignment of frequency values.

4.15 Distinguishing feature (c) essentially states that the first LDB ordered word in the list is also stored in the RDB, even if it was not used. Feature (d) states that the initial frequency value of a selected word in the RDB should be lower than that of the first word in the list.

As explained in the following, features (c) and (d) are directed towards the implementation of the "non-aggressive learning principle" described in the application on page 10, lines 33 to 37. This concurs with the appellant's submission in its letter dated 18 December 2014 (page 6).

According to the non-aggressive learning principle, "a single usage of a non-first word should not beat the first-word to the first position in the displayed selection list". The first and non-first words are described on page 9, lines 8 to 10 as being the first LDB ordered word in the list and a non-first LDB ordered word in the list respectively.

When the user selects a non-first LDB ordered word in the list for the first time, it is stored in the RDB and assigned a frequency value in both the process of document D2 and that of the claim. The next time a displayed list is created in D2, the word selected in the previous step could appear in the first position of the displayed list (see above points 4.8 and 4.10). Compared to the approach of D2, features (c) and (d) contribute to avoiding this by including also the first LDB ordered word in the list in the RDB and by assigning a newly inserted selected word a lower frequency value than that of the first word in the list. In this respect the Board remarks that since the first word in the list is often the first LDB ordered word in the list, feature (d) can be considered to support the non-aggressive principle.

In the opinion of the Board the non-aggressive learning principle reflects non-technical considerations about how likely it is that specific words will be input later by the user on the basis of knowledge of linguistic aspects, and independently of the problem solved by feature (a).

Features (c) and (d) are hence directed to the problem of implementing the non-technical model of word usage described as the "non-aggressive learning principle" or, equivalently, of avoiding a single usage of a non-first LDB ordered word resulting in it beating the first LDB ordered word to the first position in the displayed list.

The custom vocabulary of D2 is used in the same way as the RDB to build the displayed list, its order taking priority over that of the standard vocabulary. The skilled person would therefore immediately recognise that a modification of the order of words in the displayed list could be achieved by a corresponding change in the entries in the RDB.

From the above it follows that the skilled person, starting from document D2 and faced with the above-stated problem, would consider storing in the custom vocabulary not only the selected non-first LDB ordered word in the list but also the first LDB ordered word in the list (feature(c)), and assign them appropriate frequency values so that the next time the latter would appear in a higher position than the former in the displayed list.

Regarding the assignment of frequency values, the skilled person would consider, as one possible solution, assigning to a word the first time it is selected a lower frequency value than the frequency value of the first word in the list (feature (d)). The Board notes that feature (d) anyway constitutes a minor change to the prior art of document D2, where the initial frequency value is normally lower than or equal to that of the first word in the list (see point 4.84.8 above).

In the opinion of the Board, the skilled person starting from the prior art of document D2 would hence not require inventive skills to arrive at features (c) and (d).

4.16 The Board comes to the conclusion that the subject-matter of independent claim 1 does not involve an inventive step within the meaning of Article 56 EPC and that the appeal has to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.

Quick Navigation