System and method for query expansion

• US 7,685,119 B2
• Filed: 12/20/2006
• Issued: 03/23/2010
• Est. Priority Date: 12/20/2006
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Riise, Soren, Campbell, Bruce, Jones, Rosie, Patel, Devesh, Stipp, Eugene, Richardson-Bunbury, David
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US11/642,207
• Publication Number:
  US 20080154856A1
• Time in Patent Office: 1,189 Days
• Field of Search: 707/3, 707/5, 707/4, 707/6, 707/7, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system is disclosed for expanding a user query based on user learned popularity rankings. User queries often have no exact match, resulting in a user having to refine or abandon the search. The disclosed system obtains popularity rankings based on the content of a user query. The system expands the user query based on the popularity rankings. Thereafter, query results based on the expanded user query may be provided to the user. The system also regularly learns from user behavior and adapts the popularity rankings according to the learned information.

Claims

1. A method for augmenting a user query, comprising:

receiving the user query;

obtaining a first popularity ranking associated with the user query, where the user query comprises a geographic component;

associating the geographic component of the user query with a first geographic locality;

identifying a plurality of neighboring geographic localities comprising geographic localities in proximity to the first geographic locality, where one of the plurality of neighboring localities is a first neighboring geographic localities identified based on the first popularity ranking;

ranking, using a processor, the plurality of neighboring localities based on the first popularity ranking, where ranking the plurality of neighboring geographic localities comprises weighting each geographic locality of the plurality of neighboring geographic localities based on the first popularity ranking;

generating, using the processor, an augmented query by augmenting the user query based on the first popularity ranking, the first neighboring geographic locality identified based on the first popularity ranking, and the ranking of the plurality of neighboring geographic localities, where the augmenting of the user query comprises expanding the user query to include the weighted geographic localities of the plurality of neighboring geographic localities; and

providing the augmented query to a search engine.

2. The method of claim 1, further comprising disambiguating the user query based on the first popularity ranking.

3. The method of claim 1, further comprising obtaining neighboring locality popularity rankings associated with each geographic locality of the plurality of neighboring geographic localities, where the ranking is based on the neighboring locality popularity rankings.

4. The method of claim 1, where the first popularity ranking comprises a reference count.

5. The method of claim 1, where the first popularity ranking comprises user click behavior.

6. The method of claim 1, where the first popularity ranking comprises query refinement data.

7. The method of claim 1, further comprising obtaining a second popularity ranking associated with the user query, where the user query comprises a first component and a second component, and where the first popularity ranking is obtained based on content of the first component and the second popularity ranking is obtained based on content of the second component.

8. The method of claim 7, further comprising augmenting the user query based on the second popularity ranking.

9. The method of claim 1, further comprising:

monitoring user behavior; and

augmenting the first popularity ranking based on the user behavior.

10. The method of claim 1, where the first popularity ranking comprises user inferred preferences related to the first geographic locality and to the first neighboring geographic locality.

11. The method of claim 1, where the first neighboring geographic locality identified based on the first popularity ranking was not included in the user query, and where the augmenting of the user query comprises expanding the user query to include the first neighboring geographic locality identified based on the first popularity ranking.

12. A query expansion system for augmenting a query, the query expansion system comprising:

a processor;

a memory coupled to the processor, the memory comprising instructions that cause the processor to;

obtain a first popularity ranking associated with a received user query;

associate the received user query with a first geographic locality where the received user query comprises a geographic component;

identify a plurality of neighboring geographic localities comprising geographic localities that are proximate to the first geographic locality;

identify, based on the first popularity ranking, a first neighboring geographic locality from among the plurality of neighboring geographic localities;

rank the plurality of neighboring geographic localities based on the first popularity ranking, where ranking the plurality of neighboring geographic localities comprises weighting each geographic locality of the plurality of neighboring geographic localities based on the first popularity ranking;

generate an augmented query by augmenting the received user query based on the first popularity ranking, the first neighboring geographic locality identified based on the first popularity ranking, and the ranking of the plurality of neighboring geographic localities, where the augmenting of the received user query comprises expanding the received user query to include the weighted geographic localities of the plurality of neighboring geographic localities; and

provide the augmented query to a search engine.

13. The query expansion system of claim 12, where the first popularity ranking comprises user click behavior.

14. The query expansion system of claim 12, where the memory further comprises instructions that cause the processor to:

monitor a user'"'"'s response to search results generated from the augmented query; and

augment the first popularity ranking based on the user'"'"'s actions.

15. The query expansion system of claim 12, where the received user query is associated with the first geographic locality based on the first popularity ranking.

16. The query expansion system of claim 12, where the first neighboring geographic locality identified based on the first popularity ranking was not included in the user query, and where the augmenting of the received user query comprises expanding the user query to include the first neighboring geographic locality identified based on the first popularity ranking.

17. A system for augmenting a query comprising:

an augmenting server configured to;

obtain a first popularity ranking associated with a received user query;

associate the received user query with a first geographic locality;

identify neighboring geographic localities based on the first popularity ranking, where the neighboring geographic localities are in proximity to the first geographic locality;

rank the identified neighboring geographic localities based on the first popularity ranking, where ranking the identified neighboring geographic localities comprises weighting each of the identified neighboring geographic localities based on the first popularity ranking;

generate an augmented query by augmenting the received user query based on the first popularity ranking and on the ranking of the identified neighboring geographic localities, where augmenting the received user query comprises expanding the received user query to include the weighted neighboring geographic localities; and

provide the augmented query to a search engine;

a web server configured to receive results from the search engine and present the results to a user; and

a learning server configured to;

monitor a user'"'"'s response to the search results; and

augmenting the first popularity ranking based on the user'"'"'s actions.

18. The system of claim 17, where the learning server is further configured to:

scan a corpus of data;

track a number of times a term appears in the corpus of data; and

augment the first popularity ranking based on the number of times the term appears in the corpus of data.

19. The system of claim 17, where the augmented query is augmented to include one or more of the neighboring geographic localities based on the first popularity ranking.

20. The system of claim 17, where the augmenting server is further configured to disambiguate the received user query based on the first popularity ranking.

21. The system of claim 17, where the augmenting server is further configured to:

generate a result ranking; and

order the search results based on the result ranking.