Managing cached search result: technical

The invention relates to managing pre-computed search results. The Examining Division alleged that the invention lacked an inventive step as it saw no technical problem that was solved over the prior art.

However, the applicant argued that distinguishing features achieved the technical effect of more efficient utilization 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.

The Board noted that a more accurate estimation of the current validity probabilities of 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. Improved caching mechanism, in principle represents a technical effect.

While there can be no general guarantee that a specific unexpected event also has a significant effect on the validity of the search results, it is not unreasonable to assume that the effect of an unexpected event in different shares is similar to the effect of past unexpected events and is therefore reflected in the measured correlation over time. The board therefore has no sound reason to doubt that, on average, the distinguishing features do improve the accuracy of the validity probabilities

Here are the practical takeaways from the decision T 0576/21 (Managing pre-computed search results/AMADEUS) from November 21, 2023 of the Technical Board of Appeal 3.5.07.

Key takeaways

The invention

The Board summarized the invention as follows:

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).

Is it patentable?

In the decision under appeal, the Examining Division refused the application as it lacked inventive steps in document D1 (WO 2013/160721 A1), and the problem to be solved referred to a non-technical decision.  The Board identified the distinguishing feature as follows:

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 λ^D 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 λ^D and λ^D’ 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.

With respect to technical effect, the Board agreed with the appellant as follows

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.

The Board considered the subject-matter was inventive. Therefore, the case is remitted with the order to grant a patent.

More information

You can read the full decision here:T 0576/21 (Managing pre-computed search results/AMADEUS) from November 21, 2023 of the Technical Board of Appeal 3.5.07.

Please share this article if you enjoyed it!