SEMI-SUPERVISED PART-OF-SPEECH TAGGING

• US 20090157643A1
• Filed: 12/12/2007
• Published: 06/18/2009
• Est. Priority Date: 12/12/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gollapudi, Sreenivas, Panigrahy, Rina
• Granted Patent: US 8,099,417 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Relevant search results for a given query may be determined using click data for the query and the number of times the query is issued to a search engine. The number of clicks that a result receives for the given query may provide a feedback mechanism to the search engine on how relevant the result is for the given query. The frequency of a query along with the associated clicks provides the search engine with the effectiveness of the query in producing relevant results. Edges in a graph of queries versus results may be weighted in accordance with the click data and the efficiency to rank the search results provided to a user.

Claims

1. A method of ranking query results, comprising:

receiving a plurality of queries;

determining frequencies of the plurality of queries;

determining selected results of the plurality of queries;

determining an effectiveness of a query within the plurality of queries; and

determining a weight on an edge connecting the query to a result in accordance with a number of selected results and the effectiveness of the query.

2. The method of claim 1, further comprising:

normalizing the weight to determine a transition probability from the plurality of queries to the results.

3. The method of claim 2, wherein normalizing is determined by dividing the weight on an edge by the sum of weights of edges associated with the query.

4. The method of claim 1, further comprising:

parsing a query log to determine the frequencies of the plurality of queries and the number of selected results.

5. The method of claim 1, wherein determining the effectiveness further comprises summing the selected results for the query divided by a frequency of the query.

6. The method of claim 5, wherein determining the weight on an edge further comprises multiplying the effectiveness by the number of selected results.

7. The method of claim 1, further comprising:

ranking the query results in an order of relevance.

8. A method of ranking query results, comprising:

creating a bipartite graph of queries versus documents;

analyzing a frequency of the queries;

determining an effectiveness of the queries; and

weighting a plurality of edges in the bipartite graph in accordance with a frequency of results and the effectiveness of the queries.

9. The method of claim 8, further comprising:

normalizing the weight on the plurality of edges to determine a transition probability in the bipartite graph.

10. The method of claim 9, wherein normalizing is determined in accordance with the sum of all weights on all edges associated with a particular query.

11. The method of claim 8, further comprising:

parsing a query log to determine click data associated with the frequency of the queries.

12. The method of claim 11, wherein determining the effectiveness further comprises summing a number of clicked documents in response to a query divided by a frequency of the query.

13. The method of claim 12, wherein weighting the plurality of edges further comprises multiplying the effectiveness by the number of clicked documents.

14. The method of claim 8, further comprising:

walking the bipartite graph based on the weighting; and

ranking the query results in an order of relevance.

15. A system for ranking search queries, comprising:

a search engine that receives a plurality of queries over a network connection;

a query log for maintaining historical data about the plurality of queries and a plurality of results; and

a ranking engine that creates a bipartite graph of queries versus results and determines a weight on edges of the bipartite graph in accordance with a frequency of results for a particular query and the effectiveness of the particular query.

16. The system of claim 15, wherein the ranking engine normalizes the weight on the edges to determine a transition probability.

17. The system of claim 16, wherein the ranking engine normalizes the weight on the edges in accordance with the sum of all weights of all edges associated with the particular query.

18. The system of claim 16, wherein the ranking engine determines click data associated with the frequency of queries.

19. The system of claim 18, wherein the ranking engine determines effectiveness by summing a number of clicked results in response to the particular query divided by a frequency of the particular query.

20. The system of claim 15, wherein the ranking engine walks the bipartite graph based on the weighting and ranks the query results in an order of relevance.