T 1109/24 (Incremental search/ADEIA GUIDES) 05-09-2025

Application

1. The invention concerns a user interface system for incrementally finding and presenting content items in response to keystrokes entered by a user using a keypad with "overloaded keys". Each overloaded key has a corresponding set of alphanumeric symbols (see application as filed, paragraph [0007], Figure A).

1.1 A database stores the content items and corresponding descriptive terms and phrases (paragraph [0007]). Searches can be based on multiple word prefixes, e.g. "gar keillor" for "Garrison Keillor". A user enters a "multiple prefix query string" where the input string includes "ambiguous encoded text" due to the overloaded keys. As the user enters the query string to describe the desired item, the system incrementally searches for matches with the ambiguous prefix input (paragraphs [0004], [0005] and [0020]).

1.2 The system uses "mapping logic" which operates in accordance with a "defined error model" for generating orthographic, typographic or N-gram variants of terms. The mapping logic includes "dynamic intersection logic", which compensates for errors in the input of an individual term, for example errors of addition, deletion, substitution, or transposition. The variants are used to find the content items most likely matching the terms and phrases as they are entered by the user (paragraphs and [0007] to [0010], [0029] and [0034]).

1.3 In some embodiments, the error model is applied to the descriptive terms and phrases stored in the database to pre-compute their variants (paragraphs [0004] and [0028] to [0032], Figure 3). In other embodiments, the error model is applied in "real time" to the terms and phrases as they are entered by the user (paragraph [0041]).

Admission of claims request

2. The present claims of the sole request on file were submitted in response to fresh objections under Articles 84 and 123(2) EPC raised by the board in its communication and at the oral proceedings and overcome all the outstanding objections. The board thus recognises the presence of exceptional circumstances under Article 13(2) RPBA and admits the request into the appeal proceedings.

Clarity, support and basis

3. Claim 1 specifies a user interface system as described in paragraphs [0007] to [0010] of the description and further including features described in other passages of the description as filed. Paragraphs [0007] to [0010] disclose a user interface system including a database, input logic, mapping logic comprising dynamic intersection logic and presentation logic essentially as claimed.

4. Compared to that passage of the description, claim 1 further restricts the "string" built by the input logic and used in the mapping logic and dynamic intersection logic to a "multiple prefix (query) string", and it restricts the first and second sets of alphanumeric symbols identified by the dynamic intersection logic, as described in paragraph [0010], to the first and second prefixes. Basis for this is found in paragraphs [0033], [0036] and [0037].

5. Claim 1 further specifies that the mapping logic comprises trie pre-computation logic and trie descent logic. The pre-computation of a trie is disclosed in Figure 3, which describes a method for calculating the pre-computed variants and building a trie by applying error models (see paragraphs [0028], [0031] and [0032] in combination with paragraph [0041]). Figure 5 discloses how a trie is used to find the top records matching the user's incremental entries (see also paragraph [0037]). The description then further discloses, in paragraph [0042], that the mapping logic can "handle variants of the search input string and/or of the descriptive terms and phrases" created according to the described error models. As an example, the mapping logic can generate input strings in real time. In either embodiment (i.e. either real-time generated or pre-computed variants) "the mapping logic handles variants and performs a database lookup to determine the most likely content items...". From these passages, the skilled person understands that the mapping logic is used for pre-computing the trie and descending the trie using trie pre-computation logic and trie descent logic as specified in claim 1.

6. Basis for the trie pre-computation and trie descent logic features is thus found in paragraphs [0041] and [0042], read in the light of the disclosure of a trie in step 305 of Figure 3 (see also paragraphs [0028] to [0032]). The trie descent logic is disclosed in Figure 5 (see also paragraph [0037]).

7. Taking the above into account, the board concludes that claim 1 satisfies the requirements of Article 123(2) EPC.

8. Since the description of the present application and that of the parent application are identical, claim 1 also satisfies the requirements of Article 76(1) EPC.

9. The objections under Article 84 EPC raised in the board's preliminary opinion were overcome by amendment. Claim 1 was amended to clearly explain the function of the error model in the claimed system. The specification of the dynamic intersection logic was amended to refer to the first and second prefixes instead of the first and second set of alphanumeric symbols in the string, which were considered unclear and not supported by the description. The board is thus satisfied that claim 1 is clear and supported by the description in accordance with Article 84 EPC.

