Systems and methods for analyzing and clustering search queries

• US 9,098,571 B2
• Filed: 01/24/2012
• Issued: 08/04/2015
• Est. Priority Date: 01/24/2011
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Achuthan, Sudhir, Mahajan, Vineet, Timm, Sean C., Walker, Travis A., Song, Sangchul
• Primary Examiner(s): PYO, MONICA M
• Application Number:
  US13/357,385
• Publication Number:
  US 20130024443A1
• Time in Patent Office: 1,288 Days
• Field of Search: 707/722, 707/727, 707/728
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

Computerized systems and methods are disclosed for analyzing search query relationships and managing electronic content. In accordance with one implementation, log data pertaining to a plurality of queries may be received over an electronic network. A click graph may be generated representing one or more relationships between the queries. Further, temporal similarities may be identified between the queries, for example, by looking at peaks in frequency of queries over time. A pair of search queries may be evaluated based on the generated click graph and the identified temporal similarities to determine whether the queries in the pair are related.

Claims

1. A method for analyzing search query relationships, the method comprising the following operations performed by one or more processors:

receiving, over an electronic network, log data relating to a plurality of search queries received from users;

generating a click graph representing relationships among a plurality of queries and a plurality of visited query results associated with each of the plurality of queries,

wherein the click graph depicts at least one first layer relationship between a first query and a second query in the plurality of queries, the first layer relationship indicating that at least one of the plurality of visited query results is associated with both the first query and the second query, and

further wherein the click graph depicts at least one second layer relationship between the first query and second query in the plurality of queries, the second layer relationship indicating that each of the first and second queries has a first layer relationship to a third query;

computing a numeric value representing a degree of the at least one second layer relationship;

identifying temporal similarities between at least one pair of the plurality of queries, the temporal similarities determined based on a temporal distance between peaks in frequency of occurrence for both queries in the at least one pair of the plurality of queries;

evaluating the at least one pair of queries based on the generated click graph and the identified temporal similarities to determine whether the at least one pair of queries are related; and

designating the queries in the at least one pair of queries as related based on the computed value being greater than zero and the temporal distance being below a threshold value.

2. The computer-implemented method of claim 1, wherein the click graph depicts at least one third layer relationship between the first query and the second query in the plurality of queries, the third layer relationship indicating that each of the first and second queries has at least one of a first layer relationship and a second layer relationship to the third query.

3. The computer-implemented method of claim 2, wherein evaluating the at least one pair of queries comprises:

computing a numeric value representing a degree of the at least one third layer relationship; and

designating the queries in the at least one pair of queries as related based on;

at least one of the computed value representing the degree of the at least one second layer relationship and the computed value representing the degree of the at least one third layer relationship being greater than zero; and

the temporal distance being below a threshold value.

4. The computer-implemented method of claim 1, wherein the temporal distance is a Euclidean distance.

5. The computer-implemented method of claim 1, wherein identifying temporal similarities comprises computing a time series for each query in the at least one pair of the plurality of queries, the time series indicating a query frequency at each of a plurality of times.

6. The computer-implemented method of claim 5, further comprising performing at least one of normalizing, coarsening, and flattening on each computed time series.

7. The computer-implemented method of claim 5, further comprising normalizing, coarsening, and flattening each computed time series.

8. The computer-implemented method of claim 1, further comprising, based on the evaluation, designating the queries in the at least one pair of queries as related.

9. The computer-implemented method of claim 1, wherein evaluating the at least one pair of queries comprises:

computing a value representing a first layer similarity between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed value is greater than zero.

10. The computer-implemented method of claim 1, wherein evaluating the at least one pair of queries comprises:

computing the temporal distance between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed temporal distance is below a threshold value.

11. A system for analyzing search query relationships, the system comprising:

a server configured to receive, over an electronic network, log data relating to a plurality of search queries received from users; and

a processor configured to;

generate a click graph representing relationships among a plurality of queries and a plurality of visited query results associated with each of the plurality of queries,

wherein the click graph depicts at least one first layer relationship between a first query and a second query in the plurality of queries, the first layer relationship indicating that at least one of the plurality of visited query results is associated with both the first query and the second query, and

further wherein the click graph depicts at least one second layer relationship between the first query and second query in the plurality of queries, the second layer relationship indicating that each of the first and second queries has a first layer relationship to a third query;

compute a numeric value representing a degree of the at least one second layer relationship;

identify temporal similarities between at least one pair of the plurality of queries, the temporal similarities determined based on a temporal distance between peaks in frequency of occurrence for both queries in the at least one pair of the plurality of queries;

