Determination of time dependency of search queries

• US 7,693,908 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): Abel-Jalil; Neveen
• Assistant Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US11/770,358
• Publication Number:
  US 20090006312A1
• Time in Patent Office: 1,013 Days
• Field of Search: None
• US Class Current: 707/751
• 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 analyzing time dependency of a query, the method comprising:

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

calculating by the computing device values of a frequency spectral for each of a plurality of angular frequencies of the query based on the stored frequency of the queries at each of the plurality of intervals based on the following equation;

$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]$

where S_N(λ

) represents a value of the spectral frequency for the angular frequency λ

, q_t represents the frequency for interval t, and N represents the number of intervals in the plurality of intervals;

determining by the computing device whether the values of the frequency spectral include peaks wherein a peak is a locally maximum value of the frequency spectral within a range with a property 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-\frac{1}{2<br><br>\sqrt{N}},{\mathrm{\lambda <br><br>}}_j+\frac{1}{2<br><br>\sqrt{N}}\right];<br><br>$

and

after determining that the values of the frequency spectral include no peaks, indicating that the query is time-independent; and

after determining that the values of the frequency spectral include a peak, indicating that the query is time-dependent; and

calculating the periodicities of the query based on the following equation;

T_j=2π

/λ

_j

where T_j represents the periodicity corresponding to the peak at angular frequency λ

_j

wherein time dependency of the query based on the determination of whether the frequency spectral includes peaks.

2. The method of claim 1 wherein the query is a query submitted to a search engine service and the stored frequency for an interval represents the number of times the query was submitted to the search engine service during that interval.

3. A computer-readable storage medium encoded with instructions for controlling a computing device to determine time dependency of a query, by a method comprising:

calculating a value of a frequency spectral for each of a plurality of angular frequencies of the query based on the following equation;

$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]$

where S_N(λ

) represents a value of the spectral frequency for an angular frequency λ

, q_t represents a frequency for an interval t, and N represents the number of intervals;

determining whether the values of the frequency spectral include peaks wherein a peak is a locally maximum value of the frequency spectral within a range;

when it is determined that the frequency spectral includes no peak, indicating that the query is time-independent; and

when it is determined that the frequency spectral includes one or more peaks, indicating that the query is time-dependent.

4. The computer-readable storage medium of claim 3 wherein a peak is a locally maximum value of the frequency spectral.

5. The computer-readable storage medium of claim 3 wherein each identified peak represents a periodicity of the query.

6. The computer-readable storage medium of claim 3 wherein a peak is a locally maximum value of the frequency spectral within a range with a property 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-\frac{1}{2<br><br>\sqrt{N}},{\mathrm{\lambda <br><br>}}_j+\frac{1}{2<br><br>\sqrt{N}}\right].$

7. The computer-readable storage medium of claim 3 including adjusting the frequencies to have a zero mean prior to calculating the values of the frequency spectral.

8. The computer-readable storage medium of claim 3 wherein the query is a query submitted to a search engine service and the frequency for an interval represents the number of times the query was submitted to the search engine service during that interval.

9. The computer-readable storage medium of claim 3 wherein a periodicity of a query is based on an inverse of the angular frequency of the peak.

10. The computer-readable storage medium of claim 9 wherein the periodicity is 2π

divided by the angular frequency of the peak.

11. A computing device for determining time dependency of a query, comprising:

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

a memory storing computer-executable instructions of

a component that calculates a value of the frequency spectral for each of a plurality of angular frequencies of the query based on the stored frequency of the queries at each of the plurality of intervals based on the following equation;

$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]$

where S_N(λ

) represents a value of the spectral frequency for the angular frequency λ

, q_t represents the frequency for interval t, and N represents the number of intervals in the plurality of intervals;

a component that determines whether the values of the frequency spectral includes peaks, each peak being a locally maximum value within a range of angular frequencies that is based on an inverse of the number of intervals; and

a component that, when it is determined that the frequency spectral includes no peak, indicates that the query is time-independent, and when it is determined that the frequency spectral includes one or more peaks, indicates that the query is time-dependent; and

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

12. The computing device of claim 11 wherein each identified peak represents a periodicity of the query.

13. The computing device of claim 12 wherein the periodicity is 2π

divided by the angular frequency of the peak.