Dynamic query expansion

• US 6,411,950 B1
• Filed: 11/30/1998
• Issued: 06/25/2002
• Est. Priority Date: 11/30/1998
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Monier, Louis M., Moricz, Michael Z., Michelou, Jean-Claude
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/201,624
• Time in Patent Office: 1,303 Days
• Field of Search: 707/3, 707/4, 707/5, 707/521, 707/531, 707/10, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A dynamic search result refinement for refining a general search query into a more specific search query. For a general search query, a user is presented with a list of more specific queries. The entries in the list selected from a log-file of queries according to the index frequency of each query. The user can choose a new query from the list of more specific queries and run a database search. The user also has the option to be presented with a list of even more specific queries based on the chosen query and to have a database search run with one of these queries.

Claims

1. A method for searching a plurality of stored records, the method comprising the steps of:

generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases;

identifying at least one subphrase of the query phrase that, in combination with the query phrase, meets at least one predefined phrase-refinement criterion, and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

receiving a first new query phrase from a user;

searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the first new query phrase;

retrieving the identified refinement phrase from the query refinement index; and

transmitting the retrieved refinement phrase to the user;

wherein;

the retrieved refinement phrase is a suggested second new query phrase; and

a subset of phrases in the plurality of phrase and refinement phrase pairs are multi-word phrases.

2. The method of claim 1, wherein identifying at least one subphrase includes identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion only when the subphrase is a quoted phrase having more than one word.

3. The method of claim 1, wherein identifying at least one subphrase includes identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

4. The method of claim 1, wherein:

searching the query refinement index includes identifying a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

the retrieving includes retrieving a plurality of the identified refinement phrases from the query refinement index; and

the transmitting includes transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.

5. A method for searching a plurality of stored records, the method comprising the steps of:

generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases;

computing a frequency for the query phrase and at least one subphrase of the query phrase;

determining whether the frequency for the subphrase is greater than the frequency for the query phrase;

identifying the subphrase and the query phrase as meeting at least one predefined phrase-refinement criterion when the frequency for the subphrase is greater than the frequency of the query phrase; and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

receiving a first new query phrase from a user;

searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the first new query phrase;

retrieving the identified refinement phrase from the query refinement index; and

transmitting the retrieved refinement phrase to the user;

wherein the retrieved refinement phrase is a suggested second new query phrase.

6. The method of claim 5, wherein computing the frequency of the query phrase includes computing the number of times the query phrase is included in the plurality of stored records, and computing the frequency of the subphrase includes computing the number of times the subphrase is included in the plurality of stored records.

7. The method of claim 5, wherein the at least one predefined phrase-refinement criterion is met when the frequency for the subphrase is greater than the frequency of the query phrase by at least a selected factor.

8. The method of claim 5, wherein identifying the subphrase and the query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

9. The method of claim 5, wherein:

searching the query refinement index includes identifying a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

the retrieving includes retrieving a plurality of the identified refinement phrases from the query refinement index; and

the transmitting includes transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.

10. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases, instructions for;

identifying at least one subphrase of the query phrase that, in combination with the query phrase, meets at least one predefined phrase-refinement criterion, and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

instructions for receiving a first new query phrase from a user;

instructions for searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the the first new query phrase;

instructions for retrieving the identified refinement phrase from the query refinement index; and

instructions for transmitting the retrieved refinement phrase to the user;

wherein;

the retrieved refinement phrase is a suggested second new query phrase; and

a subset of phrases in the plurality of phrase and refinement phrase pairs are multi-word phrases.

11. The computer program product of claim 10, wherein the instructions for identifying at least one subphrase include instructions for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion only when the subphrase is a quoted phrase having more than one word.

12. The computer program product of claim 10, wherein the instructions for identifying at least one subphrase include instructions for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

13. The computer program product of claim 10, wherein:

the instructions for searching the query refinement index include instructions for identifying a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

the instructions for retrieving include instructions for retrieving a plurality of the identified refinement phrases from the query refinement index; and

the instructions for transmitting include instructions for transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.

14. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases, instructions for;

computing a frequency for the query phrase and at least one subphrase of the query phrase;

determining whether the frequency for the subphrase is greater than the frequency for the query phrase;

identifying the subphrase and the query phrase as meeting at least one predefined phrase-refinement criterion when the frequency for the subphrase is greater than the frequency of the query phrase; and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

instructions for receiving a first new query phrase from a user;

