Real-time document collection search engine with phrase indexing

• US 6,070,158 A
• Filed: 11/13/1997
• Issued: 05/30/2000
• Est. Priority Date: 08/14/1996
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Infoseek Corporation (The Walt Disney Company)
• Inventors: Chang, William I., Miller, Edward R., Kirsch, Steven T.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/970,175
• Time in Patent Office: 929 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 707/102, 707/103, 705/7, 395/200.31, 430/138
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A collection search system is responsive to a user query against a collection of documents to provide a search report. The collection search system includes a collection index including first predetermined single word and multiple word phrases as indexed terms occurring in the collection of documents, a linguistic parser that identifies a list of search terms from a user query, the linguistic parser identifying the list from second predetermined single words and multiple word phrases, and a search engine coupled to receive the list from the linguistic parser. The search engine operates to intersect the list with the collection index to identify a predetermined document from the collection of documents. The search engine includes an accumulator for summing a relevancy score for the predetermined document that is related to the intersection of the predetermined document with the list.

Claims

1. A collection search system responsive to a user query against a collection of documents to provide a search report, said collection search system comprising:

a) a collection index including first predetermined single word and multiple word phrases as indexed terms occurring in said collection of documents;

b) a linguistic parser that identifies a list of search terms from a user query, said linguistic parser identifying said list from second predetermined single words and multiple word phrases; and

c) a search engine coupled to receive said list from said linguistic parser, said search engine intersecting said list with said collection index to identify a predetermined document from said collection of documents, said search engine including an accumulator for summing for said predetermined document a relevancy score related to the intersection of said predetermined document with said list using conditional indexing of said word phrases.

2. The collection search system of claim 1 wherein said collection is fractionally stored in a plurality of distributed servers.

3. The collection search system of claim 1 wherein said linguistic parser provides for eliding predetermined punctuation marks and stop list words, wherein said collection search engine.

4. The search system of claim 1 wherein said phrase document terms include proximity related single word terms, and wherein phrase document terms exclude a predetermined set of words.

5. A collection search system responsive to a user query against a collection of documents to provide a search report, said collection search system comprising:

a) a collection index including first predetermined single word and multiple word phrases as indexed terms occurring in said collection of documents, said collection index storing one-word and two-word indexes of the frequency of occurrence of search phrases;

b) a linguistic parser that identifies a list of search terms from a user query, said linguistic parser identifying said list from second predetermined single words and multiple word phrases; and

c) a search engine coupled to receive said list from said linguistic parser, said search engine intersecting said list with said collection index to identify a predetermined document from said collection of documents, said search engine including an accumulator for summing for said predetermined document a relevancy score related to the intersection of said predetermined document with said list.

6. The search system of claim 5 wherein three-word and more phrases are inferred from said one-word and two-word indexes of the frequency of occurrence of search phrases.

7. A collection search system responsive to a user query against a collection of documents to provide a search report, said collection search system comprising:

a) a collection index including first predetermined single word and multiple word phrases as indexed terms occurring in said collection of documents, wherein said collection index is distributed in different subgroups which share common group statistics;

b) a linguistic parser that identifies a list of search terms from a user query, said linguistic parser identifying said list from second predetermined single words and multiple word phrases; and

c) a search engine coupled to receive said list from said linguistic parser, said search engine intersecting said list with said collection index to identify a predetermined document from said collection of documents said search engine including an accumulator for summing for said predetermined document a relevancy score related to the intersection of said predetermined document with said list.

8. The search system of claim 7 wherein one or more of said subgroups is stored within high-speed memory whereby searches of said one or more of said subgroups do not require accesses to slower-speed memory.

9. A collection search system responsive to a user query against a collection of documents to provide a search report, said collection search system comprising:

a) a distributed collection index including first predetermined one-word and two-word phrases as indexed terms occurring in said collection of documents;

b) a linguistic parser that identifies a list of search terms from a user query, said linguistic parser identifying said list from second predetermined single words and multiple word phrases; and

c) a search engine coupled to receive said list from said linguistic parser, said search engine intersecting said list with said collection index to identify a predetermined document from said collection of documents, said search engine including an accumulator for summing for said predetermined document a relevancy score related to the intersection of said predetermined document with said list.

10. A collection search system responsive to a user query, Q, for searching against a collection of documents,

where each document is described as a string of words, S, where for an M-word document, S=S₁, S₂,S₃, . . . ,S_m,S_m+1,S_m+2,S_m+3, . . . ,SM, where m=1,2, . . . , M,

where for a number, N_g, of documents in a group g of documents in the collection, the documents are designated S1_g,S2_g, . . . ,Sn_g, . . . ,SN_g for n_g =1,2, . . . , N_g, and

where a typical predetermined document, Sn_g, of said documents in the group g is given by, Sn_g =Sn_g,1,Sn_g,2,Sn_g,3, . . . ,Sn_g,m3 Sn_g,m+1,Sn_g,m+2,Sn_g,m+3, . . . ,Sn_g,Mm,

said collection search system comprising:

a collection index including first predetermined one-word and two-word phrases as indexed terms occurring in said collection of documents;

a linguistic parser that identifies from the user query, Q, a list of search terms Q₁, Q₂, . . . , Q_p, . . . , Q_p each having a weighted value, W_Q1,W_Q2, . . . ,W_Qp3 . . . , WQP, said linguistic parser identifying said list of search terms from second predetermined one-word and two-word phrases; and

a search engine coupled to receive said list from said linguistic parser, said search engine intersecting said list with said collection index to identify the predetermined document Sn_g from said collection of documents, said search engine including an accumulator for summing for said predetermined document a relevancy score, score(Sn_g)_Q, for the document Sn_g based on the query Q as follows;

##EQU5## where (A_Ng)_Qp =a document value relative to the number of occurrences of the term Qp in the documents in the group g,

where W_Qp =the value of the query term relative to the number of occurrences of the term Qp in the particular document Sn_g.

11. The search system of claim 10 wherein said documents are in different subgroups, sg_p of the group, g, where g=sg₁, sg₂, . . . ,sg_j, . . . ,sg_G and the scoring is performed separately for each subgroup j using the statistics of the master subgroup, g, where score, score(Sn_g)_Q {sg_j }, for the particular document Sn_g for a particular one subgroup {sg_j } is determined as follows, ##EQU6## where W_Qp {sg_j }=the weighted value for the query collectively considering all the Nsg_j documents in the subgroup sp_j.

12. The search system of claim 11 wherein the total score SCORE(Sn_g)_Q for the document Sn_g for all the subgroups {sg_j } for j=1,2, . . . , P is determined as follows:

##EQU7##