Identifying related queries

• US 8,732,153 B1
• Filed: 09/14/2012
• Issued: 05/20/2014
• Est. Priority Date: 05/31/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Covell, Michele
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US13/616,893
• Time in Patent Office: 613 Days
• Field of Search: 707/706
• 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:

generating a first image based on a first search query;

generating a second image based on a second search query;

generating a first set of wavelets corresponding to the first image;

generating a second set of wavelets corresponding to the second image;

generating a first signature for at least some of the wavelets corresponding to the first image;

generating a second signature for at least some of the wavelets corresponding to the second image; and

determining whether the first search query and the second search query are related queries based on comparing at least part of the first signature and at least part of the second signature.

2. The method of claim 1, wherein the at least some wavelets corresponding to the first image are wavelets corresponding to first image that have a magnitude that is greater than a predetermined threshold.

3. The method of claim 1, wherein the at least some wavelets corresponding to the first image are n wavelets corresponding to the first image that have the greatest magnitude, wherein n is an integer.

4. The method of claim 1, further comprising:

identifying the at least part of the first signature and the at least part of the second signature using at least one hashing scheme.

5. The method of claim 4, wherein the at least one hashing scheme includes a Min-Hash algorithm.

6. The method of claim 4, wherein the at least one hashing scheme includes a locality-sensitive hashing algorithm.

7. A system, comprising:

one or more computers including one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising;

generating a first image based on a first search query;

generating a second image based on a second search query;

generating a first set of wavelets corresponding to the first image;

generating a second set of wavelets corresponding to the second image;

generating a first signature for at least some of the wavelets corresponding to the first image;

generating a second signature for at least some of the wavelets corresponding to the second image; and

determining whether the first search query and the second search query are related queries based on comparing at least part of the first signature and at least part of the second signature.

8. The system of claim 7, wherein the at least some wavelets corresponding to the first image are wavelets corresponding to the first image that have a magnitude that is greater than a predetermined threshold.

9. The system of claim 7, wherein the at least some wavelets corresponding to the first image are n wavelets corresponding to the first image that have the greatest magnitude, wherein n is an integer.

10. The system of claim 7, wherein the operations comprise:

identifying the at least part of the first signature and the at least part of the second signature using at least one hashing scheme.

11. The system of claim 10, wherein the at least one hashing scheme includes a Min-Hash algorithm.

12. The system of claim 10, wherein the at least one hashing scheme includes a locality-sensitive hashing algorithm.

13. A non-transitory computer-readable storage medium encoded with a computer program, the computer program comprising instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

generating a first image based on a first search query;

generating a second image based on a second search query;

generating a first set of wavelets corresponding to the first image;

generating a second set of wavelets corresponding to the second image;

generating a first signature for at least some of the wavelets corresponding to the first image;

generating a second signature for at least some of the wavelets corresponding to the second image; and

determining whether the first search query and the second search query are related queries based on comparing at least part of the first signature and at least part of the second signature.

14. The medium of claim 13, wherein the at least some wavelets corresponding to the first image are wavelets corresponding to the first image that have a magnitude that is greater than a predetermined threshold.

15. The medium of claim 13, wherein the at least some wavelets corresponding to the first image are n wavelets corresponding to the first image that have the greatest magnitude, wherein n is an integer.

16. The medium of claim 13, wherein the operations comprise:

identifying the at least part of the first signature and the at least part of the second signature using at least one hashing scheme.

17. The medium of claim 16, wherein the at least one hashing scheme includes a Min-Hash algorithm.

18. The medium of claim 16, wherein the at least one hashing scheme includes a locality-sensitive hashing algorithm.