T 0576/21 (Managing pre-computed search results/AMADEUS) of 21.11.2023

Summary of Facts and Submissions

I. The applicant appealed against the decision of the examining division refusing European patent application No. 14003698.9.

II. The contested decision cited the following documents:

D1:|WO 2013/160721 A1, 31 October 2013;|

D2:|WO 2006/074246 A2, 13 July 2006. |

The examining division decided that the subject-matter of independent claim 14 of the main request and of auxiliary requests 1, 2 and 3 lacked an inventive step over document D1.

III. In its notice of appeal, the appellant requested that the decision under appeal be set aside and that the case be remitted to the examining division with the order to grant a patent on the basis of the application documents according to the main request or, in the alternative, one of auxiliary requests 1, 2 and 3.

IV. In a communication accompanying the summons to oral proceedings, the board expressed the preliminary view that the subject-matter of claim 1 of all requests lacked an inventive step over document D1 and that claim 1 of auxiliary requests 2 and 3 lacked clarity.

V. With its written submissions in preparation for the oral proceedings, the appellant replaced its requests with a new main request and auxiliary requests A and B.

VI. During the oral proceedings, the appellant replaced its requests with a new, sole main request. At the end of the oral proceedings, the Chair announced the board's decision.

VII. The appellant's final requests were that the decision under appeal be set aside and that a patent be granted on the basis of the main request filed at the oral proceedings before the board, or that the case be remitted for further prosecution.

VIII. Independent claim 1 of the main request reads as follows:

"A method for managing pre-computed search results, the method being performed in a database environment (1), the database environment comprising:

- at least one search platform (4) for maintaining pre-computed search results, the pre-computed search results being subdivided into a plurality of shares of related pre-computed search results including a first share D;

- a re-computation controller (2) for controlling re-computation of the pre-computed search results on the basis of validity probabilities being associated with the pre-computed search results; and

- a computation platform (3) for re-computing the pre-computed search results;

the method comprising:

- determining (12), by the re-computation controller (2), a validity trend FORMULA/TABLE/GRAPHIC indicating a change rate of the validity probability of a pre-computed search result i over time, the pre-computed search result i being a member of the first share D, the validity trend FORMULA/TABLE/GRAPHIC being derived from at least three past re-computations of i;

- determining (13), by the re-computation controller, an instantaneous validity rate FORMULA/TABLE/GRAPHIC for the pre-computed search result i, the instantaneous validity rate FORMULA/TABLE/GRAPHIC being derived from the two latest re-computations of the related pre-computed search results included in the first share D, wherein the instantaneous validity rate FORMULA/TABLE/GRAPHIC is determined as a common value FORMULA/TABLE/GRAPHIC for the pre-computed search results in the first share D;

- in response to determining (14) a difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC exceeding a given extent with the instantaneous validity rate FORMULA/TABLE/GRAPHIC being greater than the validity trend FORMULA/TABLE/GRAPHIC, decreasing (15), by the re-computation controller (2), the validity probabilities associated with other pre-computed search results included in a second share D' being correlated to the first share D, wherein the amount of decrease depends on the amount of the difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC;

- wherein the related pre-computed search results within a share have identical or similar validity trends FORMULA/TABLE/GRAPHIC;

- wherein the correlation between the first share D and the second share D' is given by FORMULA/TABLE/GRAPHIC exceeding a given threshold, wherein FORMULA/TABLE/GRAPHIC denotes a covariance between past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D' over time, FORMULA/TABLE/GRAPHIC denotes a variance of past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC over time and therefore FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D', and

- issuing (16), by the re-computation controller (2), re-computation orders to the computation platform (3) to re-compute a part of the pre-computed search results with lower validity probabilities than other pre-computed search results with higher validity probabilities."

Claims 2 to 10 depend, directly or indirectly, on independent claim 1.

Independent claim 11 reads as follows:

"A re-computation controller (2) for managing pre-computed search results maintained by a search platform (4), the pre-computed search results being subdivided into a plurality of shares of related pre-computed search results including a first share D, the re-computation controller (2) comprising one or more processors (101) and a memory (102, 106, 111) including instructions that, when executed by the one or more processors (101), cause the re-computation controller (2) to control re-computation of the pre-computed search results on the basis of validity probabilities being associated with the pre-computed search results by:

- determining (12) a validity trend FORMULA/TABLE/GRAPHIC indicating a change rate of the validity probability of a pre-computed search result i over time, the pre-computed search result i being a member of the first share D, the validity trend FORMULA/TABLE/GRAPHIC being derived from at least three past re-computations of i;

- determining (13) an instantaneous validity rate FORMULA/TABLE/GRAPHIC for the pre-computed search result i, the instantaneous validity rate FORMULA/TABLE/GRAPHIC being derived from the two latest re-computations of the related pre-computed search results included in the first share D, wherein the instantaneous validity rate FORMULA/TABLE/GRAPHIC is determined as a common value FORMULA/TABLE/GRAPHIC for the pre-computed search results in the first share D;

- in response to determining (14) a difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC exceeding a given extent with the instantaneous validity rate FORMULA/TABLE/GRAPHIC being greater than the validity trend FORMULA/TABLE/GRAPHIC, decreasing (15) validity probabilities being associated with other pre-computed search results included in a second share D' being correlated to the first share D, wherein the amount of decrease depends on the amount of the difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC;

- wherein the related pre-computed search results within a share have identical or similar validity trends FORMULA/TABLE/GRAPHIC;

- wherein the correlation between the first share D and the second share D' is given by FORMULA/TABLE/GRAPHIC exceeding a given threshold, wherein FORMULA/TABLE/GRAPHIC denotes a covariance between past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D' over time, FORMULA/TABLE/GRAPHIC denotes a variance of past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC over time and therefore FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D', and

- issuing (16) re-computation orders to a computation platform to re-compute a part of the pre-computed search results with lower validity probabilities than other pre-computed search results with higher validity probabilities."

Claim 12 depends on independent claim 11.

Independent claim 13 reads as follows:

"A computer program product for managing pre-computed search results maintained by a search platform (4), the pre-computed search results being subdivided into a plurality of shares of related pre-computed search results including a first share D, the computer program product comprising:

a non-transitory computer-readable storage medium; and

instructions stored on the non-transitory computer-readable storage medium that, when executed by a processor (101), cause the processor (101) to control re-computation of the pre-computed search results on the basis of validity probabilities being associated with the pre-computed search results by:

- determining (12) a validity trend FORMULA/TABLE/GRAPHIC indicating a change rate of the validity probability of a pre-computed search result i over time, the pre-computed search result i being a member of the first share D, the validity trend FORMULA/TABLE/GRAPHIC being derived from at least three past re-computations of i;

- determining (13) an instantaneous validity rate FORMULA/TABLE/GRAPHIC for the pre-computed search result i, the instantaneous validity rate FORMULA/TABLE/GRAPHIC being derived from the two latest re-computations of related pre-computed search results included in the first share D, wherein the instantaneous validity rate FORMULA/TABLE/GRAPHIC is determined as a common value FORMULA/TABLE/GRAPHIC for the pre-computed search results in the first share D;

- in response to determining (14) a difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC exceeding a given extent with the instantaneous validity rate FORMULA/TABLE/GRAPHIC being greater than the validity trend FORMULA/TABLE/GRAPHIC, decreasing (15) validity probabilities being associated with other pre-computed search results included in a second share D' being correlated to the first share D, wherein the amount of decrease depends on the amount of the difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC;

- wherein the related pre-computed search results within a share have identical or similar validity trends FORMULA/TABLE/GRAPHIC;

