Methods for iteratively and interactively performing collection selection in full text searches

• US 6,018,733 A
• Filed: 09/12/1997
• Issued: 01/25/2000
• Est. Priority Date: 09/12/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Infoseek Corporation (GOCOM Corporation)
• Inventors: Chang, William I., Kirsch, Steven T.
• Primary Examiner(s): Fetting, Anton
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/928,543
• Time in Patent Office: 865 Days
• Field of Search: 707/1, 707/3, 707/4, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of selecting the likely most relevant database collections for document searching based on an ad hoc query where each of the databases includes a plurality of documents. Iterative collection selection processing of the databases is performed to obtain consistent relative-ranking collection selection results for each iteration. The method uses a collection selection query and performs the repetitive steps of determining an inverse collection frequency and a document frequency for each database; determining a ranking value for each database; selecting a subset of the set of databases based on predetermined criteria dependant on the ranking value for each the database. The method provides for automated and manual descriptions, boolean selection terms combined with soft terms, and uses term proximity, capitalization, phraseology and other information in establishing a relevance ranking of the collections with respect to the ad hoc query.

Claims

1. A method of permitting iterative performance of collection selection relative to a set of databases, where each said database includes a plurality of documents, to obtain consistent relative-ranking collection selection results for each iteration, said method comprising the steps of:

a) obtaining a collection selection query including a set of predetermined search terms;

b) determining an inverse collection frequency for each member of said set of predetermined search terms with respect to each said database and said set of databases, and determining a document frequency for each member of said set of predetermined search terms with respect to each said database;

c) determining a ranking value for each said database based on a sum of the products of said inverse collection frequencies for said set of predetermined search terms and said document frequencies for respective members of said set of search terms;

d) selecting a subset of said set of databases based on predetermined criteria dependant on said ranking value for each said database; and

e) selectively repeating portions of said steps (b) through (d) with respect to each member of said set of predetermined search terms for each iteration of said method.

2. The method of claim 1 wherein an iteration of said method is performed upon modification of said set of predetermined search terms.

3. The method of claim 2 wherein modification of said set of predetermined search terms includes, in any combination, the addition, alteration, and removal of a search term with respect to said set of predetermined search terms.

4. The method of claim 2 further comprising a step of preparing a meta-index including a set of records respectively representative of said set of databases, each member of said set of records including any of search term data, statistical data and fielded data, said inverse collection frequencies and said document frequencies being determinable from said search term data and said statistical data.

5. The method of claim 4 wherein said set of databases is selected from a superset of databases based on a set of conditional values established in connection with said set of predetermined search terms, the selection of said set of databases being based on an intersection of said set of conditional values and said fielded data stored with respect to said superset of databases.

6. The method of claim 5 wherein an iteration of said method is performed upon modification of said set of conditional values.

7. The method of claim 6 wherein said search term data includes single word terms and multiple-word phrase terms and wherein said set of predetermined search terms includes in any combination of one or more:

a) a search term including a single-word term;

b) a search term including one or more single word terms reduced by exclusion of context-free single word terms;

c) a search term identified as a noun phrase;

d) a search term identified as a word tuple;

e) a search term identified as a capitalized single word term or a multiple word term;

f) a proper name reduced by exclusion of any context-free single word terms;

g) a hyphenated phrase expanded to include, as separate search terms, the single-word terms of the hyphenated phrase, a single-word term that is the combined form of the single-word terms of the hyphenated phrase, and sequential subsets of the single-word terms of the hyphenated phrase;

h) a proper name, having more than two single-word terms, expanded to include, as separate search terms, the single-word terms of said proper name; and

i) a search term delineated by a predetermined phrase word-length.

8. The method of claim 7 wherein said fielded data of each member of said set of records includes descriptive information qualifying the contents of a respective member of said set of databases.

9. The method of claim 1, 4 or 8 wherein said document frequency is calculated in relation to the number of documents in a predetermined member of said set of databases that contains a predetermined one of said predetermined terms and the number of documents within said predetermined member of said set of databases, constrained to being in excess of a predetermined threshold number.

10. A method of executing a query selectively against a collection of databases, each including a plurality of documents, said method comprising the steps of:

a) receiving a first predetermined query including a set of predetermined search terms from a user;

b) utilizing said first predetermined query to select a set of databases from said collection of databases;

