Ranking functions using an incrementally-updatable, modified naïve bayesian query classifier

• US 7,620,634 B2
• Filed: 07/31/2006
• Issued: 11/17/2009
• Est. Priority Date: 07/31/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramsey, William D.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/496,373
• Publication Number:
  US 20080028010A1
• Time in Patent Office: 1,205 Days
• Field of Search: 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Methods of ranking documents on a network using an incrementally-updatable system are disclosed. Computer readable storage media having stored computer-executable instructions for performing a method of ranking documents on a network using an incrementally-updatable system are also disclosed. Further, computing devices containing at least one application module comprising application code for performing methods of ranking documents on a network using an incrementally-updatable system are disclosed.

Claims

1. A computer readable storage medium having stored computer-executable instructions that when executed by a computer cause the computer to:

rank documents on a network in response to a user inputted search query comprising one or more search query terms utilizing an incrementally-updatable query classifier for ranking the documents based on usage data;

display documents to the user ranked by the query classifier based on usage data comprising pre-calculated values #(w_i, Asset) and log[#(w_i, Asset)]stored for each of the search query terms and pre-calculated values #(Asset), log[#(Asset)] and Σ

#(w_i, Asset) stored for each of the documents; and

update the usage data in response to the user selecting a document for viewing by;

updating count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset),

