Identifying related queries

• US 8,515,935 B1
• Filed: 08/26/2011
• Issued: 08/20/2013
• 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/219,076
• Time in Patent Office: 725 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 system comprising:

one or more data processing devices programmed to perform operations comprising;

receiving a first search query from a source device;

identifying a second search query as having a relationship with the first search query, comprising comparing;

properties of a first set of wavelets whose magnitude exceeds a first threshold value, the first set of wavelets being generated by processing a first multi-dimensional representation of a volume at which the first search query has been submitted to a search engine system

with

properties of a second set of wavelets whose magnitude exceeds a second threshold value, the second set of wavelets being generated by processing a second multi-dimensional representation of a volume at which the second search query has been submitted to the search engine system; and

transmitting, to the source device, data identifying the second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query,

wherein the first threshold value is based on a size of the first multi-dimensional representation and the second threshold value is based on a size of the second multi-dimensional representation.

2. The system of claim 1, wherein:

the system comprises the search engine system; and

the operations further comprise transmitting, to the source device, data characterizing a first search result set responsive to the first search query and data characterizing a first search result set responsive to second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query.

3. The system of claim 1, wherein identifying the second search query as having the relationship with the first search query comprises:

generating the first multi-dimensional representation of the query volume for the first search query relative to two or more variables, the two or more variables including at least the first variable and the second variable;

generating the 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 the first representation to generate a set of wavelets representing the first representation;

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

identifying the first set of wavelets whose magnitude exceeds the first threshold value and the second set of wavelets whose magnitude exceeds the second threshold value.

4. The system of claim 1, wherein identifying the second search query as having the relationship with the first search query comprises identifying that a result of a comparison of similarity of the properties of the first set of wavelets whose magnitude exceeds the first threshold value and the properties of the second set of wavelets whose magnitude exceeds the second threshold value exceeds a third threshold value.

5. The system of claim 1, wherein identifying the second search query as having the relationship with the first search query comprises determining that similarity between the properties of the first set of wavelets whose magnitude exceeds the first threshold value and the properties of the second set of wavelets whose magnitude exceeds the second threshold value exceeds similarity between the properties of the first set of wavelets whose magnitude exceeds the first threshold value and properties of a third set of wavelets whose magnitude exceeds a third threshold value generated by processing a third multi-dimensional representation of a volume at which a third search query has been submitted to the search engine system.

6. The system of claim 1, wherein:

the properties of the first set of wavelets whose magnitude exceeds the first threshold value comprise binary vectors representing quantizations of the first set of wavelets whose magnitude exceeds the first threshold value; and

the properties of the second set of wavelets whose magnitude exceeds the second threshold value comprise binary vectors representing quantizations of the second set of wavelets whose magnitude exceeds the second threshold value.

7. The system of claim 1, wherein:

the properties of the first set of wavelets whose magnitude exceeds the first threshold value comprise a first signature created by compressing the first set of wavelets whose magnitude exceeds the first threshold value; and

the properties of the second set of wavelets whose magnitude exceeds the second threshold value comprise a second signature created by compressing the second set of wavelets whose magnitude exceeds the second threshold value.

8. The system of claim 7, wherein identifying the second search query as having the relationship with the first search query comprises using a hashing scheme to identify that the first signature should be compared to the second signature.

9. The system of claim 1, wherein:

the first multi-dimensional representation represents locations of origin of the first search query submissions and the volume at which the first search query has been submitted to the search engine system; and

the second multi-dimensional representation represents locations of origin of the second search query submissions and the volume at which the second search query has been submitted to the search engine system.

10. A method implemented by a system comprising one or more data processing devices, the method comprising:

receiving a first search query from a source device;

identifying a second search query as having a relationship with the first search query, comprising comparing;

properties of a first set of wavelets whose magnitude exceeds a first threshold value, the first set of wavelets being generated by processing a first multi-dimensional representation of a volume at which the first search query has been submitted to a search engine system

with

properties of a second set of wavelets whose magnitude exceeds a second threshold value, the second set of wavelets being generated by processing a second multi-dimensional representation of a volume at which the second search query has been submitted to the search engine system; and

transmitting, to the source device, data identifying the second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query,

wherein the first threshold value is based on a size of the first multi-dimensional representation and the second threshold value is based on a size of the second multi-dimensional representation.

11. The method of claim 10, wherein:

the system comprises the search engine system; and

the method further comprises transmitting, from the system to the source device, data characterizing a first search result set responsive to the first search query and data characterizing a first search result set responsive to second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query.

12. The method of claim 10, wherein identifying the second search query as having the relationship with the first search query comprises:

generating, by the system, the first multi-dimensional representation of the query volume for the first search query relative to two or more variables, the two or more variables including at least the first variable and the second variable;

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

storing, by the system, the first and second representations in computer memory;

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

processing, by the system, the second representation to generate a set of wavelets representing the second representation; and

identifying the first set of wavelets whose magnitude exceeds the first threshold value and the second set of wavelets whose magnitude exceeds the second threshold value.

13. The method of claim 10, wherein identifying the second search query as having the relationship with the first search query comprises identifying that a result of a comparison of similarity of the properties of the first set of wavelets whose magnitude exceeds the first threshold value and the properties of the second set of wavelets whose magnitude exceeds the second threshold value exceeds a third threshold value.

14. The method of claim 10, wherein identifying the second search query as having the relationship with the first search query comprises determining that similarity between the properties of the first set of wavelets whose magnitude exceeds the first threshold value and the properties of the second set of wavelets whose magnitude exceeds the second threshold value exceeds similarity between the properties of the first set of wavelets whose magnitude exceeds the first threshold value and properties of a third set of wavelets whose magnitude exceeds a third threshold value generated by processing a third multi-dimensional representation of a volume at which a third search query has been submitted to the search engine system.

15. The method of claim 10, wherein:

the properties of the first set of wavelets whose magnitude exceeds the first threshold value comprise binary vectors representing quantizations of the first set of wavelets whose magnitude exceeds the first threshold value; and

the properties of the second set of wavelets whose magnitude exceeds the second threshold value comprise binary vectors representing quantizations of the second set of wavelets whose magnitude exceeds the second threshold value.

16. The method of claim 10, wherein:

the properties of the first set of wavelets whose magnitude exceeds the first threshold value comprise a first signature created by compressing the first set of wavelets whose magnitude exceeds the first threshold value; and

the properties of the second set of wavelets whose magnitude exceeds the second threshold value comprise a second signature created by compressing the second set of wavelets whose magnitude exceeds the second threshold value.

17. The method of claim 16, wherein identifying the second search query that has the relationship with the first search query comprises using a hashing scheme to identify that the first signature should be compared to the second signature.

18. The method of claim 10, wherein:

the first multi-dimensional representation represents locations of origin of the first search query submissions and the volume at which the first search query has been submitted to the search engine system; and

the second multi-dimensional representation represents locations of origin of the second search query submissions and the volume at which the second search query has been submitted to the search engine system.

19. A system comprising:

one or more data processing devices programmed to perform operations comprising;

receiving a first search query from a source device;

identifying a second search query as having a relationship with the first search query, comprising comparing;

properties of a first set of wavelets whose magnitude exceeds a first threshold value, the first set of wavelets being generated by processing a first multi-dimensional representation of a volume at which the first search query has been submitted to a search engine system

with

properties of a second set of wavelets whose magnitude exceeds a second threshold value, the second set of wavelets being generated by processing a second multi-dimensional representation of a volume at which the second search query has been submitted to the search engine system,

wherein the first threshold value is based on a size of the first multi-dimensional representation and the second threshold value is based on a size of the second multi-dimensional representation; and

transmitting, to the source device, search results responsive to the first search query and search results responsive to the second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query.

20. A method implemented by a system comprising one or more data processing devices, the method comprising:

receiving a first search query from a source device;

identifying a second search query as having a relationship with the first search query, comprising comparing;

properties of a first set of wavelets whose magnitude exceeds a first threshold value, the first set of wavelets being generated by processing a first multi-dimensional representation of a volume at which the first search query has been submitted to a search engine system

with

properties of a second set of wavelets whose magnitude exceeds a second threshold value, the second set of wavelets being generated by processing a second multi-dimensional representation of a volume at which the second search query has been submitted to the search engine system,

wherein the first threshold value is based on a size of the first multi-dimensional representation and the second threshold value is based on a size of the second multi-dimensional representation; and

transmitting, to the source device, search results responsive to the first search query and search results responsive to the second search query in response to the receipt of the first search query and the identification of the second search query as having the relationship with the first search query.