Identifying related queries

• US 8,019,742 B1
• Filed: 05/31/2007
• Issued: 09/13/2011
• Est. Priority Date: 05/31/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Covell, Michele
• Primary Examiner(s): Wu; Yicun
• Assistant Examiner(s): Mamillapalli; Pavan
• Application Number:
  US11/756,127
• Time in Patent Office: 1,566 Days
• Field of Search: 707/3, 707/4, 707/5, 707/706, 707/721, 707/727, 707/751, 705/10, 382/115, 382/131, 715/854, 706/58
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method includes receiving search queries. Images are generated that represent the volume of each search query relative to all search queries over a period of time. The images are processed to generate wavelets for each image. Related queries having similar increases or decreases in volume are identified by comparing at least some of the wavelets corresponding to a first query to wavelets corresponding to other queries.

Claims

1. A computer-implemented method comprising:

receiving information identifying a first search query through a communication interface;

receiving information identifying a second search query through the communication interface, wherein the first search query differs from the second search query;

accessing information characterizing prior input of the identified search queries by clients into a search engine, the information characterizing the prior input being stored in computer memory;

determining, from the accessed information characterizing the prior input, a query volume for the first search query during a first period of time for which prior input of the identified search queries is characterized by the information stored in the computer memory;

determining, from the accessed information characterizing the prior input, a query volume for the second search query during a second period of time for which prior input of the identified search queries is characterized by the information stored in the computer memory;

generating, using one or more processors, a first representation of the query volume for the first search query relative to two or more variables and a second representation of the query volume for the second search query relative to the two or more variables;

processing, using the one or more processors, the first representation and the second representation to generate a first set of wavelets representing the first representation and a second set of wavelets representing the second representation;

identifying, using the one or more processors, a first subset of wavelets having high magnitude coefficients for the first set of wavelets and a second subset of wavelets having high magnitude coefficients for the second set of wavelets;

generating, using the one or more processors, a first signature for the first representation based on the first subset of wavelets and a second signature for the second representation based on the second subset of wavelets; and

determining, using the one or more processors, whether the first search query and the second search query are related by comparing the first signature to the second signature.

2. The method of claim 1, wherein the first period of time is the same as the second period of time.

3. The method of claim 2, wherein determining if the first search query and the second search query are related comprises:

determining that the first search query and the second search query are related when the first representation and the second representation exhibit similar rises or decreases in query volume during the period of time.

4. The method of claim 3, wherein determining

the query volume for the first search query and the query volume for the second search query comprises:

normalizing the query volume for the first search query based on the search volume of the first search query relative to all queries during the period of time, and

normalizing the query volume for the second search query based on the search volume of the second search query relative to all queries during the period of time.

5. The method of claim 1, further comprising displaying an indication that the first search query and the second search query are related on a display.

6. The method of claim 1, further comprising retrieving, using the one or more processors, search results related to the first query and the second query.

7. The method of claim 6, further comprising displaying the search results to a user on a display.

8. The method of claim 1, further comprising blurring the first representation and the second representation relative to all of the two or more variables before comparing the representations.

9. The method of claim 1, wherein the representations represent the query volume relative to more than two variables.

10. The method of claim 9, wherein one of the variables is geography.

11. The method of claim 1, wherein comparing the images comprises analyzing a plurality of subsets of a time span for the query volumes.

12. A computer-implemented method comprising:

determining, using one or more processors, a query volume for a first search query during a first period of time from information indicating instances where the first search query has been entered into a search engine by clients;

determining, using the one or more processors, a query volume for a second search query during a second period of time from information indicating instances where the first search query has been entered into a search engine by clients;

generating, using the one or more processors, a first representation of the query volume for the first search query relative to two or more variables;

generating, using the one or more processors, a second representation of the query volume for the second search query relative to the two or more variables;

storing the first and second representations in computer memory;

processing, using the one or more processors, the first representation to generate a first set of wavelets representing the first representation;

processing, using the one or more processors, the second representation to generate a second set of wavelets representing the second representation;

identifying, using the one or more processors, a first subset of top wavelets from the first set of wavelets and a second subset of top wavelets from the second set of wavelets; and

determining, using the one or more processors, whether the first search query and the second search query are related by comparing a first signature generated based on at least some of the first set of wavelets to a second signature generated based on at least some of the second set of wavelets, wherein determining if the first search query and the second search query are related comprises determining whether the first search query and the second search query are related by comparing the first subset of top wavelets to the second subset of top wavelets.

