T 0943/16 (Tier assignments/MICROSOFT TECHNOLOGY LICENSING) 25-06-2020
Download und weitere Informationen:
Determining quality of tier assignments
Inventive step - claimed subject-matter not rendered obvious by D1
Remittal to the department of first instance - special reasons for remitting the case (yes)
Summary of Facts and Submissions
I. The appeal lies from the decision of the Examining Division to refuse European patent application No. 08868759.5 for lack of inventive step in the subject-matter of the independent claims of a main and an auxiliary request over prior-art document
D1: US 2005/0021530 A1, published on 27 January 2005.
In an obiter dictum the Examining Division also expressed the opinion that the claimed subject-matter was not inventive over the prior art acknowledged in the application.
II. In the statement of grounds of appeal, the appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of a main or a first auxiliary request, corresponding to the main request and auxiliary request considered in the decision under appeal, or a second auxiliary request filed with the grounds of appeal.
III. In a communication pursuant to Rule 100(2) EPC, the Board expressed its preliminary opinion that the decision under appeal could not be upheld and that document D1 was not a suitable starting point for assessing inventive step. The Board recognised more differences from the acknowledged prior art than those identified in the obiter dictum and did not agree with the Examining Division's assessment that the distinguishing features did not achieve any technical effect. Since there were doubts concerning the completeness of the search, the Board intended to remit the case for further prosecution. The appellant was invited to indicate whether it agreed to a remittal along the lines indicated by the Board without first holding oral proceedings.
IV. With a letter of reply the appellant agreed to remittal for further prosecution without holding oral proceedings.
V. Claim 1 of the main request reads as follows:
"A computer implemented method, comprising:
receiving user history data including queries that were issued by users and search results provided to the users in response to the queries; and
generating an indication of quality of a tier assignment used to store searchable digital items in a tiered storage system, wherein higher tiers have faster access and retrieval times when compared to lower tiers, and wherein the indication is based at least in part upon a subset of the user history data;
wherein the tier assignment indicates to which of several tiers the searchable digital items are assigned;
wherein the tiered storage system is a search engine index; and
wherein the method further comprises generating an improved tier assignment based at least in part upon the indication of quality, and assigning digital items to the tiered storage system based at least in part upon the improved tier assignment."
Claims 2 to 6 depend directly or indirectly on claim 1.
VI. Claim 7 of the main request reads as follows:
"A system, comprising:
a receiver component (106) that is configured to receive user history data (104) including queries that were issued by users and search results provided to the users in response to the queries; and
a quality indicator component (108) that is configured to determine an indication of quality of a tier assignment used to store digital items that are searchable, wherein the quality indicator component (108) is configured to generate the indication based at least in part upon a subset of the user history data (104) and the tier assignment indicates where digital items are to be stored in a tiered storage system, wherein higher tiers have faster access and retrieval times when compared to lower tiers;
wherein the indication is indicative of the quality of a tier assignment for a search engine index;
wherein the system further comprises an update component that is configured to generate an improved tier assignment based at least in part upon the indication of quality; and
wherein the system is configured to assign digital items to the tiered storage system based at least in part upon the improved tier assignment."
Claims 8 to 13 depend directly or indirectly on claim 7.
VII. The claims of the auxiliary requests are not relevant to the present decision.
VIII. The appellant's arguments, where relevant to this decision, are addressed in detail below.
Reasons for the Decision
1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.
The invention
2. The invention concerns the problem of assigning searchable digital items to tiers in a tiered storage system serving as a search-engine index, with higher tiers offering faster retrieval but having smaller capacity.
2.1 According to the application, user history data is used to generate a quality indication of a tier assignment, where a tier assignment indicates to which of several tiers searchable digital items are assigned. An improved tier assignment is generated on the basis of the indication of quality and/or the user history data and is used to update a tiering policy to assign items to tiers in the tiered system (see international publication, paragraphs [0006] and [0008], original claims 2 to 7).
2.2 The user history data may be obtained by monitoring user interaction and may include, for example, queries issued by the users, search results provided to the users or search results selected by the users (paragraphs [0006] and [0021]). The indication of quality of a tier assignment may conform to a defined tier assignment quality metric on the basis of which an improved tier assignment is optimised (paragraph [0008]).
2.3 The indication of quality of a tier assignment is calculated by the quality indicator component which includes four determiner components to determine weight, load, tier and utility with respect to a query. The determiner components determine a weight assigned to a query, the system load observed when the query is executed, a probability that a certain tier will be the last tier searched over for digital items (where retrieval is performed at the highest tier possible), and an indication of search result quality (utility) when retrieval ends in a certain tier (paragraphs [0023] to [0027] and Figure 2). The indication of the quality of a tier assignment can be determined by the following algorithm (paragraphs [0028] to [0034] and original claim 10)
FORMULA/TABLE/GRAPHIC
where
- TQ(T(D),L,Q') is a measure of tier assignment quality for a current system load L with respect to the "set of observed queries" Q';
- D is the set of all digital items di that are to be stored in k tiers T1... Tk with corresponding capacities;
- T(D) = {t(di),...,t(di)} is the overall set of tier assignments t(di) of each item di;
- w(q) is a weight (e.g., relative importance) of a query q in Q';
- P(t|q,T(D),L) is the probability that the t-th tier will be the lowest tier visited during retrieval under the current system load L;
- Utility(t,R(q),T(D)) is a measure of search result quality obtained when retrieval ends in the t-th tier; and
- R(q) is a relevant result set for query q in Q'.
Main request
3. Inventive step over document D1
3.1 Document D1 concerns the allocation of resources to various applications in a data center which includes a collection of server-class data processing systems. The data center allows applications to be hosted on a collection of shared computing resources according to the resource needs of the applications and the architecture of each application. For example, a common architecture for a web service system is a tiered structure including a first tier of web servers, a second tier of application servers, and a third tier of database servers. Within each tier, multiple machines may be provisioned to share the incoming workload (paragraphs [0001] to [0003]).
The method of allocating resources to a plurality of applications in document D1 starts by collecting transaction data or instrumentation data for work requests processed by the applications and determining an associated workload level for work requests processed by the applications. For each application, a resource requirement is then determined for the associated workload levels and service level metric, and a subset of resources is determined by taking account of the resource requirement. As a final step, the resources are automatically reconfigured according to the assigned subset of resources for each application (page 11, claim 1 and paragraphs [0018] and [0043]).
Therefore, document D1 relates to the allocation of resources in the form of computing systems to applications with a tiered architecture.
3.2 The Board agrees with the appellant that allocation of computing resources to tiered applications is conceptually quite different from assignment of data items to tiers in a tiered storage system.
In a system such as that in document D1, each application may use data items and each computer system offers storage, but the allocation of computer systems to applications in a tiered architecture does not necessarily correspond to the assignment of the application's data items to the computer systems' storage systems. None of the passages of D1 cited in the contested decision discloses assigning digital items to storage systems.
3.3 In the decision under appeal, the Examining Division considered that the method of claim 1 differed from the disclosure of document D1 in that
(1) the indication of quality used to generate the tier assignment is based at least in part on a subset of the user history data including queries that were issued by users and search results provided to the users in response to the queries,
(2) higher tiers have faster access and retrieval times when compared with lower tiers.
According to the decision under appeal, the feature "tier assignment used to store searchable digital items in a tiered storage system" in claim 1 was disclosed in paragraph [0028] of document D1, the step of generating an improved tier assignment was disclosed in paragraph [0042] and the feature "the tier assignment indicates to which of several tiers the searchable digital items are assigned" was disclosed in paragraph [0045] and Figures 1 and 3.
Figure 1 shows servers in a data center, and applications running on the servers (see also paragraph [0013]). Paragraph [0028] discloses minimising some criteria such as the mean response time of a request, and assigning sessions comprising mostly small requests to different servers from those comprising large requests. Paragraph [0042] refers to allocating hierarchically organised server resources to tiered applications in such a way that communications delays are minimised and bandwidth capacity constraints are satisfied.
With reference to Figure 3, paragraphs [0045] to [0050] describe "an example arrangement for gathering data to be used in analyzing resource requirements and allocations for applications hosted by a data center". The resources of the data center are configured to support a tiered architecture for processing web transactions. The first tier of the web transaction processing architecture is a load balancer 306. The second and third tiers of resources are a web server farm 308 (erroneously indicated as "318" in the drawing) and an application server farm 314. The application servers 314 host the application logic that processes web transactions. The load balancer distributes web transactions amongst the web servers 308. The file system 318 may be used to store the web pages that are served to the user and configuration information for the web and application servers.
However, the description of this embodiment does not disclose any direct association between the web transactions and the "web pages that are served to the user". In addition, it is clear that both the second and third tiers of servers share the file system 318 and database 316. Therefore, the distribution of web transactions amongst the web servers in the tiered system in this example does not correspond to the assignment of data items to a tiered storage system.
3.4 The Board therefore concludes that document D1 does not disclose at least features (1), (2) and a "tier assignment used to store searchable digital items in a tiered storage system".
Furthermore, the Board agrees with the appellant that the idea of document D1 is very remote from that of the invention in this case. Starting from document D1, the skilled person would have to completely change the type of allocation performed in the system in D1 in order to arrive at the invention in this case. Document D1 is therefore not a suitable starting point for assessing inventive step.
3.5 The invention of claim 1 is therefore not rendered obvious by the disclosure of document D1. The same applies to corresponding independent claim 7.
Inventive step over the acknowledged prior art
4. In paragraphs [0003] and [0004] of its background section, the present application acknowledges a prior-art method of generating an improved tier assignment for storing searchable digital items in a tiered storage system, where the higher tiers have faster access and retrieval times when compared to lower tiers, the tier assignment indicates to which of several tiers the searchable digital items are assigned, and the tiered storage system is a search engine index. The acknowledged prior-art method further includes a step of assigning digital items to the tiered storage system based at least in part on the improved tier assignment.
The Board therefore agrees with the appellant that the prior art acknowledged in the background section of the application is a more promising starting point than document D1.
4.1 According to paragraph [0004], the acknowledged prior-art method takes into account "the web page's relative importance as determined by some metric, such as a static rank of the web page", or the number of links to a web page, in order "to select a tier of an index in which to place" the web page.
4.2 The method of claim 1 differs from the acknowledged prior-art method in that
(a) user history data is received which includes queries that were issued by users and search results provided to the users in response to the queries;
(b) an indication of quality of a tier assignment is generated based at least in part on a subset of the user history data; and
(c) the improved tier assignment is generated based at least in part on the indication of quality.
4.3 In the contested decision's obiter dictum the Examining Division expressed the view that the claimed method differed from the acknowledged prior art in that it included features (1) (see point 3.2 above). The distinguishing features were dictated by "considerations on particular quality criteria arbitrarily decided from a technical point of view, the effects of which criteria or assignment remaining essentially speculative in view of the definition of the quality defined criteria in the claims and the assumptions on the future, unknown requests". On page 4 of the decision under appeal, in the context of its inventive-step assessment starting from document D1, the Examining Division expressed the opinion that at the level of generalisation of the claim, in which the tier assignment relied only in part on undefined quality criteria, the effects (if any) of the tier assignment policy were essentially implementation-dependent. No additional technical effect was achieved by providing a different tier assignment according to features (1), since the generated tier assignment did not change the properties of the computer system, and since the effects of the generated assignment depended on future, unknown queries issued by users. Any effect provided by the tier assignment thus appeared to be essentially speculative. The use of any quality criteria based e.g. on the quality of results to decide on a resource allocation belonged to non-technical requirements specifications and was arbitrary from a technical point of view.
4.3.1 In its statement of grounds of appeal, the appellant argued that in many technical fields a technical effect could only be ascertained at a statistical level since the systems involved were too complex to allow for easily predictable results. Index design for search engines was one example of such a technical field. The appellant drew a parallel with the medical and pharmaceutical fields.
Efficiency of a search engine (retrieval time of relevant search results) depended on the assignment of the searchable items in the tiered search engine index. The claimed subject-matter made it possible to improve a given tier assignment and, thus, to improve the efficiency of the search engine. For a given future query, the effect might not be able to be conclusively determined. For a large number of future queries, however, the effect was statistically measurable.
The claimed method changed the assignment of digital items to the tiered storage system, or in other words, their storage location.
The effect was not implementation-dependent. Assigning the digital items in accordance with the improved tier assignment increased the search engine's efficiency.
In the case in hand, the tier assignment was determined for purposes involving technical considerations, namely for providing a search engine index that allowed the search engine to retrieve relevant search results in less time, or in other words, allowed the search engine to optimise retrieval times.
According to the appellant, in view of the acknowledged prior art the claimed invention solved the problem of providing an improved method for tiering web pages in a search engine index.
4.4 The Board is not persuaded by the reasons given in the contested decision as to why the distinguishing features were not based on technical considerations and did not contribute to a technical effect.
In the claimed method, history data is used for predicting the future use or workload of the system. The Board accepts that, in the present context, analysing history data enables a statistically reliable prediction of the system's operation and does not lead to purely speculative results. Since the claim explicitly and clearly specifies that higher tiers have faster access and retrieval times than lower tiers, an improved tier assignment means improved average access times. Moreover, since the history data is purposively used to improve access times, this improvement is not merely the physical consequence of a non-technical decision but a technical effect to be taken into account in the assessment of inventive step (T 697/17 of 17 October 2019, reasons 5.2.3 to 5.2.5; T 1965/11 of 24 March 2017, reasons 5.1).
4.5 It still has to be determined whether adding distinguishing features (a) to (c) to the acknowledged prior-art method would involve an inventive step. Document D1, which is the sole prior-art document cited in the present case, would not be taken into consideration for solving a technical problem related to tiered storage systems.
Remittal for further prosecution
5. The Board does not find the Examining Division's reasoning convincing and therefore the decision under appeal cannot be upheld.
5.1 Under Article 111(1) EPC, the Board may either proceed further with the examination of the application or remit the case to the examining division for further prosecution.
According to Article 11 RPBA 2020, a case is not to be remitted to the department whose decision was appealed unless special reasons present themselves for doing so. In the Board's view, this provision has to be read in conjunction with Article 12(2) RPBA 2020, which stipulates that it is the primary object of the appeal proceedings to review the decision under appeal in a judicial manner.
5.2 It is not clear whether the features considered non-technical by the Examining Division were searched. Since the only document cited in the search report is less relevant than the prior art cited in the application, there is good reason to doubt that the search was complete. Under these circumstances, the Board does not find itself in a position to assess inventive step.
5.3 It follows that special reasons for remitting the case within the meaning of Article 11 RPBA 2020 present themselves (see also T 565/17 of 15 June 2020, reasons 5.2 to 5.4).
5.4 Accordingly, the Board decides to exercise its power under Article 111(1), second sentence, EPC and remit the case for further prosecution.
Order
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the department of first instance for further prosecution.