Inventive step - documents D1 and D2

10. Document D1 discloses a system for facilitating text input using a reduced keypad, such as numeric keys, and more particularly a system for spell checking words corresponding to key sequences entered using the reduced keypad (paragraph [0001]).

10.1 Document D1 explains that one common way of entering text on a device with a reduced keyboard is the "single-tap approach" in which the user presses the numeric key associated with the desired letter once, even though the numeric key may be mapped to three or four different letters. The device attempts to discern the word that the user intended to enter, based on the number sequence. Each number sequence is mapped to a common word that corresponds to the sequence. This can involve a "disambiguation approach" in which the user is shown a number of different words that correspond to the entered number sequence, in order of decreasing frequency of use (paragraphs [0003], [0005] and [0008]).

The system disclosed in D1 uses the single-tap approach for spell-checking based on comparisons of the entered number sequences with number sequences within a dictionary (paragraph [0016]).

The user enters a number sequence corresponding to a word using the single-tap approach. The device employs "word-determining logic" to determine the word or words corresponding to the numeric key input entered by the user on the numeric keypad and display the results of its determination on the display (paragraphs [0031] and [0032]).

The word-determining logic of the system of D1 can make the determination of the words based on the context of the numeric key input. It examines the words - or their corresponding number sequences - that have already been entered to the left and/or the right of the current numeric key input to assist in determining what word the user intended to enter with the current numeric key input (paragraphs [0031] and [0032]).

The dictionary is stored as a tree, such that there is a distinguished root node of the tree. Each node of the tree other than the root node contains a letter, indicating that that letter is appended to any path from the root node through that point (paragraph [0090]).

10.2 The subject-matter of claim 1 differs from the system of document D1 at least in that:

d1 the database comprises content items and descriptive terms that characterise the content items, rather than just including words;

d2 the query string is a multiple prefix query string;

d3 the mapping logic further comprises dynamic intersection logic for

identifying a first and a second set of content items corresponding respectively to a first and a second prefix in the multiple prefix string;

including content items appearing in both the first and second sets of content items in the most likely matching content items corresponding to the incremental entries;

wherein the dynamic intersection logic is invoked when the number of most likely matching content items mapped by the trie descent logic is below a predetermined threshold;

d4 the trie is pre-computed in accordance with a defined error model, the error model being based on the known layout of overloaded keys.

10.3 In the decision under appeal, the examining division recognised three distinguishing features Delta1, Delta2 and Delta3 with regard to claim 1 of the refused main request. Features Delta1 and Delta2 correspond essentially to features d1 and d2. Feature Delta3 corresponds to feature d3 before the amendments were introduced to replace the "first/second set of alphanumeric symbols in the string" with the "first/second prefix in the in the multiple prefix string". The examining division was of the opinion that none of features Delta1, Delta2 and Delta3 solved a technical problem. The three features were considered individually to merely fulfil the user requirements of incorporating additional data into the database or dictionary, using multiple prefixes in queries and receiving additional or different results for a better search. The subjective concept of "better search" was not a technical effect according to decision T 598/14. The objective technical problem was the implementation of these non-technical user requirements in the system of document D1, which did not involve any inventive activity on the part of a skilled person.

10.4 The board is not convinced by this reasoning. While it is sometimes stated that the proper question to be answered when assessing inventive step is not whether the skilled person could have modified the closest prior art to arrive at the claimed invention but whether they would have done so (Case Law of the Boards of Appeal, 11th edition, 2025, I.D.5), the board notes that the "would" question in fact presupposes that the "could" question is answered in the affirmative (see e.g. decision T 667/91, Reasons 5).

It is often easier to establish that the skilled person could modify the closest prior art to arrive at the invention than to show that they would have done so. For example, if the starting point for assessing inventive step is a general-purpose computer and the claimed invention essentially amounts to implementing a computer program as such, the "could" question requires little or no justification.

However, the "could" question cannot be ignored in cases where there is not self-evidently a realistic path or "workable route" from the starting point to the claimed invention. That is the case if the distinguishing features cannot reasonably be combined with the closest prior art to obtain the claimed invention. In such a situation, the invention is not rendered obvious by that prior art and the question whether the distinguishing features achieve a technical effect over the closest prior art is essentially meaningless.

