T 1089/17 (Ambiguous queries on online social networks/FACEBOOK) of 7.2.2020

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 13197982.5, published as EP 2 750 056 A1. The application claims a priority date of 31 December 2012.

II. The documents cited in the contested decision were as follows (as the numbering of documents D1 to D3 in point 2 of the contested decision is inconsistent with the later references in its reasons, the Board has used a numbering that is consistent with these reasons):

D1: US 2012/0059708 A1, published on 8 March 2012

D2: Delbru, R. et al., "Searching web data: An entity retrieval and high-performance indexing model", Web Semantics: Science, Services and Agents on the World Wide Web, vol. 10, January 2012, pp. 33-58

D3: Kirsch, S. M. et al., "Beyond the Web: Retrieval in Social Information Spaces", Lecture Notes in Computer Science, vol. 3936, pp. 84-95, 2006

D4: US 8,027,990 B1, published on 27 September 2011

III. The Examining Division refused the application for lack of inventive step regarding the subject-matter of claims 1 to 14 of the main request and of each of the first to third auxiliary requests and of claims 1 to 13 of the fourth auxiliary request in view of a notoriously known general-purpose computer system, known for example from D4, or the prior art disclosed in either of documents D1 or D2 when combined with D4.

IV. In its statement of grounds of appeal, the appellant requested that the decision be set aside and that a patent be granted on the basis of the main request or one of the four auxiliary requests considered in the contested decision. These were all resubmitted with the grounds of appeal.

V. In a communication under Article 15(1) RPBA 2007 accompanying the summons to oral proceedings, the Board raised objections under Articles 123(2) and 84 EPC and cited the following document:

D5: US 2012/0271831 A1, published on 25 October 2012

D5 is a US patent application by the appellant that is very similar to US patent application No. 12/763162, which was filed on 19 April 2010 and is mentioned in paragraph [61] of the originally filed description as being relevant for typeahead processes.

Furthermore, the Board expressed its provisional opinion that the subject-matter of claim 1 of the main request and the first to fourth auxiliary requests lacked inventive step in view of document D5.

VI. In response, the appellant submitted a fifth auxiliary request and arguments. Moreover, in view of the newly raised objections and the new document D5, it requested remittal of the case to the department of first instance.

VII. The oral proceedings were held as scheduled and the appellant was heard on relevant issues. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VIII. The appellant's final requests were that the decision under appeal be set aside and a patent be granted on the basis of the main request or one of the first to fourth auxiliary requests submitted with its letter dated 3 April 2017 and the fifth auxiliary request submitted with its letter dated 7 January 2020, and, as a procedural request, that the case be remitted to the department of first instance for further prosecution if the Board intended to base its inventive-step assessment on document D5.

IX. Claim 1 of the main request reads as follows:

"A method of operating an online social network (160), comprising:

accessing (510), by a computing device (160), a database (164) of the online social network (160), the database (164) implemented as a social-graph database (164) comprising a plurality of nodes (202, 204) and a plurality of edges (206) connecting the nodes (202, 204), each of the edges (206) between two of the nodes (202, 204) representing a single degree of separation between them, the nodes (202, 204) comprising:

a first node corresponding to a first user associated with the online social network (160); and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network (160);

by the computing device:

- receiving (520) from a client system (130) of the first user an unstructured text query comprising an ambiguous n-gram;

- identifying (530) in the social-graph database (164) a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;

- generating (540) a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query comprising a reference to the identified second node or identified edge;

- receiving (550) from the client system (130) of the first user a selected first structured query from the first set of structured queries, the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively; and

- generating (560) a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge."

X. Claim 1 of the first auxiliary request differs from claim 1 of the main request in that the following text was added after "by the computing device":

"executing in sequential order the steps of".

XI. Claim 1 of the second auxiliary request differs from claim 1 of the main request in that the text before "a social-graph database (164)" was replaced with:

"A computer-implemented method of operating a search engine of an online social network (160) comprising";

and in that the text "by the computing device:

- receiving (520) from a client system (130) of the first user an unstructured text query comprising an ambiguous n-gram;" was replaced with:

"characterized in that

the method involves the generation of structured queries, wherein each generated structured query contains references to social-graph elements, wherein the method further comprises:

by a computing device (160) executing in sequential order the steps of:

- accessing (510) the database (164);

- receiving (520) from a client system (130) of the first user a[ ]text query that is unstructured with respect to elements of the social-graph database, the query comprising an ambiguous n-gram corresponding to multiple social-graph elements;".

XII. Claim 1 of the third auxiliary request differs from claim 1 of the second auxiliary request in that it adds the following text at the end of the claim:

", wherein the structured queries are based on natural-language strings generated, by the computing device, by one or more non-terminal grammars, wherein non-terminal symbols of the non-terminal grammar are replaced with query tokens in which some of the query tokens may correspond to the identified second nodes or edges, wherein a string generated by the grammar is then used as the basis for a structured query containing references to the identified nodes or identified edges."

XIII. Claim 1 of the fourth auxiliary request differs from claim 1 of the second auxiliary request in that the word "and" was deleted after "edges, respectively" and in that it adds the following text at the end of the claim:

",

- receiving from the client system (130) of the first user a selected second structured query from the second set of structured queries; and

- generating one or more search results corresponding to the second structured query, wherein the second structured query further comprises reference to zero or more additional second nodes of the plurality of second nodes and zero or more additional edges of the plurality of edges, and wherein each search result corresponds to a second node of the plurality of second nodes that is connect[ed] to either the selected second node or one of the additional second nodes by one or more of either the selected edge or one of the additional edges."

XIV. Claim 1 according to the fifth auxiliary request differs from claim 1 of the main request in that the beginning of the claim before "the database (164) implemented" was replaced with:

"A method of operating an online social networking system (160), comprising:

accessing (510), by a computing device (160) of the system (160), a database (164) of the system (160),";

and in that the text after "by the computing device:" was replaced with:

"- receiving (520) from a client system (130) of the first user an unstructured text query comprising an ambiguous n-gram, the ambiguous n-gram corresponding to multiple social-graph elements;

- identifying (530) in the social-graph database (164) a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;

- generating (540) a first set of structured queries, each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query referencing the identified second node or identified edge;

- receiving (550) from the first user a selection of a first structured query from the first set of structured queries, the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively, and in response to receiving the selection from the first user, locking the ambiguous n-gram to the selected second node or selected edge to which the first structured query corresponds to; and

- in response to receiving a selection of a structured query from the first user, generating (560) a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge to which the first structured query corresponds to, and enabling the first user to select a second structured query;

- receiving from the first user a selection of a second structured query from the second set of structured queries; and

- generating one or more search results corresponding to the second structured query, and identifying content that is related to the second structured query,

- generating a search-results webpage including the one or more search results, and

- transmitting the search-results webpage to the user."

XV. The appellant's arguments, where relevant to the decision, are discussed in detail below.

Reasons for the Decision

1. Admissibility of the appeal

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

2. Oral proceedings before the Examining Division

2.1 According to point 9 of the summary of facts and submissions of the contested decision, oral proceedings were held on 11 November 2016 in the absence of the applicant. However, according to the electronic file, the applicant was informed by fax dated 10 November 2016 that the oral proceedings had been cancelled. The electronic file contains no minutes of oral proceedings before the department of first instance. In the oral proceedings before the Board, the appellant confirmed that oral proceedings before the Examining Division had not taken place.

2.2 While it is unacceptable that important procedural facts mentioned in the contested decision are incorrect, the Board considers that this issue has no consequences for the appeal proceedings in the present case. During the oral proceedings, the appellant agreed with the Board on this point.

The invention

3. The application relates to social graphs and performing searches for objects within a social-networking environment (description as originally filed, paragraph [1]).

3.1 A social-networking system, which may include a social-networking website, may enable its users (such as persons or organisations) to interact with it and with each other through it. The social-networking system may, with input from a user, create and store in the social-networking system a user profile associated with the user. The user profile may include demographic information, communication-channel information, and information on personal interests of the user. The social-networking system may also, with input from a user, create and store a record of relationships of the user with other users of the social-networking system, as well as provide services (e.g. wall posts, photo-sharing, event organisation, messaging, games, or advertisements) to facilitate social interaction between or among users (description, paragraph [2]).

3.2 Social-graph analysis views social relationships in terms of network theory consisting of nodes and edges. Nodes represent the individual actors within the networks, and edges represent the relationships between the actors (description, paragraph [4]).

