Discovering associative intent queries from search web logs

• US 7,552,112 B2
• Filed: 09/18/2006
• Issued: 06/23/2009
• Est. Priority Date: 09/18/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Rey, Benjamin, Jhala, Pradhuman
• Primary Examiner(s): Robinson; Greta L
• Assistant Examiner(s): Wilcox; James J
• Application Number:
  US11/522,638
• Publication Number:
  US 20080071740A1
• Time in Patent Office: 1,009 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system is described for discovering associative intent queries based on search web logs. The system may mine one or more user sessions comprising data from search engine query logs and generate query pairs based on the data. The system may use statistics and morphology to identify relationships among the query pairs. From these relationships, the system may distinguish the associative intent query pairs from the similar and unrelated intent query pairs.

Claims

1. A computer-implemented method for discovering an associated query pair comprising:

mining, by a computer, a user session derived from a query log database, wherein the user session comprises at least one query record, the query record comprising a plurality of queries submitted during a defined time period, wherein the time period is delineated by a non-temporal event comprising detecting a switch in search intent by the user;

generating, by the computer, a set of query pairs based on the user session, wherein the set of query pairs comprises an unordered collection of unique query pair combinations having particular attributes;

removing, by the computer, a substitutable query pair from the set of query pairs, wherein substitutable comprises queries that are interchangeable or semantically similar; and

discovering, by the computer, an associated query pair from the set of remaining query pairs, wherein the queries of the associated query pair share a mutually-related subject matter without being substitutable.

2. The method of claim 1 wherein the query record further comprises a user identifier, a timestamp, or combinations thereof.

3. The method of claim 1 wherein the set of query pairs comprises a first set of query pairs, the removing further comprises:

generating a second set of query pairs based on the mined query log; and

performing a statistical test on the second set of query pairs to determine the substitutable query pair.

4. The method of claim 3 wherein the statistical test comprises a log-likelihood ratio (LLR) test and wherein the similar query pair has a computed LLR value greater than a threshold LLR value.

5. The method of claim 1 wherein the removing further comprises:

performing at least one morphological test on the set of query pairs to determine the substitutable query pair.

6. The method of claim 5 wherein the at least one morphological test comprises at least one of an edit distance test, a token number test, a number of substitutions test, a prefix overlap test, a suffix overlap test, or combinations thereof.

7. The method of claim 1 wherein the discovering further comprises:

performing a log-likelihood ratio (LLR) test on the set of remaining query pairs, wherein the associated query pair has a determined LLR value greater than a threshold LLR value.

8. The method of claim 1 further comprising:

offering a search suggestion to a user by at least one of an Internet search engine, intranet search engine, personal search engine, mobile search engine, or combinations thereof, wherein the search suggestion is associated with a user submitted search query and based on the discovered associated query pair.

9. The method of claim 1 further comprising:

offering to a user an advertisement associated with a user submitted search query and based on the discovered associated query pair.

10. A computer-implemented method for discovering an associated query pair comprising:

generating, by a computer, a group of query pairs based on a user session, wherein the user session comprises at least one query record, the query record comprising a plurality of queries submitted during a time period delineated by a non-temporal event comprising detecting a switch in search intent by the user, wherein the set of query pairs comprises an unordered collection of unique query pair combinations having particular attributes;

removing, by the computer, a substitutable query pair from the group of query pairs, wherein substitutable comprises queries that are interchangeable or semantically similar; and

performing, by the computer, a statistical test on the group of remaining query pairs to discover an associated query pair, wherein the queries of the associated query pair share a mutually-related subject matter without being substitutable.

11. The method of claim 10 wherein the group of query pairs comprises a query pair permutation.

12. The method of claim 10 wherein the group of query pairs comprises a first group of query pairs, the removing further comprising:

generating a second group of query pairs based on the user session; and

performing a statistical test on the second group of query pairs to determine the similar query pair.

13. The method of claim 12 wherein the second group of query pairs comprises a query pair combination.

14. The method of claim 10 wherein the removing further comprises:

performing at least one morphological test on the group of query pairs to determine the substitutable query pair.

15. The method of claim 14 wherein the at least one morphological test comprises at least one of an edit distance test, a token number test, a number of substitutions test, a prefix overlap test, a suffix overlap test, or combinations thereof.