- wherein the correlation between the first share D and the second share D' is given by FORMULA/TABLE/GRAPHIC exceeding a given threshold, wherein FORMULA/TABLE/GRAPHIC denotes a covariance between past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D' over time, FORMULA/TABLE/GRAPHIC denotes a variance of past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC over time and therefore FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D', and

- issue (16) re-computation orders to a computation platform to re-compute a part of the pre-computed search results with lower validity probabilities than other pre-computed search results with higher validity probabilities."

Claim 14 depends on independent claim 13.

Reasons for the Decision

1. The application

1.1 The background section of the application, on page 1, lines 11 to 17, explains that maintaining a cache of pre-computed search results which can be returned in response to search queries helps to shorten query response times. Since the data which forms the basis for the pre-computation of the search results changes over time, the cached pre-computed search result may get outdated and therefore have to be regularly updated by re-computing them (see also page 6, lines 12 to 22).

1.2 Since computational resources are generally limited, only a selected number of the pre-computed search results can be re-computed within a certain period of time (page 6, lines 24 to 29). Typically, update strategies for selecting the search results to be updated are based on probabilistic models for estimating the current validity probability of the pre-computed search results (page 7, lines 8 to 20).

1.3 The invention aims to improve the estimated validity probabilities by adjusting them when an "unexpected or unpredictable" event is detected which is not accounted for in the probability model (page 7, line 33, to page 8, line 16).

2. Admission into the appeal proceedings

The main request was filed during the oral proceedings before the board. Since, for the reasons given below, the board is satisfied that the amendments made overcome the board's objection of lack of inventive step, which was essentially based on the absence of a technical effect achieved by the distinguishing features, the board exceptionally admits the main request into the appeal proceedings (Article 13(2) RPBA 2020).

3. Amendments

3.1 Independent claim 1 is based on claim 1 as filed with the following amendments taken from the description as originally filed:

- the instantaneous validity rate FORMULA/TABLE/GRAPHIC is determined as a common value FORMULA/TABLE/GRAPHIC for the pre-computed search results in the first share D (page 17, line 29, to page 18, line 16);

- validity probabilities are adjusted by "decreasing ... the validity probabilities ..., , wherein the amount of decrease depends on the amount of the difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC" (page 21, line 32, to page 22, line 8);

- the related pre-computed search results within a share have identical or similar validity trends FORMULA/TABLE/GRAPHIC (page 11, lines 3 to 5);

- the correlation between the first share D and the second share D' is given by FORMULA/TABLE/GRAPHIC exceeding a given threshold, wherein FORMULA/TABLE/GRAPHIC denotes a covariance between past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D' over time, FORMULA/TABLE/GRAPHIC denotes a variance of past values of the instantaneous validity rate FORMULA/TABLE/GRAPHIC over time and therefore FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the first share D and FORMULA/TABLE/GRAPHIC denotes a standard deviation of the instantaneous validity rate FORMULA/TABLE/GRAPHIC of the second share D' (page 22, line 26, to page 23, line 6),

- re-computation order are issued "to re-compute a part of the pre-computed search results with lower validity probabilities than other pre-computed search results with higher validity probabilities" (page 25, lines 24 to 26).

3.2 Independent claims 11 and 13 were obtained by making the same amendments to originally filed independent claims 13 and 15, with a further amendment made to independent claim 13 to align it with independent claims 1 and 11.

3.3 Hence, the subject-matter of the independent claims does not extend beyond the content of the application as filed (Article 123(2) EPC).

4. The invention according to claim 1

4.1 Claim 1 is directed to a method for managing pre-computed search results.

According to the application, the pre-computed search results may be priced travel recommendations (see, for example, page 35, lines 14 to 27, and Figure 10).

4.2 The method is performed in a database environment which comprises a "search platform", a "re-computation controller" and a "computation platform".

The "search platform" maintains pre-computed search results. The "re-computation controller" controls re-computation, by the "computation platform", of the pre-computed search results on the basis of validity probabilities associated with the pre-computed search results.