3.3 The invention proposes a social-networking system that may, in response to a text query received from a user, generate structured queries that include references to particular social-graph elements. By providing suggested structured queries in response to a user's text query, the social-networking system may provide a way for users of an online social network to search for elements represented in a social graph based on their social-graph attributes and their relation to various social-graph elements (description, paragraph [5]).

For example, when a user enters the ambiguous search term "facebook" as part of the search query "people who like facebook", the online social network may propose several matching elements of the social graph such as "Facebook", "Facebook Culinary Team", "Facebook Camera", "Facebook HQ" or "Facebook Security" to the user for selection (see Figure 4C). If the user then selects one of the proposed matching elements (for example, "Facebook"), the system proposes a set of queries related to the selected graph element (for example, "People who work for Facebook", "People who like Facebook and Stanford"; see Figure 4D), from which the user can select one to be performed.

In claim 1 of each of the requests the matching elements are proposed in the form of a "first set of structured queries corresponding to an identified second node [...]" and the proposed set of queries related to the selected graph element is the "second set of structured queries [...] comprising a reference to the selected second node [...]".

The appellant's procedural request for remittal

4. In reply to the Board's communication, which introduced document D5, the appellant submitted a procedural request that the case be remitted for further prosecution to the department of first instance. In the oral proceedings, the appellant maintained this request in the event that the Board intended to base its inventive-step assessment on document D5.

5. However, the Board considers that, regarding the appellant's request for remittal, it has to judge whether remittal under Article 111(1) EPC is appropriate in view of the requirements of Article 11 RPBA 2020. According to this latter provision, the Board "shall not remit a case to the department whose decision was appealed for further prosecution, unless special reasons present themselves for doing so. As a rule, fundamental deficiencies which are apparent in the proceedings before that department constitute such special reasons."

In the present case, the Board is not aware of any fundamental procedural deficiencies. According to the explanatory remarks to Article 11 RPBA 2020 (see document CA/3/19), the aim of the new provision is to reduce the likelihood of a "ping-pong" effect between the boards of appeal and the departments of first instance, and consequent undue prolongation of the entire proceedings before the EPO. Hence, if all the issues can be decided without an undue burden, a Board should normally not remit the case.

The Board considers that, in the present case, remittal would be likely to result in a further appeal, as document D5 is clearly more relevant than the prior art on file. Furthermore, it is not an undue burden for the Board to continue the appeal proceedings with an assessment of inventive step over document D5, which in fact simplifies certain issues, for example regarding the interpretation of the claims.

In addition, the Board considers that, in the circumstances of the present case, the appellant should be able to deal with document D5 as prior art within the appeal proceedings. Document D5 is a patent application by the appellant itself and is similar to a document mentioned as relevant in the description (see point V. above). This view of the Board is confirmed by the fact that the appellant filed a further auxiliary request, the fifth auxiliary request, in reply to the introduction of document D5 into the appeal proceedings. Consequently, the appellant's right to be heard is not infringed by not remitting the case.

Consequently, the Board decides that the case is not remitted for further prosecution on the basis of document D5.

Main request

6. The appellant's request

In line with the itemisation used by the Examining Division and the appellant, claim 1 of the main request can be itemised as follows:

1 A method of operating an online social network, comprising:

accessing, by a computing device, a database of the online social network,

1.1 the database implemented as a social-graph database1.2 comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:2 a first node corresponding to a first user associated with the online social network; and3 a plurality of second nodes that each correspond to a concept3.1 or a second user associated with the online social network;4 by the computing device:

- receiving from a client system of the first user an unstructured text query4.1 comprising an ambiguous n-gram;5 - identifying in the social-graph database a plurality of second nodes or a plurality of edges corresponding to the ambiguous n-gram;6 - generating a first set of structured queries,6.1 each structured query from the first set of structured queries corresponding to an identified second node or identified edge, the structured query comprising a reference to the identified second node or identified edge;7 - receiving from the client system of the first user a selected first structured query from the first set of structured queries,7.1 the first structured query corresponding to a selected second node or selected edge from the identified second nodes or identified edges, respectively; and8 - generating a second set of structured queries,8.1 each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge. 6.1 Interpretation of claim 1

