Granted Patent B2

US 9,098,571 · App. 13/357,385 · Granted Aug 4, 2015

Abstract

Claims (79)

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.

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.

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.

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.

Assignments (7)