Randomized query generation and document relevance ranking for robust information retrieval from a database

• US 5,802,515 A
• Filed: 06/11/1996
• Issued: 09/01/1998
• Est. Priority Date: 06/11/1996
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Adar, Eytan, Charity, Mitchell N.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/661,591
• Time in Patent Office: 812 Days
• Field of Search: 707/5, 707/3, 707/4
• US Class Current: 707/723
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus for randomly selecting terms from an input string to form a plurality of search queries is described. Each of the plurality of search queries can be provided to a database to locate database entries in the database. Database entries returned from a database search using the plurality of search queries may be ordered to provide a relevance ranked list of the database entries.

Claims

1. A information retrieval system for retrieving information from a database, the system comprising:

a query string generator for receiving an input text string and for providing a plurality of query strings, each of the plurality of query strings having a plurality of terms wherein each of the plurality of terms are randomly selected from the input text string;

a database search interface coupled to the query string generator, the database search interface for receiving each of the plurality of query strings from the query string generator, for providing the plurality of query strings to the data base and for receiving search results from the database, the search results including a number of items; and

a ranking processor for receiving the search results from the database search interface and for providing a rank value for each of the items in the search results.

2. The system of claim 1 further comprising:

an input device for receiving an input text string; and

a text string processor coupled between the input device and the query string generator, the text string generator for receiving the input text string from the input device and for providing a conditioned text string to the query string generator.

3. The system of claim 2 wherein the database search interface is coupled to the query string generator and the search results are provided from said database search interface to said query string generator and said query string generator includes means for modifying a search parameter in response to the search results.

4. The system of claim 3 wherein the search parameter modified in response to the search results correspond to at least one of:

the number of every strings; and

the number of terms in each of the query strings.

5. The system of claim 2 wherein the ranking processor is coupled to the query string generator and the search results are provided from said ranking processor to said query string generator and said query string generator includes means for modifying a search parameter of said query string generator.

6. The system of claim 5 wherein the search parameter corresponds to a first one of:

the number of words in a query string; and

the number of query strings.

7. The system of claim 2 wherein:

each of the items in the search results correspond to a first one of;

a list of database entries; and

a list of document identifiers, each of the document identifiers provided as a unique pointer to a corresponding entry in the database; and

wherein each of the rank values are provided by counting the number of query strings which return a particular item in the search results and said ranking processor sorts the items in the search results in a predetermined order according to the respective rank values.

8. A method for searching a database having a plurality of documents stored therein, the method comprising the steps of:

(a) identifying an input text string having a first plurality of terms;

(b) randomly selecting a second plurality of terms from the first plurality of terms to form a first search string, the number of terms in the first search string being less than the number of terms in the input text string;

(c) randomly selecting a third plurality of terms from the input text string, to form a second search string, wherein the number of terms in the first search string are equal to the number of terms in the second search string and wherein at least one of the terms in the second search string is not found in the first search string;

(d) identifying each of the documents in the database which contain the first search string;

(e) identifying each of the documents in the database which contain the second search string;

(f) computing a rank value for each of the documents identified in steps (d) and (f) wherein each rank value for each respective document corresponds to the number of search strings with which the respective document was identified; and

(g) listing each of the records in a predetermined order, wherein the order is determined by the corresponding rank values.

9. The method of claim 8 wherein after step (c) the method further comprises the step of:

repeating step (c) to provide a plurality of search strings.

10. The method of claim 9 wherein the number of terms in at least one of the plurality of search strings is not equal to the number of terms in the second search string.

11. A method for searching a database comprising the steps of:

(a) identifying a first text string having a first plurality of terms;

(b) randomly selecting a first predetermined number of terms from the first plurality of terms to form a first search string, the number of terms in the first search string being less than the number of terms in the first text string;

(c) randomly selecting a next predetermined number of terms from the first plurality of terms to form a next search string;

(d) repeating step (c) a predetermined number of times to provide a predetermined number of next search strings, wherein the first search string and each of the next search strings form a plurality of search strings;