In the oral proceedings, the appellant argued, based on the description (paragraph [66]), that the expression "structured query" should be interpreted in a broad manner as meaning a text expression in a natural language that could be presented to users for selection, as users were not expected to be able to read queries in a formal query language. Moreover, structured queries contained references to nodes and/or edges of the social graph. The Board agrees with this interpretation, which is also consistent with the examples of structured queries according to paragraph [74] of the description and Figures 4C and 4D, for example. Thus, in the following, the Board uses this interpretation of "structured query".

Moreover, the appellant submitted that, according to claim 1 of the main request, the minimum requirements for an online social network were that it comprised a computing device and a social-graph database, as was explicitly defined in the claim. The Board accepts this argument in the context of the present case.

Finally, the appellant argued that the references to a "selected" node or edge in feature 7.1 had to be understood as referring to the indirect selection of nodes/edges by selecting a structured query according to feature 7. The Board adopts this view for its assessment of inventive step.

7. The contested decision

In its decision, the Examining Division stated that the subject-matter of claims 1 to 14 of the main request and of each of the first to third auxiliary requests and of claims 1 to 13 of the fourth auxiliary request lacked inventive step in view of a notoriously known general-purpose computer system, known for example from D4, or the prior art disclosed in either of documents D1 or D2 when combined with D4.

7.1 In its statement of grounds of appeal, the appellant argued among other points that the operation and function of the claimed search engine may be considered to lie in a technical field. Furthermore, the appellant argued that the assessment of the technical character and inventive step of claim 1 of the main request as presented in the contested decision was improper to an extent such that setting aside the contested decision was justified. Moreover, it argued that no proper search and examination had been provided in relation to the dependent claims.

7.2 The Board agrees with the appellant that not all aspects of the reasoning of the contested decision are convincing. In particular, none of the cited documents discloses a search process which maps natural language text input to elements of a social-graph database in the context of a social network. The Board considers that document D5, which is a patent application by the appellant, is more relevant than the prior art cited by the Examining Division. Consequently, the Board prefers to use document D5 as the starting point for assessing inventive step.

8. Inventive step using D5 as the starting point

8.1 Document D5 discloses an integrated social network environment and a social graph based on the social network environment that includes nodes representing users and concepts in the social network environment as well as edges that define or represent connections between such nodes (paragraph [0002]; Figures 1, 2A, 2B and 3). According to D5, a computing device accesses a database of the online social network (paragraphs [0026] to [0029] and [0059] to [0071]; Figures 2B and 6; claim 1). Hence, document D5 discloses feature 1 of claim 1. As document D5 discloses implementing the database as a social-graph database (see paragraph [0033]; Figure 2B, reference sign 206), it also discloses feature 1.1 of claim 1. Moreover, document D5 discloses a graph structure with nodes and edges according to feature 1.2 (see paragraphs [0016], [0017], [0033] and [0034]; Figure 3), the nodes comprising user and concept nodes as specified in features 2, 3 and 3.1 (see paragraphs [0016], [0017], [0033], [0034] and [0041]; claim 1).

8.1.1 Document D5 discloses in paragraphs [0018] and [0059] to [0062] and Figures 2B and 6 that, when a user enters text into a form box of a graphical user interface on the client computer, a typeahead feature attempts to match the string of textual characters being entered in the form box to strings of characters (for example names) corresponding to existing concepts (or users) and corresponding concept (or user) nodes in the social graph. When a match is found, the typeahead feature automatically populates the form box with a node name (or other identifier) of the existing node and causes an edge to be created between the matching existing node and the user's node (paragraph [0061]).

According to the description of the application (paragraph [67]), an n-gram is a contiguous sequence of n items from a given sequence of text or speech. The items may be characters, phonemes, syllables, letters, words, base pairs, prefixes, or other identifiable items from the sequence of text or speech. Thus, the text entered by a user into a form box according to document D5 can be viewed as an n-gram which is ambiguous in the sense that it may match a plurality of graph elements.

Consequently, D5 discloses features 4, 4.1 and 5 of claim 1.