c) optionally reporting said set of databases to said user and permitting said first predetermined query to be modified and substituted for said first predetermined query, said steps of utilizing and optionally reporting then being repeated;

d) optionally receiving a second predetermined query from said user and substituting said second predetermined query for said first predetermined query; and

e) searching said set of databases to select a set of documents that are responsive to said first predetermined query.

11. The method of claim 10 wherein said step of utilizing includes the steps of:

a) determining an inverse collection frequency for each member of said set of predetermined search terms with respect to each said database and said set of databases, and determining a document frequency for each member of said set of predetermined search terms with respect to each said database;

b) determining a ranking value for each said database based on a sum of the products of said inverse collection frequencies for said set of predetermined search terms and said document frequencies for respective members of said set of search terms; and

c) selecting said set of databases from said collection of databases based on predetermined criteria dependant on said ranking value for each said database.

12. The method of claim 11 wherein said of step of utilizing uses a meta-index data file that stores a plurality of records that respectively represent the members of a superset of said collection of databases, each of said records storing any of search term data, statistical data, and fielded data descriptive of a corresponding member of said superset of databases, said inverse collection frequencies and said document frequencies being determinable from said search term data and said statistical data.

13. The method of claim 12 further comprising the step of prequalifying said collection of databases by selection from said superset of databases based on a set of conditional values established by said user in connection with said set of predetermined search terms, the selection of said collection of databases being based on an intersection of said set of conditional values and said fielded data stored by said plurality of records.

14. The method of claim 13 wherein said step of obtaining includes said step of prequalifying said collection of databases, and wherein said step of optionally reporting includes permitting said set of conditional values to be modified and substituted as part of said first predetermined query, said steps of prequalifying, utilizing and optionally reporting then being repeated.

15. A method of supporting a search of a plurality of databases in response to a predetermined query, said method comprising the steps of:

a) establishing a meta-index database containing collection records corresponding to the members of said plurality of databases, each said collection record including a collection term list, including terms that may include word terms and phrase terms, statistical data, and fielded data descriptive of a respective member of said plurality of databases;

b) supporting a first search of said collection records with respect to said fielded data to identify a set of said plurality of databases by satisfaction of logical relationships between a set of conditional values, provided in conjunction with a set of search terms as part of said predetermined query, and said fielded data of respective said collection records;

c) supporting a second search of said collection records corresponding to said set of databases with respect to said collection term lists and statistical data to develop term rank calculation data on a per said term, per said collection record, and per said set of databases basis;

d) selecting a subset of said set of databases based on said rank calculation data for use in a subsequent search.

16. The method of claim 15 wherein said step of establishing said meta-index database includes obtaining index databases corresponding to members of said plurality of databases, said index databases including pluralities of document records, where each said document record corresponds to a document stored in a member of said plurality of databases and includes any of a document term list, statistical data, and fielded data, and wherein said meta-index database is constructed from any of said index databases, said plurality of databases, and data separate from said index databases and said plurality of databases that is descriptive of any member of said plurality of databases.

17. The method of claim 16 wherein said term rank calculation data is based on a document frequency derived from the frequency of occupancy of a predetermined term in documents of a predetermined database relative to the total number of documents within said predetermined database that is equal or greater than a predetermined minimum number of documents in said predetermined database.

18. The method of claim 17 wherein said term rank calculation data is further based on an inverse collection frequency derived from the total number of documents within said set of databases relative to the total number of documents within said set of databases that have at least a predetermined number of occurrences of said predetermined term.

19. The method of claim 18 wherein said collection term lists and statistical data stored by said collection records and corresponding to said plurality of databases is used to develop said term rank calculation data.

20. The method of claim 19 wherein a predetermined said collection term list includes in any combination of one or more:

a) a word term;

b) a phrase term including one or more single word terms reduced by exclusion of context-free single word terms;

c) a phrase term identified as a noun phrase;

d) a phrase term identified as a word tuple;

e) a term identified as a capitalized word term or a phrase term;

f) a proper name reduced by exclusion of any context-free word terms;

g) a hyphenated phrase expanded to include, as separate terms, the separate word terms of the hyphenated phrase, a word term formed from the combined form of the separate word terms of the hyphenated phrase, and sequential subsets of the separate word terms of the hyphenated phrase;

h) a proper name, having more than two word terms, expanded to include, as separate search terms, the separate word terms of said proper name; and

i) a phrase term delineated by a predetermined phrase word-length.