(e) identifying each of a plurality of database entries which contain at least one of the plurality of search strings;

(f) computing a rank value for each of the database entries identified in step (e) wherein each rank value for each respective database entry corresponds to the number of search strings from the plurality of search strings with which the respective database entry was identified; and

(g) listing each of the database entries in a predetermined order, wherein the order is determined by the corresponding rank values.

12. The method of claim 11, wherein the predetermined number of terms in a first one of the plurality of search strings is equal to the predetermined number of terms in a second one of the plurality of search strings.

13. The method of claim 12, wherein the predetermined number of terms in a third one of the plurality of search strings is different than the predetermined number of terms in a fourth one of the plurality of search strings.

14. The method of claim 11, wherein the step of identifying each of the plurality of database entries includes the step of identifying a plurality of document identifiers, each of the document identifiers provided as a unique pointer to a corresponding entry in the database.

15. The method of claim 14 further comprising the steps of:

providing at least one of the document identifiers to a processor; and

retrieving from the database, via the processor the particular database entry represented by the document identifier.

16. The method of claim 15 further comprising the step of providing the document to an output device.

17. A method for searching a database comprising the steps of:

(a) identifying a first text string having a first plurality of terms;

(b) randomly selecting a first predetermined number of terms from the first plurality of terms to form a first search string, the number of terms in the first search string being less than the number of terms in the first text string;

(c) identifying each of a plurality of database entries which contain each of the terms in the first search string;

(d) randomly selecting a next predetermined number of terms from the first plurality of terms to form a next search string;

(e) identifying each of a plurality of database entries which contain each of the terms in the next search string;

(f) repeating steps (d) and (e) a predetermined number of times to provide a predetermined number of next search strings, wherein the first search string and each of the next search strings form a plurality of search strings;

(g) computing a rank value for each of the database entries identified in steps (c), (e) and (f) wherein each rank value for each respective database entry corresponds to the number of search strings from the plurality of search strings with which the respective database entry was identified; and

(g) listing each of the database entries in a predetermined order, wherein the order is determined by the corresponding rank values.

18. The method of claim 17 wherein the predetermined number of times steps (d) and (e) are repeated is determined by the particular database entries identified in step (e).

19. A computer program product for use with an information retrieval system, the computer program product comprising:

a computer usable medium having computer readable program code means for identifying an input text string having a first plurality of terms;

a computer usable medium having computer readable program code means for randomly selecting a first predetermined number of terms from the first plurality of terms to form a first search string, the number of terms in the first search string being less than the number of terms in the input text string;

a computer usable medium having computer readable program code means for randomly selecting a second predetermined number of terms from the input text string, to form a second search string, wherein at least one of the terms in the second search string is not found in the first search string;

a computer usable medium having computer readable program code means for identifying each of the documents in the database which contain the first search string;

a computer usable medium having computer readable program code means for identifying each of the documents in the database which contain the second search string;

a computer usable medium having computer readable program code means for computing a rank value for each of the documents identified by said computer usable medium having computer readable program code means for identifying each of the documents in the database which contain the first search string and said computer usable medium having computer readable program code means for identifying each of the documents in the database which contain the second search string, wherein each rank value for each respective document corresponds to the number of search strings with which the respective document was identified; and

a computer usable medium having computer readable program code means for listing each of the records in a predetermined order, wherein the order is determined by the corresponding rank values.

20. The computer program product of claim 19 further comprising a computer usable medium having computer readable program code means for modifying the predetermined number of terms selected by said computer readable program code means for randomly selecting a second predetermined number of terms from the input text string in response to the documents identified by said computer readable program code means for identifying each of the documents in the database which contain the first search string.

21. The computer program product of claim 20 further comprising a computer usable medium having computer readable program code means for receiving the input text string identified by said computer readable program code means for identifying an input text string having a first plurality of terms and for providing the input text string as a conditioned input text string.