FORECASTING TIME-DEPENDENT SEARCH QUERIES

• US 20090006045A1
• Filed: 06/28/2007
• Published: 01/01/2009
• Est. Priority Date: 06/28/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Ning, Chen, Zheng, Zhang, Benyu, Yan, Jun, Wang, Jian
• Granted Patent: US 7,693,823 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Techniques for analyzing and modeling the frequency of queries are provided by a query analysis system. A query analysis system analyzes frequencies of a query over time to determine whether the query is time-dependent or time-independent. The query analysis system forecasts the frequency of time-dependent queries based on their periodicities. The query analysis system forecasts the frequency of time-independent queries based on causal relationships with other queries. To forecast the frequency of time-independent queries, the query analysis system analyzes the frequency of a query over time to identify significant increases in the frequency, which are referred to as “query events” or “events.” The query analysis system forecasts frequencies of time-independent queries based on queries with events that tend to causally precede events of the query to be forecasted.

Claims

1. A method in a computing device for forecasting frequency of a time-dependent query, the method comprising:

storing frequency of the query at intervals;

calculating a value of a frequency spectral of the query for each of a plurality of angular frequencies;

identifying one or more peaks within the frequency spectral;

generating, for a model, parameters for each identified peak; and

determining a forecasted frequency at an interval based on the model parameters generated for the model.

2. The method of claim 1 wherein the model is based on a cosine signal hidden periodicity model.

3. The method of claim 2 wherein the model is represented by the following:

$q_t=\underset{j=1}{\overset{q}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\exp <br><br>\left(\mathrm{<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

4. The method of claim 3 wherein the model parameters are represented by the following:

$\begin{array}{cc}{\mathrm{\omega <br><br>}}_j={\mathrm{\lambda <br><br>}}_j^{*},T_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\omega <br><br>}}_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\lambda <br><br>}}_j^{*},{\mathrm{\alpha <br><br>}}_j=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>{\mathrm{\lambda <br><br>}}_j^{*}<br><br>t},<br><br>A_j=2<br><br><br><br>{\mathrm{\alpha <br><br>}}_j<br><br><br><br><br><br>\mathrm{and}<br><br><br><br>{\mathrm{\varphi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

5. The method of claim 2 wherein the model is represented by the following:

$q_t=\underset{j=1}{\overset{k}{\sum <br><br>}}<br><br>A_j<br><br>\cos <br><br>\left({\mathrm{\omega <br><br>}}_j<br><br>t+{\mathrm{\varphi <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

6. The method of claim 5 wherein the model is represented in the complex domain.

7. The method of claim 1 wherein the value of the frequency spectral for an angular frequency is represented by the following:

$S_N<br><br>\left(\mathrm{\lambda <br><br>}\right)=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>\mathrm{\lambda <br><br>}<br><br><br><br>t}<br><br>\mathrm{\lambda <br><br>}\in <br><br>\left[-\mathrm{\pi <br><br>},\mathrm{\pi <br><br>}\right].$

8. The method of claim 7 wherein a peak is a locally maximum value of the frequency spectral within a range as represented by the following:

$S_N<br><br>\left({\mathrm{\lambda <br><br>}}_j\right)\ge <br><br>S_N<br><br>\left(\mathrm{\lambda <br><br>}\right),<br><br>\mathrm{where}<br><br><br><br>\mathrm{\lambda <br><br>}\in <br><br>\left[{\mathrm{\lambda <br><br>}}_j-1/2<br><br>\sqrt{N},{\mathrm{\lambda <br><br>}}_j+1/2<br><br>\sqrt{N}\right]$

9. The method of claim 1 including after generating the model, predicting the frequencies for the intervals using the model and determining an error between the stored frequencies and the predicted frequencies.

10. The method of claim 9 including when the error satisfies an accuracy criterion, indicating that the model is accurate.

11. A computer-readable medium encoded with instructions for controlling a computing device to forecast frequency of a time-dependent query, by a method comprising:

calculating a value of the frequency spectral of the query for each of a plurality of angular frequencies;

identifying one or more peaks within the frequency spectral;

for each identified peak, generating model parameters for a cosine signal hidden periodicity model;

evaluating accuracy of the model using the model parameters; and

when the evaluation indicates that the model is accurate, forecasting frequency of the query at an interval using the model parameters.

12. The computer-readable medium of claim 11 wherein the model is represented by the following:

$q_t=\underset{j=1}{\overset{q}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\exp <br><br>\left(\mathrm{<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t$

13. The computer-readable medium of claim 12 wherein the model parameters are represented by the following:

$\begin{array}{cc}{\mathrm{\omega <br><br>}}_j={\mathrm{\lambda <br><br>}}_j^{*},T_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\omega <br><br>}}_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\lambda <br><br>}}_j^{*},{\mathrm{\alpha <br><br>}}_j=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>{\mathrm{\lambda <br><br>}}_j^{*}<br><br>t},<br><br>A_j=2<br><br><br><br>{\mathrm{\alpha <br><br>}}_j<br><br><br><br><br><br>\mathrm{and}<br><br><br><br>{\mathrm{\varphi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

14. The computer-readable medium of claim 11 wherein the frequency spectral is represented by the following:

$S_N<br><br>\left(\mathrm{\lambda <br><br>}\right)=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>\mathrm{\lambda <br><br>}<br><br><br><br>t}<br><br>\mathrm{\lambda <br><br>}\in <br><br>\left[-\mathrm{\pi <br><br>},\mathrm{\pi <br><br>}\right].$

15. The computer-readable medium of claim 14 wherein a peak is a locally maximum value of the frequency spectral within a range as represented by the following:

$S_N<br><br>\left({\mathrm{\lambda <br><br>}}_j\right)\ge <br><br>S_N<br><br>\left(\mathrm{\lambda <br><br>}\right),<br><br>\mathrm{where}<br><br><br><br>\mathrm{\lambda <br><br>}\in <br><br>\left[{\mathrm{\lambda <br><br>}}_j-1/2<br><br>\sqrt{N},{\mathrm{\lambda <br><br>}}_j+1/2<br><br>\sqrt{N}\right].$

16. The computer-readable medium of claim 11 wherein the evaluating includes predicting the frequencies for the intervals using the model and determining an error between actual frequencies and predicted frequencies.

17. A computing system for forecasting frequency of a time-dependent query, by a method comprising:

a query frequency store storing number of times the query was submitted to a search engine during each of a plurality of intervals;

a component that calculates values of a frequency spectral for each of a plurality of angular frequencies based on a cosine signal hidden periodicity model;

a component that identifies one or more peaks within the frequency spectral;

a component that generates model parameters for the cosine signal hidden periodicity model based on the identified peaks;

a component that evaluates accuracy of the model using the model parameters by predicting the frequencies for the intervals using the model and determining an error between actual frequencies and predicted frequencies; and

a component that forecasts frequency of the query at an interval using the model parameters.

18. The computing device of claim 17 wherein the model is represented by the following:

$q_t=\underset{j=1}{\overset{q}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\exp <br><br>\left(\mathrm{<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

19. The computing device of claim 17 wherein the model parameters are represented by the following:

$\begin{array}{cc}{\mathrm{\omega <br><br>}}_j={\mathrm{\lambda <br><br>}}_j^{*},T_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\omega <br><br>}}_j=2<br><br>\mathrm{\pi <br><br>}/{\mathrm{\lambda <br><br>}}_j^{*},{\mathrm{\alpha <br><br>}}_j=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>{\mathrm{\lambda <br><br>}}_j^{*}<br><br>t},<br><br>A_j=2<br><br><br><br>{\mathrm{\alpha <br><br>}}_j<br><br><br><br><br><br>\mathrm{and}<br><br><br><br>{\mathrm{\varphi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

20. The computing device of claim 19 wherein the frequency spectral is represented by the following:

$S_N<br><br>\left(\mathrm{\lambda <br><br>}\right)=\underset{t=1}{\overset{N}{\sum <br><br>}}<br><br>q_t<br><br>{\mathrm{<br><br>}}^{-\mathrm{<br><br>}<br><br><br><br>\mathrm{\lambda <br><br>}<br><br><br><br>t}<br><br>\mathrm{\lambda <br><br>}\in <br><br>\left[-\mathrm{\pi <br><br>},\mathrm{\pi <br><br>}\right].$