The Board is aware that feature 4 refers to an "unstructured text query", whereas document D5 refers to filling text into a form box (see D5, Figure 4D, reference sign 442). However, the claim wording covers such a case, and according to the application the query is also filled into a box of a web page (Figure 3 of the application, reference sign 350). Furthermore, the text fragment filled into the form in D5 is used for querying the social-graph database. Hence, the Board is not convinced by the appellant's argument that document D5 did not disclose inputting a text string for the purpose of querying a social graph.

8.1.2 Document D5 discloses, in paragraph [0061] and Figures 4D and 6, that the typeahead process on the client displays a drop-down menu that displays names of matching existing concept profile pages (called "hubs" in D5) and respective nodes (e.g. a hub named "weight lifting" is displayed when a user has entered the characters "wei"). Users can then select the displayed name corresponding to a node. By way of example, upon clicking "weight lifting", the typeahead process causes the web browser to auto-populate the form with "weight lifting". Consequently, document D5 also discloses features 6, 6.1, 7 and 7.1 of claim 1.

The Board agrees with the appellant that document D5 does not disclose features 8 and 8.1 of claim 1 of the main request.

8.2 The claimed invention therefore differs from the method disclosed in document D5 in that it includes features 8 and 8.1.

8.3 In its statement of grounds of appeal, page 37, third paragraph from the bottom, and page 39, last paragraph, the appellant submitted that the technical effect of the claimed invention was to provide an improved human-machine interaction to guide and support the user as regards querying a social-graph database even if highly ambiguous search queries were involved. In its reply to the Board's communication, the appellant argued that document D5 did not suggest that the typeahead function was used for querying a database. Moreover, D5 did not suggest the claimed two-fold generation of structured queries where a second set of structured queries was generated after a manual disambiguation of search query terms by users.

8.4 However, the Board is not convinced by these arguments in view of its above analysis of document D5 and the following considerations. The distinguishing features 8 and 8.1 generate a second set of structured queries. The queries in this second set contain a reference to a selected node or edge, but are not further defined.

The distinguishing features have the effect of generating a set of exemplary queries regarding a selected element of the social graph. In this respect, the Board observes that the application discloses ranking the structured queries based on advertising sponsorship (description, paragraph [0075]), which seems to suggest that the generated queries may serve a non-technical purpose and result from business considerations.

The claimed generation of queries according to features 8 and 8.1 does not contribute to a "further" technical effect. In particular, the Board does not agree that the human-machine interaction is improved, as no interaction between the user and the system after the disambiguation of the entered data is claimed. The distinguishing features do not involve any further interaction or the display of the generated second set of structured queries to the user.

Moreover, the Board considers that defining a natural language query is per se not a technical task, but lies in a non-technical field. As the claim is entirely silent regarding the user interface for entering search queries, the Board is not convinced that the claimed method solves a technical problem in the area of user interfaces.

8.5 The appellant argued that the fact that claimed subject-matter had some relation to "semantic" aspects did not inevitably imply that it was of non-technical character. Non-technical character could only be affirmed if absolutely no further technical considerations, for example related to the database/search engine and their structure and/or function, were involved.

8.5.1 The Board is not convinced that the distinguishing features involve any "further technical considerations" (see opinion G 3/08, OJ EPO 2011, 10, Reasons 13.5.1), as the generation of the second set of queries is based on non-technical considerations regarding the desired query semantics in the context of the social graph. The Board observes that the social graph, which is known from document D5, constitutes social data not serving a technical purpose, and the distinguishing features do not define whether or how the social graph as a data structure is used to generate the second set of structured queries.

8.6 The appellant also argued that, according to the Board's decision T 2230/10 of 3 July 2015, points 3.9 and 3.10 of the Reasons, taking the technical structure of the underlying database and/or search engine into account may make a technical contribution. The invention in that case concerned the addition of keywords selected from a user's long-term interest to disambiguate the query. According to the appellant, T 2230/10 held only the specific case where the added keywords were unrelated to the technical structure of the underlying database to be non-technical. In the present case, the situation was different, as the generated search term related to the underlying graph structure of the database.

8.6.1 However, the social graph is already known from document D5, and the distinguishing features 8 and 8.1 define the generation of the second set of structured queries only in terms of non-technical semantic aspects. Consequently, the Board considers that features 8 and 8.1 are not about exercising technical control over the functioning of the search engine in the sense of decision T 2230/10. Hence, the Board is not persuaded by the appellant's arguments.