instructions for searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the the first new query phrase;

instructions for retrieving the identified refinement phrase from the query refinement index; and

instructions for transmitting the retrieved refinement phrase to the user;

wherein the retrieved refinement phrase is a suggested second new query phrase.

15. The computer program product of claim 14, wherein the at least one predefined phrase-refinement criterion is met when the frequency for the subphrase is greater than the frequency of the query phrase by at least a selected factor.

16. The computer program product of claim 14, wherein the instructions for computing the frequency of the query phrase include instructions for computing the number of times the query phrase is included in a plurality of records stored in the computer readable storage medium, and the instructions for computing the frequency of the subphrase include instructions for computing the number of times the subphrase is included in the plurality of stored records.

17. The computer program product of claim 16, wherein the instructions for identifying at least one subphrase include instructions for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

18. The computer program product of claim 14, wherein:

the instructions for searching the query refinement index include instructions for identifying a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

the instructions for retrieving include instructions for retrieving a plurality of the identified refinement phrases from the query refinement index; and

the instructions for transmitting include instructions for transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.

19. A computer system for locating a particular record included in a plurality of records, the computer system comprising:

a first storage device for storing a plurality of previously submitted query phrases;

a processor connected to the first storage device, the processor configured for;

generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of the previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases;

identifying at least one subphrase of the query phrase that, in combination with the query phrase, meets at least one predefined phrase-refinement criterion, and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

receiving a first new query phrase from a user;

searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the the first new query phrase;

retrieving the identified refinement phrase from the query refinement index; and

transmitting the retrieved refinement phrase to the user;

wherein;

the retrieved refinement phrase is a suggested second new query phrase; and

a subset of phrases in the plurality of phrase and refinement phrase pairs are multi-word phrases.

20. The computer system of claim 19, wherein the processor is configured for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion only when the subphrase is a quoted phrase having more than one word.

21. The computer system of claim 19, wherein the processor is configured for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

22. The computer system of claim 19, wherein the processor is configured for:

searching the query refinement index to identify a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

retrieving a plurality of the identified refinement phrases from the query refinement index; and

transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.

28. The computer system of claim 19, further comprising a second storage device connected to the processor for storing the query refinement index.

29. The computer system of claim 19, wherein the first storage device is configured for storing a log-file of user queries.

23. A computer system for locating a particular record included in a plurality of records, the computer system comprising:

a first storage device for storing a plurality of previously submitted query phrases;

a processor connected to the first storage device, the processor configured for;

generating a query refinement index comprising a plurality of phrase and refinement phrase pairs from a set of the previously submitted query phrases, including, for each query phrase of a plurality of the previously submitted query phrases;

computing a frequency for the query phrase and at least one subphrase of the query phrase;

determining whether the frequency for the subphrase is greater than the frequency for the query phrase;

identifying the subphrase and the query phrase as meeting at least one predefined phrase-refinement criterion when the frequency for the subphrase is greater than the frequency of the query phrase; and

storing the identified subphrase and query phrase in the query refinement index as a phrase and refinement phrase pair;

receiving a first new query phrase from a user;

searching the query refinement index to identify a refinement phrase in the query refinement index that is a refinement of the the first new query phrase;

retrieving the identified refinement phrase from the query refinement index; and

transmitting the retrieved refinement phrase to the user;

wherein the retrieved refinement phrase is a suggested second new query phrase.

24. The computer system of claim 23, wherein the at least one predefined phrase-refinement criterion is met when the frequency for the subphrase is greater than the frequency of the query phrase by at least a selected factor.

25. The computer system of claim 23, wherein the processor is configured for computing the number of times the query phrase is included in the plurality of records, and the instructions for computing the frequency of the subphrase include instructions for computing the number of times the subphrase is included in the plurality of records.

26. The computer system of claim 23, wherein the processor is configured for identifying the subphrase and query phrase as meeting the at least one predefined phrase-refinement criterion when the subphrase appears in the plurality of the previously submitted query phrases a sufficient number of times to be statistically significant.

27. The computer system of claim 23, wherein the processor is configured for:

identifying a plurality of refinement phrases in the query refinement index, wherein each identified refinement phrase in the query refinement index is a refinement of the first new query phrase;

retrieving a plurality of the identified refinement phrases from the query refinement index; and

transmitting at least a subset of the plurality of retrieved refinement phrases to the user;

wherein the transmitted plurality of retrieved refinement phrases are suggested second new query phrases.