4.3 The pre-computed search results are subdivided into a plurality of "shares" of "related" pre-computed search results. The related pre-computed search results i within a share have identical or similar "validity trends FORMULA/TABLE/GRAPHIC". The validity trend FORMULA/TABLE/GRAPHIC for a pre-computed search result i indicates a "change rate of the validity probability" of i. The re-computation controller derives it from at least three past re-computations of i.

The board notes that the estimated validity probability of a pre-computed search result i decreases as its age, i.e. the time that elapsed since its last re-computation, increases. Hence, the validity trend FORMULA/TABLE/GRAPHIC is the (estimated) rate at which the validity probability decreases over time.

4.4 In addition to the validity trends FORMULA/TABLE/GRAPHIC, the re-computation controller determines an "instantaneous validity rate FORMULA/TABLE/GRAPHIC" for each pre-computed search result i. The instantaneous validity rate FORMULA/TABLE/GRAPHIC is a common value FORMULA/TABLE/GRAPHIC for the whole share D and is derived from the two latest re-computations of the ("related") pre-computed search results included in the share D.

4.5 When the instantaneous validity rate FORMULA/TABLE/GRAPHIC exceeds the validity trend FORMULA/TABLE/GRAPHIC by a given extent for a pre-computed search result i in a first share D, the re-computation controller decreases the validity probabilities associated with the pre-computed search results in a second share D' which is "correlated" to the first share D. The amount by which the validity probabilities are decreased depends on the difference between the instantaneous validity rate FORMULA/TABLE/GRAPHIC and the validity trend FORMULA/TABLE/GRAPHIC.

4.6 Two shares D and D' are "correlated" if the correlation between the values of their instantaneous validity trends FORMULA/TABLE/GRAPHIC and FORMULA/TABLE/GRAPHIC over time, as measured by the well-known Pearson correlation coefficient (the covariance of the two variables divided by the product of their standard deviations), exceeds a given threshold.

4.7 The re-computation controller instructs the computation platform to re-compute a part of the pre-computed search results which are associated with lower validity probabilities than other pre-computed search results.

5. Inventive step

5.1 Document D1 discloses a method for managing pre-computed database query results (see page 1, lines 5 to 9). The pre-computed database query results may be priced travel offers (page 9, lines 5 to 11), which are "pre-computed search results" within the meaning of claim 1 (see point 4.1 above).

5.2 The method of document D1 is performed in a database environment comprising a "search platform" 3, a "computation platform" 2, and a re-computation controller in the form of "re-computation trigger platform" 4 (see Figure 1).

The search platform 3 maintains pre-computed query results (page 8, line 2 to 4). The re-computation trigger platform 4 controls re-computation, by the "computation platform", of the pre-computed query results on the basis of validity probabilities associated with the pre-computed query results (page 8, lines 6 to 10; page 5, lines 6 to 12).

5.3 An analyzer module 41 of the re-computation trigger platform determines probabilities indicating whether cached prices might be outdated on the basis of a probabilistic model represented by meta-data attributes (page 62, line 20, to page 63, line 3; page 63, lines 20 to 25; and page 64, line 28, to page 65, line 1).

The meta-data attributes include price volatility attributes, which are updated based on the number of differences between newly computed price results and their previous values (page 66, lines 7 to 15; page 72, lines 9 to 12). The price volatility attributes thus represent "validity trends", indicating a "change rate of the validity probability" of query results and being derived from a number of re-computations of the query results. When the system has been running for a sufficiently long period of time, they are based on at least three re-computations.

5.4 The re-computation trigger platform 4 instructs the computation platform 3 to re-compute a portion of the pre-computed query results which are associated with lower validity probabilities than other pre-computed query results (page 5, lines 6 to 12).

5.5 Hence, the subject-matter of claim 1 differs from the disclosure of document D1 in that:

- the pre-computed search results are subdivided into a plurality of shares of related pre-computed search results having identical or similar validity trends;

- the re-computation controller derives an instantaneous validity rate FORMULA/TABLE/GRAPHIC for a share D from the two latest re-computations of the pre-computed search results included in the share D;

- when the instantaneous validity rate for the share D exceeds the validity trend for a pre-computed search result i in the share by a given extent, the re-computation controller decreases the validity probabilities associated with the pre-computed search results in a correlated second share D' by an amount which depends on the difference between the instantaneous validity rate for the share D and the validity trend for the pre-computed search result i,

- where the shares D and D' are correlated if the correlation coefficient of the instantaneous validity trends FORMULA/TABLE/GRAPHIC and FORMULA/TABLE/GRAPHIC over time exceeds a given threshold.

These distinguishing features relate to the estimation of the validity probabilities indicating whether pre-computed results may be outdated and thereby to the determination of the pre-computed results with lower validity probabilities which are to be re-computed before pre-computed results with higher validity probabilities.

5.6 The appellant argued that the distinguishing features achieved the technical effect of a more efficient utilisation of the computation resources in that the computational resources were more likely used to re-compute actually invalid pre-computed search results than valid pre-computed search results. If the instantaneous validity rate in share D suddenly dropped, for example due to an unexpected event that was not reflected in the probabilistic model represented by the validity trends of the pre-computed search results, it was likely that the instantaneous validity rate in the correlated share D' showed the same behaviour. This meant that the current validity probabilities of the pre-computed search results in share D' were too high and should be reduced.

5.7 The board accepts that a more accurate estimation of the current validity probabilities of pre-computed (i.e. cached) search results leads to an improved trade-off between the computational resources used to re-compute/update cached search results and the actual validity of the cached search results because the strategy used to decide which cached search result to update next will take its decision on the basis of more accurate information. The board further accepts that such an improved caching mechanism in principle represents a technical effect (cf. decisions T 117/10, Reasons 4; T 729/21, Reasons 9.4).

5.8 In its communication the board expressed doubt, however, that the distinguishing features did indeed result in a better estimation of the validity probabilities of the pre-computed search results in the share D', in particular because claim 1 of the then main request did not define what it meant for pre-computed search results to be "related" and for shares to be "correlated".

Present claim 1 overcomes these concerns by specifying that related pre-computed search results have identical or similar validity trends and that shares are correlated if the development over time of the past values of their instantaneous validity rates show a sufficient correlation.

5.9 The board notes that there can be no general guarantee that a specific unexpected event which causes a drop of the instantaneous validity rate for a share D by invalidating a significant number of its pre-computed search results also has a significant effect on the validity of the pre-computed search results in a correlated share D'. Nevertheless, it is not unreasonable to assume that the effect of an unexpected event on the validity of pre-computed search results in different shares is similar to the effect of past unexpected events and is therefore reflected in the measured correlation over time between the instantaneous invalidity rates calculated for different shares. The board therefore has no sound reason to doubt that, on average, the distinguishing features do improve the accuracy of the validity probabilities.

5.10 Hence, the board accepts that the distinguishing features solve the technical problem of improving the trade-off between the computational resources used to re-compute pre-computed search results and the actual validity of the pre-computed search results.

5.11 Since neither document D1 nor document D2 discloses or suggests the distinguishing features, let alone as a solution to the objective technical problem, the board concludes that the subject-matter of claim 1 and of the corresponding independent claims 11 and 13 involves an inventive step over the available prior art (Article 56 EPC).

6. Remittal for further prosecution

6.1 In view of the above, the decision to refuse the application cannot be upheld.

6.2 However, the board has not yet examined whether the amendments made to the independent claims require adaptations to be made to the dependent claims or the description.

6.3 The case is therefore to be remitted to the examining division for further prosecution (Article 111(1) EPC).

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the examining division for further prosecution.