16. The method of claim 10 wherein the statistical test comprises a log-likelihood ratio (LLR) test and wherein the performing further comprises:

identifying the associated query pair from the group of query pairs that have a LLR value greater than a threshold LLR value.

17. A computer system for identifying an associated query pair comprising:

a query log processor of a computer operable to mine a user session, wherein the user session comprises at least one query record, the query record comprising a plurality of queries submitted during a defined time period;

a query log database coupled with the computer to store the at least one query record of the user session, wherein the query log database is stored in a data storage system coupled with the query log processor;

a permutation processor coupled with the query log processor and the query log database and operable to generate and store in the query log database a set of query pairs based on the user session, wherein the set of query pairs comprises an unordered collection of unique query pair combinations having particular attributes;

a subtractor coupled with the permutation processor and operable to remove a substitutable query pair from the set of query pairs, which are deleted from the query log database, wherein substitutable comprises queries that are interchangeable or semantically similar; and

an associative log-likelihood ratio (LLR) processor coupled with the subtractor and operable to identify an associated query pair from the set of remaining query pairs, and to isolate within the query log database the associated query pair from unrelated queries, wherein the queries of the associated query pair share a mutually-related subject matter without being substitutable.

18. The computer system of claim 17 wherein the set of query pairs comprises a first set of query pairs, the system further comprising:

a combination processor coupled with the query log processor and operable to generate a second set of query pairs based on the user session;

a substitutable LLR processor coupled with the combination processor and operable to perform a statistical test on the second set of query pairs to identify the similar query pair.

19. The computer system of claim 17 further comprising:

a morphological filter processor coupled with at least one of the permutation processor, the subtractor, or combinations thereof, and operable to perform at least one morphological test on the set of query pairs to identify the similar query pair.

20. The computer system of claim 17 wherein the associative LLR processor is further operable to perform a LLR test on the set of remaining query pairs to identify the associated query pair, wherein the associated pair has a LLR value greater than a threshold LLR value.

21. The computer system of claim 20 wherein associative LLR processor is further operable to perform the LLR test using a normalized frequency count for the set of query pairs.

24. The computer system of claim 17 wherein the time period is delineated by a non-temporal event comprising detecting a switch in search intent by the user.

22. A computer system for discovering an associated query pair comprising:

means for mining, by a computer, a user session including query records derived from a query log database coupled with the computer, wherein the user session comprises at least one query record, the query record comprising a plurality of queries submitted during a defined time period delineated by a non-temporal event comprising detecting a switch in search intent by the user;

means for storing, by the computer, the user session, including the at least one query record, wherein the means for storing is stored in a data storage system coupled with the means for mining;

means, coupled with the means for mining and with the means for storing, for generating a set of query pairs based on the user session, wherein the set of query pairs comprises an unordered collection of unique query pair combinations having particular attributes and are stored in the means for storing;

means, coupled with the means for generating, for removing a substitutable query pair from the set of query pairs, which are deleted from the means for storing, wherein substitutable comprises queries that are interchangeable or semantically similar; and

means, coupled with the means for removing, for discovering an associated query pair from the set of remaining query pairs, and to isolate within the query log database the associated query pair from unrelated queries, wherein the queries of the associated query pair share a mutually-related subject matter without being substitutable.

23. A computer system for discovering an associated query pair comprising computer programming logic stored in a memory and executable by a processor coupled with the memory, the computer programming logic comprising:

a computer having a query log processor;

first logic of the computer operative to mine a user session derived from a query log database coupled with the computer, wherein the user session comprises at least one query record stored in the query log database, the query record comprising a plurality of queries submitted during a defined time period delineated by a non-temporal event comprising detecting a switch in search intent by the user, wherein the query log database is stored in a data storage system coupled with the query log processor;

second logic of the computer coupled with the first logic and operative to generate a set of query pairs based on the user session, wherein the set of query pairs comprises an unordered collection of unique query pair combinations having particular attributes;

third logic of the computer coupled with the second logic and operative to remove a substitutable query pair from the set of query pairs; and

fourth logic of the computer coupled with the third logic and operative to discover an associated query pair from the set of remaining query pairs, wherein the queries of the associated query pair share a mutually-related subject matter without being substitutable.