10.5 In the present case, the claimed invention accepts a "multiple prefix query string", including at least two prefixes and encoding a number of ambiguous or "overloaded" keystrokes, and searches a database of descriptions of content items to determine the list of content items that most likely correspond to what the user is looking for. The system of document D1, on the other hand, accepts an ambiguous input string to search a dictionary of words and locate the word that most likely corresponds to the user's intention. Starting from document D1 and equating the words in the dictionary with content items (described by themselves, i.e. the dictionary words are their own "descriptive term"), it would make no sense to look up a word using two prefixes, let alone look up a word using two separate prefixes and take the intersection of the matches.

Alternatively, starting from document D1 and adding a step of querying a database of content items with descriptive terms, the skilled person would arrive at a system that allows the user to enter a text string using ambiguous input, maps the ambiguous input to the text string intended by the user (i.e. what the system of D1 already does) using the trie computed from the dictionary, and then uses this regular text string as a query. But the mapping logic and intersection logic of claim 1 instead perform the disambiguation directly on the descriptive terms using a trie pre-computed from the descriptive terms of the database.

Hence, the board does not see how the skilled person could modify the system disclosed in document D1 to arrive at the claimed invention without fundamentally departing from the essential teaching of document D1, i.e. there does not appear to be a realistic path from document D1 to the invention. And the contested decision is silent on this point.

10.6 Therefore, the subject-matter of claim 1 is not rendered obvious by document D1 alone (Article 56 EPC).

10.7 Document D2 explains how Google interprets queries including multiple search terms. It is quite unrelated to the problem addressed by the claimed invention of finding and presenting search results in response to keystrokes entered by a user on an input device having overloaded keys. Document D2 does not disclose features d1, d3 and d4, or any index structures used by the search engine, let alone using a trie to perform such an incremental search of ambiguous input.

10.8 In view of this, the system of claim 1 is not rendered obvious by document D2 or by the combination of documents D1 and D2, either (Article 56 EPC).

10.9 For completeness, the board notes that the system of claim 1 is not rendered obvious by a general-purpose computer alone or in combination with any of the documents D1 and D2. Since facilitating input with a reduced keyboard includes technical aspects, the distinguishing features over a general-purpose computer would not be a mere computer program as such. For the reasons given above, combining a general-purpose computer with any of the disclosures of D1 or D2 would not render the claimed invention obvious (Article 56 EPC).

Priority and document D3

11. The present application cites in paragraph [0033] the US patent application No. 11/136,261, which was published on 11 May 2006 (see document D3 cited in section III. above) and thus before the present application's filing date of 21 November 2006 but after its priority date. According to paragraph [0033] of the present application, document D3 discloses an "example of a trie structure used for incremental searching" of television content using reduced text input. If the claimed priority right were to be found invalid for the claimed invention, then document D3 might be relevant prior art for the claimed invention (Articles 54(2) and 89 EPC).

12. Since a preliminary review of the priority application and the earlier application reveals differences between the two disclosures, it is not immediately apparent that both relate to the "same invention" within the meaning of Article 87(1) EPC. Without a more detailed assessment, it can thus not be excluded that the claimed priority right is invalid for the claimed invention and that document D3 is part of the state of the art and relevant to the question of patentability of the claimed invention. This was not contested by the appellant at the oral proceedings before the board.

13. The assessment of the validity of the priority claim and patentability in view of document D3 does not appear to have been dealt with in the first instance proceedings. In view of the primary object of the appeal proceedings to review the decision under appeal in a judicial manner (Article 12(2) RPBA) and the need to provide the appellant adequate opportunity to be heard, the board does not consider it appropriate to deal with these issues for the first time in the appeal proceedings.

Remittal for further prosecution

14. The subject-matter of claim 1 fulfils the requirements of Articles 84, 76(1) and 123(2) EPC and is inventive over the prior art cited during the examination proceedings. However, the board did not decide on the questions of priority and patentability in view of document D3. The case is thus to be remitted for further prosecution to the department of first instance (Article 111(1) EPC).