evaluate the at least one pair of queries based on the generated click graph and the identified temporal similarities to determine whether the at least one pair of queries are related; and

designate the queries in the at least one pair of queries as related based on the computed value being greater than zero and the temporal distance being below a threshold value.

12. The system of claim 11, wherein the click graph depicts at least one third layer relationship between the first query and the second query in the plurality of queries, the third layer relationship indicating that each of the first and second queries has at least one of a first layer relationship and a second layer relationship to the third query.

13. The system of claim 12, wherein evaluating the at least one pair of queries comprises:

computing a numeric value representing a degree of the at least one third layer relationship; and

designating the queries in the at least one pair of queries as related based on;

at least one of the computed value representing the degree of the at least one second layer relationship and the computed value representing the degree of the at least one third layer relationship being greater than zero; and

the temporal distance being below a threshold value.

14. The system of claim 11, wherein the temporal distance is a Euclidean distance.

15. The system of claim 11, wherein identifying temporal similarities comprises computing a time series for each query in the at least one pair of the plurality of queries, the time series indicating a query frequency at each of a plurality of times.

16. The system of claim 15, wherein the processor is further configured to perform at least one of normalizing, coarsening, and flattening on each computed time series.

17. The system of claim 15, wherein the processor is further configured to perform normalizing, coarsening, and flattening each computed time series.

18. The system of claim 11, wherein the processor is further configured to, based on the evaluation, designate the queries in the at least one pair of queries as related.

19. The system of claim 11, wherein evaluating the at least one pair of queries comprises:

computing a value representing a first layer similarity between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed value is greater than zero.

20. The system of claim 11, wherein evaluating the at least one pair of queries comprises:

computing the temporal distance between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed temporal distance is below a threshold value.

26. The computer-readable storage medium of claim 16, wherein the step of identifying temporal similarities comprises computing a time series for each query in the at least one pair of the plurality of queries, the time series indicating a query frequency at each of a plurality of times.

27. The computer-readable storage medium of claim 26, further comprising the step of performing at least one of normalizing, coarsening, and flattening on each computed time series.

28. The computer-readable storage medium of claim 26, further comprising the step of normalizing, coarsening, and flattening each computed time series.

21. A computer-readable storage medium including instructions for analyzing search query relationships, which, when executed by at least one processor, cause the processor to perform steps comprising:

receiving, over an electronic network, log data relating to a plurality of search queries received from users;

generating a click graph representing relationships among a plurality of queries and a plurality of visited query results associated with each of the plurality of queries,

wherein the click graph depicts at least one first layer relationship between a first query and a second query in the plurality of queries, the first layer relationship indicating that at least one of the plurality of visited query results is associated with both the first query and the second query, and

further wherein the click graph depicts at least one second layer relationship between the first query and second query in the plurality of queries, the second layer relationship indicating that each of the first and second queries has a first layer relationship to a third query;

computing a numeric value representing a degree of the at least one second layer relationship;

identifying temporal similarities between at least one pair of the plurality of queries, the temporal similarities determined based on a temporal distance between peaks in frequency of occurrence for both queries in the at least one pair of the plurality of queries;

evaluating the at least one pair of queries based on the generated click graph and the identified temporal similarities to determine whether the at least one pair of queries are related; and

designating the queries in the at least one pair of queries as related based on the computed value being greater than zero and the temporal distance being below a threshold value.

22. The computer-readable storage medium of claim 21, wherein the step of generating a click graph comprises generating a click graph depicting at least one third layer relationship between the first query and the second query in the plurality of queries, the third layer relationship indicating that each of the first and second queries has at least one of a first layer relationship and a second layer relationship to the third query.

23. The computer-readable storage medium of claim 21, further comprising the step of, based on the evaluation, designating the queries in the at least one pair of queries as related.

24. The computer-readable storage medium of claim 22, wherein the step of evaluating the at least one pair of queries comprises:

computing a numeric value representing a degree of the at least one third layer relationship; and

designating the queries in the at least one pair of queries as related based on;

at least one of the computed value representing the degree of the at least one second layer relationship and the computed value representing the degree of the at least one third layer relationship being greater than zero; and

the temporal distance being below a threshold value.

25. The computer-readable storage medium of claim 21, wherein the temporal distance is a Euclidean distance.

29. The computer-readable storage medium of claim 21, wherein the step of evaluating the at least one pair of queries comprises:

computing a value representing a first layer similarity between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed value is greater than zero.

30. The computer-readable storage medium of claim 21, wherein the step of evaluating the at least one pair of queries comprises:

computing the temporal distance between the queries in the at least one pair of queries; and

designating the queries in the at least one pair of queries as related if the computed temporal distance is below a threshold value.