REPRESENTING QUERIES AND DETERMINING SIMILARITY BASED ON AN ARIMA MODEL

• US 20090006326A1
• 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 8,090,709 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Representing queries and determining similarity of queries based on an autoregressive integrated moving average (“ARIMA”) model is provided. A query analysis system represents each query by its ARIMA coefficients. The query analysis system may estimate the frequency information for a desired past or future interval based on frequency information for some initial intervals. The query analysis system may also determine the similarity of a pair of queries based on the similarity of their ARIMA coefficients. The query analysis system may use various metrics, such as a correlation metric, to determine the similarity of the ARIMA coefficients.

Claims

1. A method in a computing device for determining similarity between queries, the method comprising:

storing frequencies of the queries during intervals;

for each of the queries, generating ARIMA coefficients for that query based on the stored frequencies for that query; and

for a pair of queries, calculating a similarity score for the queries based on a correlation between the ARIMA coefficients of the queries.

2. The method of claim 1 wherein the generating of ARIMA coefficients includes identifying a number of ARIMA coefficients for each query.

3. The method of claim 2 wherein the identifying of the number of ARIMA coefficients is based on an Akaike Information Criterion algorithm.

4. The method of claim 2 wherein the calculating of a similarity score normalizes the number of ARIMA coefficients for the pair of queries.

5. The method of claim 4 wherein the normalizing includes adding ARIMA coefficients with a zero value to the query with fewer ARIMA coefficients.

6. The method of claim 1 wherein the generating of the ARIMA coefficients generates the same number of coefficients for each query.

7. The method of claim 1 wherein the calculating of the similarity score includes aggregating products, for each ARIMA coefficient, of a first factor of a first query of the pair and a second factor of a second query of the pair, a factor for an ARIMA coefficient of a query being a difference between the ARIMA coefficient and a mean of the ARIMA coefficients divided by a standard deviation of the ARIMA coefficients.

8. The method of claim 1 wherein the frequencies of the query are derived from analysis of a query log of a search engine service.

9. The method of claim 1 including predicting frequencies of a query based on frequencies of queries that are determined to be similar based on their similarity scores.

10. A computer-readable medium encoded with instructions for controlling a computing device to determine frequency of a query at an interval, by a method comprising:

storing frequencies of the query during intervals;

generating ARIMA coefficients representing the query based on the stored frequencies; and

estimating the frequency of the query at the interval based on the ARIMA coefficients for the query.

11. The computer-readable medium of claim 10 wherein the estimated frequency is a predicted frequency for a future interval.

12. The computer-readable medium of claim 10 wherein the estimated frequency is a regenerated frequency of a past interval.

13. The computer-readable medium of claim 10 including determining similarity between a pair of queries based on the ARIMA coefficients for the queries.

14. The computer-readable medium of claim 13 wherein the similarity is based on a correlation metric.

15. The computer-readable medium of claim 13 wherein the similarity is based on a Euclidean distance metric.

16. The computer-readable medium of claim 13 wherein the similarity is based on a cosine similarity metric.

17. The computer-readable medium of claim 13 wherein the generating of ARIMA coefficients includes identifying a number of ARIMA coefficients for each query.

18. A computing device for representing a query comprising:

a query frequency store having, for each of a plurality of intervals, a frequency of the query during the interval;

a component that generates ARIMA coefficients for the query based on the frequencies of the query during the intervals; and

an ARIMA coefficient store for storing the generated ARIMA coefficients representing the query.

19. The computing device of claim 18 including a component that determines similarity between a pair of queries based on the ARIMA coefficients of the queries.

20. The computing device of claim 19 wherein the similarity is based on a similarity score derived from a correlation of the ARIMA coefficients of the queries.