8.7 In view of the above, the distinguishing features do not contribute to the solution of a technical problem and cannot be considered for the assessment of inventive step (see decision T 154/04 published in OJ EPO 2008, 46, point 5(f) of the Reasons, for example).

9. Therefore, the subject-matter of claim 1 of the main request lacks inventive step (Articles 52(1) and 56 EPC).

First to fourth auxiliary requests

10. Claim 1 of each of the first to fourth auxiliary requests additionally recites essentially the following features:

(A) executing the steps of the method in sequential order (first auxiliary request);

(B) the method operates a search engine of an online social network (second auxiliary request);

(C) the method involves the generation of structured queries, wherein each generated structured query contains references to social-graph elements (second auxiliary request);

(D) the text query is unstructured with respect to elements of the social-graph database, and the ambiguous n-gram corresponds to multiple social-graph elements (second auxiliary request);

(E) the structured queries are based on natural-language strings generated, by the computing device, by one or more non-terminal grammars, wherein non-terminal symbols of the non-terminal grammar are replaced with query tokens in which some of the query tokens may correspond to the identified second nodes or edges, wherein a string generated by the grammar is then used as the basis for a structured query containing references to the identified nodes or identified edges (third auxiliary request);

(F) receiving from the client system of the first user a selected second structured query from the second set of structured queries; and

generating one or more search results corresponding to the second structured query, wherein the second structured query further comprises reference to zero or more additional second nodes of the plurality of second nodes and zero or more additional edges of the plurality of edges, and wherein each search result corresponds to a second node of the plurality of second nodes that is connect[ed] to either the selected second node or one of the additional second nodes by one or more of either the selected edge or one of the additional edges (fourth auxiliary request).

11. Inventive step

11.1 First auxiliary request

11.1.1 In the oral proceedings, the appellant agreed with the Board that the first auxiliary request does not introduce a further limitation over document D5, and submitted that this auxiliary request had instead been introduced into the proceedings to clarify the technical character.

11.1.2 The Board considers that feature (A) does not change its assessment of inventive step as it has already interpreted claim 1 of the main request as being directed to a sequential execution of the method steps. Moreover, D5 discloses such a sequential execution order (see Figure 6, for example).

11.1.3 It follows that the subject-matter of claim 1 of the first auxiliary request lacks inventive step (Articles 52(1) and 56 EPC).

11.2 Second auxiliary request

11.2.1 The appellant argued that the second auxiliary request was an attempt to overcome the Examining Division's objections regarding a lack of technical character. The additional features of the second auxiliary request equated to a technical implementation, at least in terms of further functional definitions. Moreover, they clarified the meaning of structured queries and ambiguity in connection with n-grams.

11.2.2 Feature (A) has been already considered above in the context of the first auxiliary request. The clarification according to feature (C) does not change the Board's assessment of inventive step, because the Board has already interpreted the generation of structured queries according to feature (C) in its assessment of inventive step for claim 1 of the main request. Moreover, feature (D) is known from document D5 (see Figure 4D; paragraphs [0060] and [0061]).

As to feature (B), operating a search engine, the Board considers that the social networking system of Figure 2B of document D5 can be viewed as a search engine and that the typeahead process disclosed in document D5 (for example, see Figure 6, reference sign 608, and description, paragraph [0060]) already operates a search engine (the social networking system) for matching a typed-in character string to social-graph elements.

For the sake of completeness, the Board observes that applying the teaching of document D5 to inputting text queries for searching by means of a search engine was obvious at the relevant date, as the use of text queries for searching data collections was well known.

Moreover, the wish to offer users a way of searching using the user interface disclosed in D5 is as such a non-technical aim. According to the established case law of the boards of appeal, when assessing inventive step in accordance with the problem/solution approach, an aim to be achieved in a non-technical field may legitimately appear in the formulation of the problem as part of the framework of the technical problem to be solved as a constraint that has to be met (see decisions T 641/00, OJ EPO 2003, 352; T 154/04, OJ EPO 2008, 46). For a skilled person facing the problem of how to provide a way of searching to users of the method of document D5, the addition of an input field for search queries (as in Figure 6E of the application, for example) would have been an obvious routine design, as such search query input fields were well known.