13. The method of claim 12, wherein the first period of time is equal to the second period of time.

14. The method of claim 13, wherein determining a query volume for the first search query and a query volume for the second search query comprises:

determining the query volume for the first search query based on the search volume of the first search query relative to all queries over the first period of time, and

determining the query volume for the second search query based on the search volume of the second search query relative to all queries over the second period of time.

15. The method of claim 12, further comprising blurring the first representation and the second representation relative to all of the two or more variables before comparing the representations.

16. The method of claim 12, wherein the representations represent the query volume relative to more than two variables.

17. The method of claim 12, wherein comparing the wavelets comprises analyzing a plurality of subsets of a time span for the query volumes.

18. A computer-implemented method comprising:

determining, using one or more processors, query volumes for each of a plurality of search queries during a period of time from information indicating instances where the search queries have been entered into a search engine by clients;

generating, using the one or more processors, a plurality of representations of the query volumes for each respective search query relative to two or more variables during the period of time;

storing the representations in computer memory;

processing, using the one or more processors, the plurality of representations to generate a set of wavelets representing each of the plurality of representations;

identifying, using the one or more processors, a respective subset of top wavelets for each set of wavelets;

generating, using the one or more processors, signatures for each of the plurality of representations based on the subset of top wavelets for each respective representation; and

determining, using the one or more processors, whether first and second of the search queries are related by comparing a signature corresponding to the first search query to a signature corresponding to the second search query.

19. The method of claim 18, wherein generating signatures for each of the plurality of representations comprises generating signatures for each of the plurality of representations using a min-hash algorithm to compress the subset of top wavelets.

20. The method of claim 18, further comprising identifying at least a portion of signatures for comparison using a hashing scheme.

21. The method of claim 20, wherein the hashing scheme is a locality sensitive hashing scheme.

22. The method of claim 18, further comprising blurring the representations relative to all of the two or more variables before comparing the representations.

23. The method of claim 18, wherein the representations represent the characteristics of the queries relative to more than two variables.

24. The method of claim 18, wherein comparing the signatures comprises analyzing a plurality of subsets of a time span for the query volumes.

25. A system comprising:

means for determining query volumes for each of a plurality of search queries during the period of time from information indicating instances where the search queries have been entered into a search engine by clients;

means for generating a plurality of representations of the query volumes for each respective search query of the plurality of search queries relative to two or more variables during the period of time;

means for storing the representations in computer memory;

means for processing the plurality of representations to generate a set of wavelets for each of the plurality of images;

means for identifying a respective subset of top wavelets for each set of wavelets;

means for generating signatures for each of the plurality of representations based on the subset of top wavelets for each respective representation; and

means for determining whether first and second of the search queries are related, wherein the means for determining is operable to compare a signature corresponding to the first search query to a signature corresponding to the second search query.

26. The system of claim 25, wherein the means for generating signatures for each of the plurality of representations based on the subset of top wavelets for each respective representation comprises:

means generating signatures for each of the plurality of representations using a min-hash algorithm to compress the subset of top wavelets.

27. The system of claim 25, further comprising means for identifying at least a portion of signatures for comparison using a hashing scheme.

28. The system of claim 25, further comprising means for blurring the representations relative to all of the two or more variables before generating the wavelets.

29. The system of claim 25, wherein the representations represent the characteristics of the queries relative to more than two variables.

30. The system of claim 25, wherein comparing the signatures comprises analyzing a plurality of subsets of a time span for the query volumes.

31. A system comprising:

a data storage storing information characterizing search queries that have been entered into a search engine by clients and the timing of instances when the search queries have been entered into the search engine by the clients;

one or more computers programmed to perform operations, the operations including;

determining query volumes for each of a plurality of the search queries during a period from information in the data storage indicating the timing of the instances where the plurality of the search queries have been entered into the search engine by the clients;

generating a plurality of representations of the query volumes for each respective search query of the plurality relative to two or more variables during the period;

storing the plurality of representations;

processing the plurality of representations to generate a set of wavelets representing each of the plurality of representations;

identifying a respective subset of top wavelets for each set of wavelets;

generating signatures for each of the plurality of representations based on the subset of top wavelets for each respective representation; and

determining whether first and second of the search queries are related by comparing a signature for the first search query to a signature for the second search query.