calculating values log[#(Asset)] and log[#(w_i, Asset)], and

storing updated usage data replacing the pre-calculated values, wherein;

#(Asset) represents a number of times that a given document on the network is selected for viewing,

log[#(Asset)] represents a log of #(Asset),

#(w_i, Asset) represents a number of times that a given document on the network and a search query term, w1, of the search query are matched,

log[#(w_i, Asset)] represents a log of #(w_i, Asset), and

Σ

#(w_i, Asset) represents a sum of the number of times that a given document on the network and a search query term, w_i, of the search query are matched.

2. The computer readable storage medium of claim 1, wherein each document on the network is ranked based on its relevance to the search query and is provided a document relevance score using formula (I):

$\hspace{1em}<br><br>\begin{array}{cc}\begin{array}{c}\log <br><br>\left[P<br><br>\left(\mathrm{Asset}|\mathrm{Query}\right)\right]=<br><br>\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(T\right)\right]+\underset{i=1}{\overset{N_Q}{\sum <br><br>}}\\ <br><br>(\log <br><br>\left[\#<br><br>\left(w_i,\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]+\\ <br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)})-\underset{i=1}{\overset{V}{\sum <br><br>}}<br><br><br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)}\end{array}& \left(I\right)\end{array}$

wherein;

P(Asset|Query) represents a probability of returning a given document, Asset, given a particular user inputted search query, Query;

N_Q is the number of terms in the search query;

V is the size of the vocabulary of the network; and

#(T) is the total number of search queries that have been processed.

3. The computer readable storage medium of claim 1, wherein the incrementally-updatable query classifier is updated at an end of each time period, said time period being equal to or less than 24 hours in length.

4. The computer readable storage medium of claim 3, wherein updating count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) comprises adding new data that has been collected during said time period to previously stored count values #(Asset)(old), #(w_i, Asset)(old) and Σ

#(w_i, Asset)(old).

5. The computer storage readable medium of claim 1, wherein the incrementally-updatable query classifier further comprises a time-decay component, wherein recent search queries and user responses are given more weight than past search queries and user responses.

6. The computer readable storage medium of claim 5, wherein:

$\#<br><br>\left(\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br>$ $\#<br><br>\left(w_i,\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\#<br><br>\left(w_i,\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br><br><br>\mathrm{and}$ $\mathrm{\Sigma <br><br>}<br><br><br><br>\#<br><br>\left(w_i,\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\mathrm{\Sigma <br><br>}<br><br><br><br>\#<br><br>\left(w_i,\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br>$

wherein;

λ

is a weighing multiplier having a value of less than 1.0; and

t is an integer representing an age of a count value component.

7. The computer readable medium of claim 6, wherein updating count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) comprises recalculating #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) as follows;

#(Asset)(new)=#(Asset)(0)+λ

[#(Asset)(old)];

#(w_i, Asset)(new)=#(w_i, Asset)(0)+λ

#(w_i, Asset)(old)]; and

Σ

#(w_i, Asset)(new)=Σ

#(w_i, Asset)(0)+λ

[Σ

#(w_i, Asset)(old)];

wherein;

#(Asset)(new), #(w_i, Asset)(new) and Σ

#(w_i, Asset)(new) each independently represent incrementally updated values for count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) respectively;

#(Asset)(0), #(w_i, Asset)(0) and Σ

#(w_i, Asset)(0) each independently represent a number of occurrences within a last time period respectively; and

#(Asset)(old), #(w_i, Asset)(old) and Σ

#(w_i, Asset)(old) each independently represent cumulative count values prior to the last time period respectively.

8. The computer readable storage medium of claim 1, further comprising computer-executable instructions for accepting the search inquiry inputted by a user, conducting a search of the documents on the network to generate search results comprising multiple documents, ranking the multiple documents of the search results using the incrementally-updatable query classifier to generate ranked search results, and displaying the ranked search results to the user.

9. A computing system containing the computer readable storage medium of claim 1 and executing said stored computer-executable instructions.

10. A computer implemented method of incrementally updating a query classifier component in a search engine of a computer, said method comprising:

determining count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset), wherein #(Asset) represents a number of times that a given document on the network is selected for viewing, #(w_i, Asset) represents a number of times that a given document on the network and a search query term, w_i, of the search query are matched, and Σ

#(w_i, Asset) represents a sum of the number of times that a given document on the network and a search query term, w_i, of the search query are matched;

calculating values log[#(Asset)] and log[#(w_i, Asset)], wherein log[#(Asset)] represents a log of #(Asset) and log[#(w_i, Asset)] represents a log of #(w_i, Asset);

storing the count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) and calculated values log[#(Asset)] and log[#(w_i, Asset)] in a database of the computer, wherein the values #(w_i, Asset) and log[#(w_i, Asset)] are stored for search query terms and the values #(Asset), log[#(Asset)] and Σ

#(w_i, Asset) are stored for documents;

displaying documents to one or more users ranked by the query classifier based on previously stored count values and calculated values in response to user inputted search queries received by the search engine of the computer;

receiving responses during a time period from the one or more users selecting documents for viewing; and

updating the stored count values and calculated values by adding new data collected during the time period to the previously stored count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) and the previously stored calculated values log[#(Asset)] and log[#(w_i, Asset)].

11. The method of claim 10, wherein the time period is equal to or less than 24 hours in length.

12. The method of claim 10, wherein updating stored count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) comprises recalculating #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) as follows;

#(Asset)(new)=#(Asset)(0)+λ

[#(Asset)(old)];

#(w_i, Asset)(new)=#(w_i, Asset)(0)+λ

#(w_i, Asset)(old)]; and

Σ

#(w_i, Asset)(new)=Σ

#(w_i, Asset)(0)+λ

[Σ

#(w_i, Asset)(old)];

wherein;

#(Asset)(new), #(w_i, Asset)(new) and Σ

#(w_i, Asset)(new) represent incrementally updated values for count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) respectively;

#(Asset)(0), #(w_i, Asset)(0) and Σ

#(w_i, Asset)(0) represent a number of occurrences within a last time period respectively;

#(Asset)(old), #(w_i, Asset)(old) and Σ

#(w_i, Asset)(old) represent cumulative count values prior to the last time period respectively; and

λ

is a weighing multiplier.

13. The method of claim 12, wherein λ

has a value of less than 1.0.

14. The method of claim 10 further comprising:

determining a document relevance score for a document on a network relative to a user inputted search query.

15. The method of claim 14, wherein the document relevance score is determined using formula (I):

$\hspace{1em}<br><br>\begin{array}{cc}\begin{array}{c}\log <br><br>\left[P<br><br>\left(\mathrm{Asset}|\mathrm{Query}\right)\right]=<br><br>\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(T\right)\right]+\underset{i=1}{\overset{N_Q}{\sum <br><br>}}\\ <br><br>(\log <br><br>\left[\#<br><br>\left(w_i,\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]+\\ <br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)})-\underset{i=1}{\overset{V}{\sum <br><br>}}<br><br><br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)}\end{array}& \left(I\right)\end{array}$

wherein;

P(Asset|Query) represents a probability of returning a given document, Asset, given a particular user inputted search query, Query;

N_Q is the number of terms in the search query;

V is the size of the vocabulary of the network; and

#(T) is the total number of search queries that have been processed.

16. The method of claim 14 farther comprising:

ranking documents in descending order based on document relevance scores determined for each document.

17. A computer readable storage medium having stored computer-executable instructions that are executed by a computer and cause the computer to perform the method of claim 10.

18. A computing device comprising a processing unit executing at least one application module stored in memory on the computing device, wherein the at least one application module comprises application code executable by the processing unit of the computing device for performing a method of ranking documents on a network based on document relevance to a user inputted search query, said method comprising the steps of:

utilizing formula (I) to determine a document relevance score for each document; and

ranking documents in descending order based on the document relevance score for each document;

wherein formula (I) comprises

$\hspace{1em}<br><br>\begin{array}{cc}\begin{array}{c}\log <br><br>\left[P<br><br>\left(\mathrm{Asset}|\mathrm{Query}\right)\right]=<br><br>\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(T\right)\right]+\underset{i=1}{\overset{N_Q}{\sum <br><br>}}\\ <br><br>(\log <br><br>\left[\#<br><br>\left(w_i,\mathrm{Asset}\right)\right]-\log <br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)\right]+\\ <br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)})-\underset{i=1}{\overset{V}{\sum <br><br>}}<br><br><br><br>\frac{\#<br><br>\left(w_i,\mathrm{Asset}\right)}{\#<br><br>\left(\mathrm{Asset}\right)}\end{array}& \left(I\right)\end{array}$

wherein;

P(Asset|Query) represents a probability of returning a given document, Asset, given a particular user inputted search query, Query;

N_Q is the number of terms in the search query;

V is the size of the vocabulary of the network;

#(T) is the total number of search queries that have been processed;

#(Asset) represents a number of times that a given document on the network is selected for viewing;

log[#(Asset)] represents a log of #(Asset);

#(w_i, Asset) represents a number of times that a given document on the network and a search query term, w_i, of the search query are matched;

log[#(w_i, Asset)] represents a log of #( w_i, Asset); and

Σ

#(w_i, Asset) represents a sum of the number of times that a given document on the network and a search query term, w_i, of the search query are matched.

19. The computing device of claim 18, wherein count values #(Asset), #(w_i, Asset) and Σ

#(w_i, Asset) are incrementally updatable, and are represented by;

$\#<br><br>\left(\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\#<br><br>\left(\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br>$ $\#<br><br>\left(w_i,\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\#<br><br>\left(w_i,\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br><br><br>\mathrm{and}$ $\mathrm{\Sigma <br><br>}<br><br><br><br>\#<br><br>\left(w_i,\mathrm{Asset}\right)=\underset{t=0}{\overset{\mathrm{\infty <br><br>}}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}^t<br><br>\left[\mathrm{\Sigma <br><br>}<br><br><br><br>\#<br><br>\left(w_i,\mathrm{Asset}\right)<br><br>\left(t\right)\right];<br><br>$

wherein;

λ

is a weighing multiplier having a value equal to or less than 1.0; and

t is an integer representing an age of a count value component.

20. The computing device of claim 19, wherein λ

is less than 1.0.