Consequently, the method of claim 1 of the second auxiliary request lacks inventive step (Articles 52(1) and 56 EPC).

11.3 Third auxiliary request

The third auxiliary request differs from the second auxiliary request by additionally reciting feature (E).

11.3.1 Interpretation of feature (E)

As discussed in the oral proceedings, in the light of the description, paragraphs [0072] and [0073], the Board interprets feature (E) as relating to the use of context-free grammars.

11.3.2 The appellant argued that the method of the third auxiliary request used a grammar as a formal description of a correspondence between non-terminal symbols and (technical) database items. While a grammar could have a linguistic meaning, in the context of claim 1 it did not relate to linguistic concepts but to database entries. Thus, the additional features of the third auxiliary request made a technical contribution. The appellant referred to the description, starting from paragraph [0072], as a basis for feature (E). The first and second sets of structured queries according to claim 1 were generated using the grammars according to feature (E).

11.3.3 The Board considers that context-free grammars were well known. This was not disputed by the appellant.

The use of a grammar to generate natural language strings lies in the non-technical field of linguistics and does not involve any "further technical considerations" going beyond "merely" finding an algorithm (see opinion G 3/08, OJ EPO 2011, 10, Reasons 13.5 and 13.5.1). In particular, the Board observes that it is not apparent that the design of an appropriate grammar involves any technical considerations related to the internal functioning of a computer system. Hence, this aspect can be added to the objective technical problem as a non-technical constraint.

Document D5 already discloses replacing ambiguous search terms by unambiguous references to social-graph elements (see paragraph [0061], for example). Consequently, the skilled person, when starting from D5, was faced with the objective technical problem of how to implement the generation of structured queries corresponding to natural language queries, the natural language queries being generated according to a context-free grammar.

To solve this problem, the skilled person would consider replacing a non-terminal grammar symbol that represented an element of the social graph with a reference to a graph element matching a search term, for example, as a matter of routine software development, i.e. without exercising inventive skill. It was then straightforward to use the generated string as the basis for a structured query, as a structured query is essentially characterised by the fact that it comprises a reference to a graph element.

11.3.4 Consequently, and considering the reasons provided above for the second auxiliary request, the subject-matter of claim 1 of the third auxiliary request lacks inventive step (Articles 52(1) and 56 EPC).

11.4 Fourth auxiliary request

The fourth auxiliary request differs from the second auxiliary request by additionally reciting feature (F).

11.4.1 In the oral proceedings and in its statement of grounds of appeal, the appellant argued that the overall effect of the fourth auxiliary request related to operating a search engine and receiving search results. Thus, the request related to the internal operation of a search engine. Feedback was provided to the user for determining the user's intent when searching a social-graph database.

When a user entered a search query in Google's search engine (see document D4), a query suggestion made by the search engine might not result in a match in the database. By contrast, the invention according to the fourth auxiliary request provided assistance to the user based on the structure and content of the social-graph database. Thus, the method according to the fourth auxiliary request provided users with a real option to search content in the database.

11.4.2 The Board agrees with the appellant that the method of the fourth auxiliary request is directed to searching content in the social-graph database. The selection of a structured query is performed twice with the aim of generating queries based on the structure and content of the social-graph database. According to feature (F), a user selection of a structured query from the second set is received and the selected query is then executed to generate search results.

The fact that the user queries generate results corresponding to elements of the social graph is a non-technical aspect that relates to the desired semantics of the query and the non-technical content of the database. Neither the semantics of the query (i.e. what to search) nor the semantic content of the search results contributes to technical character. It follows that the Board does not agree with the appellant that these aspects are technical.

Using the social-graph structure to produce the search queries and respective results according to the user requirements is obvious for the skilled person, especially since document D5 already discloses suggesting terms based on the content of the social-graph database. Feature (F) does not provide further details of a technical implementation.

Furthermore, the Board notes that it was an obvious further development of the online social network disclosed in D5 to propose to users, in response to their manual disambiguation of search terms as regards the social graph, a set of further queries which relate to a user-selected element of the social graph. In particular, such a generated set of queries may be proposed to avoid some users being unable to formulate a meaningful query. Proposing a set of queries (which may or may not be of actual interest to the user) to avoid users needing to formulate queries themselves is regarded as a straightforward solution that does not involve exercising inventive skill.

