Query Intent in Information Retrieval

• US 20110289063A1
• Filed: 05/21/2010
• Published: 11/24/2011
• Est. Priority Date: 05/21/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Craswell, Nick, Szummer, Martin, Radlinski, Filip
• Granted Patent: US 8,380,723 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/953 Querying, e.g. by the use of web search engines
• CPC Class Codes: G06Q 30/00 Commerce

Abstract

Inferring query intent in information retrieval is described. In an example reformulations of an initial query by a user are used to create a query neighborhood. In the example, the query neighborhood is used to identify a set of possibly related queries. First and higher order reformulations of the initial query may be used to expand the query neighborhood. In an example precision can be improved by reducing the query neighborhood to more closely related queries for example, two queries can be connected if they are often clicked for the same document. In an example two queries can be connected using a random walk and all pairs of queries that are not connected by a random walk of less than a fixed threshold are removed. The connected queries can be used to form clusters and weights can be applied in order to determine the most likely related queries.

Claims

1. A method for use at a search engine arranged to receive queries and to provide search results for those queries, the search results comprising links to documents, the method comprising:

receiving a query;

accessing query reformulation data and using that data to create a query neighborhood around the received query, the query neighborhood being a graph data structure in memory comprising a node representing the received query and links connecting that node to other nodes representing observed reformulations of that query;

accessing evidence about queries related to the received query comprising a record of query-document pairs;

using a processor to filter the query neighborhood by editing the graph data structure on the basis of the accessed evidence to produce and store in memory a reformulation graph;

using the reformulation graph to identify queries related to the received query.

2. A method as claimed in claim 1 wherein accessing evidence comprises accessing a record of query-document pairs which is a click graph comprising nodes connected by edges, each node representing any of a document and a query and each edge representing at least one observed user click action.

3. A method as claimed in claim 1 wherein accessing evidence about related queries comprises accessing a record of query-document pairs where the queries are anchor text being clickable text in a hyperlink and a document paired to a query is the target of the link.

4. A method as claimed in claim 1 wherein accessing query reformulation data comprises accessing a record of valid reformulations, each valid reformulation being a query made by each of at least two distinct users, followed within a specified time period, by another query which is the same for each user.

5. A method as claimed in claim 1 which comprises editing the reformulation graph to remove connected groups of nodes that are smaller than a specified size.

6. A method as claimed in claim 1 wherein accessing query reformulation data comprises accessing a record of queries which has been filtered to remove frequent queries.

7. A method as claimed in claim 1 wherein filtering the query neighborhood comprises adding or removing links in the graph data structure such that only pairs of queries with a similarity above a threshold are connected, the similarity being measured using the record of query-document pairs.

8. A method as claimed in claim 7 which comprises measuring the similarity of pairs of queries using a random walk on the graph data structure.

9. A method as claimed in claim 2 wherein filtering the query neighborhood comprises identifying pairs of queries with a random walk similarity in the click graph that is above a threshold.

10. A method as claimed in claim 1 which further comprises assigning weights to the reformulations in the reformulation graph using a random walk process that takes into account at least the number of times each reformulation was observed.

11. A method as claimed in claim 10 which further comprises clustering the nodes in the reformulation graph using the assigned weights.

12. A method as claimed in claim 11 which comprises combining the weights of the queries in each cluster to obtain an importance score for that cluster.

13. A method as claimed in claim 1 wherein the queries are advertisement key words and wherein the method comprises providing the identified queries as advertisement key word suggestions to an advertisement system.

14. A method as claimed in claim 1 comprising providing the identified queries as query suggestions to a user of the search engine.

15. A query generation apparatus comprising:

an input arranged to receive a query to be issued to a search engine to retrieve documents;

a memory holding a query neighborhood for the received query, the query neighborhood being a graph data structure comprising a node representing the received query and links connecting that node to other nodes representing observed reformulations of that query;

a processor arranged to access evidence about queries related to the received query comprising a record of query-document pairs;

the processor being arranged to filter the query neighborhood by editing the graph data structure on the basis of the accessed evidence to produce a reformulation graph;

the processor being arranged to use the reformulation graph to generate queries related to the received query.

16. An apparatus as claimed in claim 15 which is integral with the search engine and wherein the search engine is arranged to produce the record of query-document pairs and to observe the reformulations of the query.

17. An apparatus as claimed in claim 15 wherein the queries are advertisement key words.

18. A method for use at a search engine arranged to receive queries and to provide search results for those queries, the search results comprising links to documents, the method comprising:

receiving a query;

accessing query reformulation data and using that data to create a query neighborhood around the received query, the query neighborhood being a graph data structure in memory comprising a node representing the received query and links connecting that node to other nodes representing observed reformulations of that query;

accessing a click graph comprising nodes connected by edges, each node representing any of a document and a query and each edge representing at least one observed click;

using a processor to filter the query neighborhood by editing the query neighborhood on the basis of the click graph to produce and store in memory a reformulation graph;

using the reformulation graph to identify queries related to the received query.

19. A method as claimed in claim 18 wherein filtering the query neighborhood comprises computing similarities between pairs of queries in the click graph using a random walk.

20. A method as claimed in claim 18 which comprises editing the reformulation graph to remove connected groups of nodes that are smaller than a specified size.