Forecasting time-dependent search queries

• US 7,693,823 B2
• Filed: 06/28/2007
• Issued: 04/06/2010
• Est. Priority Date: 06/28/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Ning, Chen, Zheng, Zhang, Benyu, Yan, Jun, Wang, Jian
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US11/770,385
• Publication Number:
  US 20090006045A1
• Time in Patent Office: 1,013 Days
• Field of Search: None
• US Class Current: 706/8
• 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:

for each of a plurality of past intervals, storing frequency of the query at the past interval, the stored frequency for an interval representing number of times the query was submitted during the interval;

calculating a value of a frequency spectral of the query for each of a plurality of angular frequencies based on frequencies at the past intervals;

identifying one or more peaks within the frequency spectral;

generating, for a model, parameters for each identified peak, the generated model providing an estimated frequency of the query at an interval based on a contribution to the estimated frequency derived from each identified peak, wherein the model is based on a cosine signal hidden periodicity model;

for each of a plurality of future intervals, determining a forecasted frequency at the future interval based on the model parameters generated for the model by summing the contributions to the estimated frequency derived from each identified peak; and

storing an indication of the determined forecasted frequency.

2. The method of claim 1 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{i<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

3. The method of claim 2 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{e<br><br>}}^{-\mathrm{i<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{\phi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

4. The method of claim 1 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{\phi <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

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

6. 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{e<br><br>}}^{-\mathrm{i<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].$

7. The method of claim 6 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),\mathrm{where}$ $\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].$

8. The method of claim I 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.

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

10. A computer-readable storage 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 based on actual frequency of the query at each of a plurality of past intervals, the actual frequency for an interval representing number of times the query was submitted during the interval;

identifying one or more peaks within the frequency spectral;

for each identified peak, generating model parameters for a cosine signal hidden periodicity model based on the identified peaks, the generated cosine signal hidden periodicity model providing an estimated frequency of the query at an interval based on a contribution to the estimated frequency derived from each identified peak;

evaluating accuracy of the cosine signal hidden periodicity model using the model parameters based on comparison of the actual frequencies of the past intervals to estimated frequencies generated by the cosine signal hidden periodicity model;

when the evaluation indicates that the cosine signal hidden periodicity model is accurate, forecasting frequency of the query at future intervals using the model parameters; and

storing an indication of the forecasted frequency at the future intervals.

11. The computer-readable storage medium of claim 10 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{i<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

12. The computer-readable storage medium of claim 11 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{e<br><br>}}^{-\mathrm{i<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{\phi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

13. The computer-readable storage medium of claim 10 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{e<br><br>}}^{-\mathrm{i<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].$

14. The computer-readable storage medium of claim 13 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),\mathrm{where}$ $\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].$

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

16. 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 past intervals as an actual frequency for each past interval;

a memory containing computer-executable instructions of

a component that calculates values of a frequency spectral for each of a plurality of angular frequencies based on the actual frequencies for the past intervals;

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

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

a component that evaluates accuracy of the cosine signal hidden periodicity 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 when the evaluation indicates that the cosine signal hidden model is accurate, forecasts frequency of the query at a future interval using the model parameters; and

a processor for executing the computer-executable instructions stored in the memory.

17. The computing device of claim 16 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{i<br><br>}<br><br><br><br>t<br><br><br><br>{\mathrm{\lambda <br><br>}}_j\right)+{\mathrm{\xi <br><br>}}_t.$

18. The computing device of claim 16 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{e<br><br>}}^{-\mathrm{i<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{\phi <br><br>}}_j=\arg <br><br><br><br>\left({\mathrm{\alpha <br><br>}}_j\right).& \end{array}$

19. The computing device of claim 18 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{e<br><br>}}^{-\mathrm{i<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].$