As discussed in the oral proceedings, the generation of search results corresponding to a query was as such well known at the priority date, and the claim does not specify any technical details with respect to the implementation of the generation of results.

11.4.3 In view of the above, and considering the Board's objection to the second auxiliary request, the subject-matter of claim 1 of the fourth auxiliary request lacks inventive step (Articles 52(1) and 56 EPC).

Fifth auxiliary request

12. Admission

Since the set of claims of the fifth auxiliary request was a response to objections raised for the first time in the Board's preliminary opinion, and in particular to the introduction of document D5, and as this set of claims could be dealt with without adjournment of the oral proceedings, the Board admitted it into the appeal proceedings.

13. Inventive step

13.1 A comparison between the wording of claim 1 according to the main request and that of claim 1 according to the fifth auxiliary request (see point XIV.) leaves no doubt that claim 1 of the fifth auxiliary request essentially adds the following features:

(i) the ambiguous n-gram corresponds to multiple social-graph elements;

(ii) in response to receiving the selection from the first user, locking the ambiguous n-gram to the selected second node or selected edge to which the first structured query corresponds;

(iii) in response to receiving a selection of a structured query from the first user, generating a second set of structured queries, each structured query of the second set of structured queries comprising a reference to the selected second node or selected edge to which the first structured query corresponds, and enabling the first user to select a second structured query;

(iv) receiving from the first user a selection of a second structured query from the second set of structured queries;

(v) generating one or more search results corresponding to the second structured query, and identifying content that is related to the second structured query;

(vi) generating a search-results web page including the one or more search results;

(vii) transmitting the search-results web page to the user.

13.2 The appellant argued that the fifth auxiliary request addressed clarity objections and the inventive-step objection over document D5 raised by the Board. According to claim 1 of the fifth auxiliary request, carrying out the search involved a two-fold generation and selection of structured queries before the query was carried out and before search results were presented to the user.

Document D5 (as well as the other prior-art references on file) at best suggested a typeahead function as a means for supporting a user in inputting text. However, none of the prior-art documents suggested implementing a two-fold generation of structured queries to support users in querying a graph-based database by guiding the users based on database content. Therefore, claim 1 of the fifth auxiliary request involved an inventive step.

13.3 The Board considers that feature (i), which corresponds essentially to a part of feature (D), is already disclosed in document D5, as discussed above for the second auxiliary request.

13.4 Feature (ii) refers to "locking the ambiguous n-gram to the selected second node or selected edge". This wording essentially specifies that the system uses the particular element of the social graph that is obtained by the user's selection of a query from the first set of structured queries to generate the second set of queries. According to feature (iii), each query of this second set comprises a reference to the particular "locked" element of the social graph.

13.4.1 The Board considers that features (ii) to (v) essentially specify that the second set of queries is generated based on a manually identified element of a set of elements of the social graph that matches an ambiguous search term, and that the system receives a user selection of a query of the second set for execution and generates the results. These features are similar to feature (F), and have been taken into account in the inventive-step assessment of claim 1 of the fourth auxiliary request.

As argued with regard to feature (F) of the fourth auxiliary request, the Board considers that it was obvious to use the node or edge identified by the user as being relevant for a search to generate further queries that are proposed to users in order to avoid the users having to formulate queries themselves.

It follows that, at the priority date, the skilled person would have considered adding features (ii) to (v) to the method disclosed in document D5 without exercising inventive skill.

13.5 As to features (vi) and (vii), the Board observes that document D5 already discloses that the online social network uses web pages accessed over the internet (paragraphs [0003] and [0018], Figure 4D). Moreover, as discussed in the oral proceedings, the Board considers that, at the priority date, the generation of search results for a query, the generation of a search-results web page and the transmission of search results to users were well-known features. Hence, features (vi) and (vii) provide no basis for acknowledging inventive step over document D5.

13.6 Consequently, when considering the above in combination with the Board's assessment of inventive step for the higher-ranking requests, the Board concludes that claim 1 of the fifth auxiliary request lacks inventive step (Articles 52(1) and 56 EPC).

Conclusion

14. As none of the appellant's requests can form the basis for the grant of a patent, the appeal is to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.