32. The system of claim 31, wherein generating signatures for each of the plurality of representations comprises generating signatures for each of the plurality of representations using a mm-hash algorithm to compress the subset of top wavelets.

33. The system of claim 31, wherein generating signatures for each of the plurality of representations comprises generating signatures for each of the plurality of representations using a mm-hash algorithm to compress the subset of top wavelets.

34. The system of claim 31, wherein the operations further comprise identifying at least a portion of signatures for comparison using a hashing scheme.

35. The system of claim 34, wherein the hashing scheme is a locality sensitive hashing scheme in which small, random, but non-overlapping members of the signatures are selected and repeatedly hashed into bins.

36. The system of claim 31, wherein the one or more computers is programmed to implement a query processing system to determine whether the first and second of the search queries are related.

37. The system of claim 31, further comprising the clients in communication with the one or more computers over one or more data communication networks, the clients having input the search queries into the search engine.

38. A system comprising:

a data storage storing information characterizing the timing of prior input of search queries by clients into a search engine;

one or more computers programmed to perform operations, the operations including;

receiving information identifying a first search query;

receiving information identifying a second search query, wherein the first search query differs from the second search query;

accessing information stored in the data storage, the information characterizing the prior input of the identified search queries into the search engine;

determining, from the accessed information characterizing the prior input, a query volume for the first search query during a first period of time for which prior input of the identified search queries is characterized by the information stored in the computer memory;

determining, from the accessed information characterizing the prior input, a query volume for the second search query during a second period of time for which prior input of the identified search queries is characterized by the information stored in the computer memory;

generating a first representation of the query volume for the first search query relative to two or more variables and a second representation of the query volume for the second search query relative to the two or more variables;

processing the first representation and the second representation to generate a first set of wavelets representing the first representation and a second set of wavelets representing the second representation;

identifying a first subset of wavelets having high magnitude coefficients for the first set of wavelets and a second subset of wavelets having high magnitude coefficients for the second set of wavelets;

generating a first signature for the first representation based on the first subset wavelets and a second signature for the second representation based on the second subset of wavelets; and

determining whether the first search query and the second search query are related by comparing the first signature to the second signature.

39. The system of claim 38, wherein the first period of time is the same as the second.

40. The system of claim 39, wherein determining if the first search query and the second search query are related comprises:

determining that the first search query and the second search query are related when the first representation and the second representation exhibit similar rises or decreases in query volume during the period of time.

41. The system of claim 40, wherein determining the query volume for the first search query and the query volume for the second search query comprises:

normalizing the query volume for the first search query based on the search volume of the first search query relative to all queries during the period of time, and

normalizing the query volume for the second search query based on the search volume of the second search query relative to all queries during the period of time.

42. The system of claim 38, further comprising displaying an indication that the first search query and the second search query are related on a display.

43. The system of claim 38, further comprising retrieving search results related to the first query and the second query.

44. The system of claim 43, further comprising the clients in communication with the one or more computers over one or more data communication networks, the clients programmed to display the search results to a user on displays.

45. A system comprising:

a data storage storing information characterizing the timing of prior instances where of a first search query and a second search query into a search engine;

one or more computers programmed to perform operations, the operations including;

determining a query volume for the first search query during a first period of time from information indicating the instances where the first search query has been entered into a search engine by clients;

determining a query volume for a second search query during a second period of time from information indicating the instances where the first search query has been entered into a search engine by clients;

generating a first representation of the query volume for the first search query relative to two or more variables;

generating a second representation of the query volume for the second search query relative to the two or more variables;

storing the first and second representations;

processing the first representation to generate a first set of wavelets representing the first representation;

processing the second representation to generate a second set of wavelets representing the second representation;

identifying a first subset of top wavelets from the first set of wavelets and a second subset of top wavelets from the second set of wavelets; and

determining whether the first search query and the second search query are related by comparing a first signature generated based on at least some of the first set of wavelets to a second signature generated based on at least some of the second set of wavelets, wherein

determining if the first search query and the second search query are related comprises determining whether the first search query and the second search query are related by comparing the first subset of top wavelets to the second subset of top wavelets.

46. The system of claim 45, wherein the first period of time is equal to the second period of time.

47. The system of claim 46, wherein determining a query volume for the first search query and a query volume for the second search query comprises:

determining the query volume for the first search query based on the search volume of the first search query relative to all queries over the first period of time, and

determining the query volume for the second search query based on the search volume of the second search query relative to all queries over the second period of time.