Method for finding semantically related search engine queries

• US 7,577,646 B2
• Filed: 05/02/2005
• Issued: 08/18/2009
• Est. Priority Date: 05/02/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Immorlica, Nicole, Chien, Steve
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): OBERLY, VAN HONG
• Application Number:
  US11/119,667
• Publication Number:
  US 20060248068A1
• Time in Patent Office: 1,569 Days
• Field of Search: 707/3, 707/4, 707/6, 707/10, 707/100, 707/102, 709/203, 709/218
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for determining semantic correlation between an input query and stored queries based on their temporal correlation. Embodiments include a formal calculation of a correlation coefficient between an input query and stored queries. Alternate embodiments include methods for calculation of a correlation coefficient using a reduced data model and efficient data examination with little or no sacrifice in the accuracy of the correlation coefficient.

Claims

1. A method for determining a semantic relationship between two search engine queries, comprising the steps of:

(a) receiving a first search engine query;

(b) identifying a second search engine query stored in memory;

(c) determining a cumulative density of the first and second search engine queries over a plurality of time periods, wherein the density of each of the two search engine queries during a given time period is the frequency of each of the search engine queries in comparison to the combined number of search engine queries during that time period, the cumulative density for the first and second search engine queries being the density of the first and second search engine queries over all time periods in the plurality of time periods;

(d) identifying a semantic correlation between the two search engine queries based on the density of the two search engine queries determined in said step (a), wherein identifying a semantic correlation between the two queries comprises the step of representing the data of the two search engine query frequencies by a bit string, and examining a degree to which corresponding bits in the bit strings representing the two search engine query frequencies match each other;

(e) modifying the second search engine query to include a linking association in memory with the first search engine query in the event it is determined that the semantic correlation identified in said step (d) is above a threshold level; and

(f) displaying results associated with the second search engine query to the user in the event it is determined that the semantic correlation identified in said step (d) is above a threshold level.

2. The method for determining a semantic relationship between two search engine queries as recited in claim 1, wherein a first query of the two search engine queries is an input query, and a second query of the two search engine queries is a stored query, the method further comprising the step of suggesting the stored query to a user or advertiser where it is determined that a semantic relationship above a threshold level exists between the input query and the stored query.

3. The method for determining a semantic relationship between two search engine queries as recited in claim 1, wherein said step (d) of identifying a semantic correlation between the two queries comprising the step of calculating a dot product of a first vector representing the normalized frequency of the first query and a second vector representing the normalized frequency of the second query.

4. A method for determining a semantic relationship between two search engine queries, comprising the steps of:

(a) receiving a first search engine query;

(b) identifying a second search engine query stored in memory;

(c) obtaining a query density function for each of the first and second search engine queries by resolving the first query into a first bit string and by resolving the second query into a second bit string, wherein the query density function for the first and second search engine queries is based on the frequency of each of the search engine queries in comparison to the combined number of search engine queries during a plurality of time periods;

(d) identifying a semantic correlation between the two search engine queries based on a degree to which corresponding bits in the first bit string and the second bit string match each other;

(e) modifying the second search engine query to include a linking association in memory with the first search engine query in the event it is determined that the semantic correlation identified in said step (d) is above a threshold level; and

(f) displaying results associated with the second search engine query to the user in the event it is determined that the semantic correlation identified in said step (d) is above a threshold level.

5. The method for determining a semantic relationship between two search engine queries as recited in claim 4, said step (c) of obtaining a query density function for each of the first and second search engine queries by resolving the first and second queries into a first bit string and a second bit string comprises the step of representing each of the query density function for the two search engine queries by a 128 bit string.

6. The method for determining a semantic relationship between two search engine queries as recited in claim 4, further comprising the step of calculating a correlation coefficient between the two search engine queries, the correlation coefficient indicating the degree of semantic relationship between the two search engine queries.

7. The method for determining a semantic relationship between two search engine queries as recited in claim 4, where said step (c) obtaining a query density function for each of the first and second queries by resolving the first and second queries into a bit string comprises the steps of generating a plurality of hyperplanes, and generating a bit in the bit string for a first of the two search engine queries, the bit determined by a dot product of a first vector orthogonal to one of the hyperplanes and a second vector representing the first search engine query.

8. The method for determining a semantic relationship between two search engine queries as recited in claim 4, further comprising the steps of:

(f) scanning a fraction of the bits of each of the bit strings to identify whether some portion of corresponding bits in the fractions of the first and second bit strings match each other; and

(g) scanning the remainder of bits in the bit strings for correspondence if it is determined in said step (f) that some portion of corresponding bits in the fractions of the first and second bit strings match each other.

9. A computer storage medium having computer-executable instructions for performing steps comprising:

(a) determining t-he a cumulative density of each of a plurality of search engine queries, wherein the plurality of search engine queries include an input query and a plurality of stored queries, and wherein the density of each of the plurality of search engine queries is the frequency of each of the search engine queries in comparison to the combined number of search engine queries during each discrete time period of a plurality of discrete time periods, the cumulative density for each of the search engine queries being the density of each of the search engine queries over all discrete time periods in the plurality of time periods;

(b) representing the query density data determined in said step (a) as respective bit strings, one bit string for each of the plurality of search engine queries;

(c) selecting one or more of the plurality of search engine queries having a correlation coefficient above a first threshold level with respect to a reference search engine the input query of the plurality of search engine queries;

(d) modifying the one or more queries selected in said step (c) to include a linking association in memory with the input; and

(e) presenting the search engine queries, having the correlation coefficient above the first threshold level, to a user.

10. The computer storage medium having computer-executable instructions as recited in claim 9, said step (c) of selecting comprising the steps of:

(i) scanning a fraction of the bits of each of the bit strings associated with the plurality of search engine queries to identify the one or more search engine queries having some portion of corresponding bits in the fractions of the bit strings match each other, and (ii) scanning the one or more search engine queries to identify the one or more search engine queries having a correlation above the first threshold level to the input query.

11. The computer storage medium having computer-executable instructions as recited in claim 10, wherein said step (i) of scanning a fraction of the bits of each of the bit strings associated with the plurality of search engine queries comprises the step of scanning 20 bits of each of the bit strings.

12. The computer storage medium having computer-executable instructions as recited in claim 9, said step (b) of representing the query data normalized in said step (a) as respective bit strings comprises the steps of generating a plurality of hyperplanes, and generating a bit in the bit string for a first of the plurality of search engine queries, the bit determined by a dot product of a first vector orthogonal to one of the hyperplanes and a second vector representing the input query.

13. The computer storage medium having computer-executable instructions as recited in claim 9, further comprising the step of suggesting the one or more search queries to a user.

14. The computer storage medium having computer-executable instructions as recited in claim 9, further comprising the step of calculating a correlation coefficient between the reference search engine input query and the one or more stored search engine queries, the correlation coefficient indicating the degree of semantic relationship between the ˜

input and one or more search engine queries.