Abstract:
A computer search involves expanding a user query with two synonym dictionaries-actions and object-and then validating the expanded queries by comparison with entries in a Subject-Action-Object Knowledge Database (SAO KB) in a discipline corresponding to the query. The latter is prepared from natural language texts and contains fields with subjects, actions, objects, and “main parts of objects” extracted from the object.

Description:
RELATED APPLICATIONS  
       [0001]    This is a continuation-in-pat of copending U.S. patent application Ser. No. 60/199,659 filed Apr.25, 2000 and copending U.S. patent application Ser. No. 60/199,920 filed Apr. 26, 2000. This application is related to copending U.S. patent application Ser. No.60/199,658 filed Apr. 25, 2000 and copending U.S. patent application Ser. No. 60/199,921 filed April 26, 2000. This application is also related to copending U.S. patent application Ser. No. 09/541,192 filed Apr.3, 2000, which is a continuation application of copending U.S. patent application Ser. No. 09/345,547, filed Jun. 30, 1999 which is a continuation-in-part of copending U.S. patent application Ser. No. 09/321,804 filed May 27, 1999. These applications are herewith incorporated herein by reference. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    This invention relates to computer based search systems, and particularly to narrowing searches for the user&#39;s convenience.  
         BACKGROUND OF THE INVENTION  
         [0003]    Usually computer-based document-search processors use keywords. The result of a keyword search is often an enormous amount of information, the majority of which is irrelevant to user&#39;s requirements.  
           [0004]    The precision of a search can be increased, if the user formulates the query as a problem, for example, “produce aluminum layer”, or “heat water”, or “oxidize silicon wafer”. But such formulations severely decrease the quantity of found information because the search will not find expressions such as “form Al layer” that are similar to “produce aluminum layer”, or expressions such as “increase temperature of water” that are similar to “heat water”, or expressions such as “perform oxidation of silicon substrate” that are similar to “oxidize silicon wafer”.  
           [0005]    It is possible to provide a complete and more exact search with help of a dictionary of search synonyms e.g. in the form of Al layer=produce aluminum layer . . . , etc. But estimates show that volume of entries in such a dictionary would be huge-more than 10 7  expressions to describe different problems in just technical fields. Expansion into other (nontechnical) disciplines will lead to multiple expansion of this dictionary (up to 10 11  expressions).  
           [0006]    An object of the invention is to improve search systems.  
         SUMMARY OF EMBODIMENTS OF THE INVENTION  
         [0007]    An embodiment of the invention involves expanding the user query with help of two synonym dictionaries-actions and object, and then validating every result from the obtained queries with help of a Subject-Action-Object Knowledge Database (SAO KB), containing fields with subjects, actions, objects, and “main parts of objects” extracted from the object. The SAO KB is prepared from natural language texts with the help of a semantic processor such as that disclosed in U.S. Pat. No. 6,167,370.  
           [0008]    These and other embodiments, objects, and advantages of the invention will become evident from the following description of exemplary embodiments when read in light of the accompanying drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    [0009]FIG. 1 is a block diagram of a system using a software program and embodying the invention.  
         [0010]    [0010]FIG. 2 is a flow chart illustrating the operation of the program embodying the invention.  
         [0011]    [0011]FIG. 3 is a more detailed flowchart illustrating the operation of the program.  
         [0012]    [0012]FIG. 4 is a view of a screen in a monitor depicting the program and inviting entry of a query.  
         [0013]    [0013]FIG. 5 is a view of a screen in a monitor depicting the program and inviting entry of a query. 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0014]    The following are incorporated herein by reference:  
         [0015]    I. System and on-line information service presently available at  www.cobrain.com  and the publicly available user manual therefor.  
         [0016]    II. The software product presently marketed by Invention Machine Corporation of Boston, Mass., U.S.A., under it&#39;s trademark “KNOWLEDGIST” and the publicly available user manual therefor.  
         [0017]    III. U.S. Pat. No. 6,167,370.  
         [0018]    IV. U.S. patent application Ser. No. 09/541,182 filed Apr. 3, 2000.  
         [0019]    V. The software product presently marketed by Invention Machine Corporation of Boston, Mass., U.S.A. under its Trademark “TECHOPTIMIZER” and the publicly available user manual therefor.  
         [0020]    VI. U.S. Pat. No. 5,901,068.  
         [0021]    In FIG. 1 a preferred software system and method embodying the invention is in the form of a program. The program resides in a personal computer  12  that includes a CPU  14 , a monitor  16 , a keyboard/mouse  18 , and a printer  20  and is in the form of a program. The program may be stored on a portable disk and inserted in a disk reader slot  22  or on a fixed disc in the computer or on a ROM. According to another embodiment the program resides on a server and the user accesses the program with a standard communication port  23  over a communications network via LAN, WAN, or the Internet. The port  23  also serves for accessing information from databases on the Internet. Computer  12  can be conventional and be of any suitable make or brand. A printer  20  provides a hard copy of a session where desired. Other peripherals and modem/network interfaces are provided as desired.  
         [0022]    [0022]FIG. 2 is a flowchart illustrating the operation of an embodiment. Here a user&#39;s query  50  passes to a query analysis and extension phase  60  to produce a list of queries  70 . A queries validation unit  80  using an SAO KB validates the query list to produce a desired list of validated queries  90  for search in external documents.  
         [0023]    A more detailed diagram of query extension appears in FIG. 3. Here, the program invites a user to enter a query  110  on a semantic search screen of a monitor  16  as shown in FIG. 4. The user&#39; query data  120  passes to query analysis module  130 . Query analysis module  130  divides the user&#39;s query data  120  into action data  150  and object data  160 . The simplest method of such division relies on list of verbs. For example, we can extract action “heat” from an initial query: “heat aluminum layer”, because “heat” is present in the list of verbs; the remainder of query: “aluminum layer” is then recognized as an object.  
         [0024]    Action data  150  are transmitted to module  180  of action expansion (or action expansion module). Action expansion is accomplished on the basis of an action dictionary  140 , containing the six parts:  
         [0025]    List of verbs divided into groups, containing the verbs with similar sense (heat-warm, produce-create-generate, etc.);  
         [0026]    List of “verb-nouns” expressions synonymous with other verb (heat-increase temperature-rise temperature, etc.)  
         [0027]    List of “verbsA” including the verbs-perform, carry out, realize, and other verbs with similar sense;  
         [0028]    List of “nouns” including the following groups—“verb—relevant verbal noun” (heat-heating; produce-production, etc.)  
         [0029]    List of “verbsB” including the verbs—produce, create, form, and other verbs of similar sense;  
         [0030]    List of “participle2” including the following groups—“verb—relevant participle2” (heat-heated; produce-produced, etc.).  
         [0031]    The action expansion module  180  forms four lists from action module  150  and actions dictionary  140 :  
         [0032]    List of verbs relevant to action in module  200 ;  
         [0033]    List of “verbsA—verbal noun” expressions relevant to action in module  210 ;  
         [0034]    List of “verbsB—participle2” expressions relevant to action in module  220 ;  
         [0035]    List of “verb—noun” expressions relevant to action in module  230 .  
         [0036]    For example, module  180  takes the action “heat” and forms the following lists:  
         [0037]    List of verbs relevant to action in module  200 —“heat, warm”;  
         [0038]    List of “verbsA—verbal noun” expressions relevant to action in module  210 —“perform—heating”, “carry out—heating”, “realize—heating”, etc.;  
         [0039]    List of “verbsB—participle2” expressions relevant to action in module  220 —“produce—heated”, “create—heated”, “form—heated”, and etc.  
         [0040]    List of “verb—noun” expressions relevant to action in module  230 —“increase—temperature”, rise—temperature”, and etc.  
         [0041]    The object data  160  pass to the module  190  of object expansion (or object expansion module  190 ). Object expansion is accomplished on basis of a dictionary of object synonyms  170 , containing groups of objects having similar sense (aluminum layer—Al layer, laser radiation—coherent radiation, etc.).  
         [0042]    The object expansion module  190  forms lists of expressions synonymous with the objects in module  240  from the objects in module  160  and a dictionary of object synonyms in module  170 . For example, object expansion in module  190  uses the object “aluminum layer” to form the following list: aluminum layer, Al layer, aluminium layer, etc.  
         [0043]    All the lists in modules  200 ,  210 ,  220 ,  230 , and  240  are transmitted into validation module  250 . A validation module  250  forms search queries from the lists in modules  200 ,  210 ,  220 ,  230 , and  240  and accomplishes the search in an SAO KB  260  according to these queries.  
         [0044]    The SAO KB  260  is prepared from natural language texts with help of a semantic processor as described in the aforementioned U.S. patent application Ser. No. 09/345,547 filed Apr.3, 2000 (Reference IV above) as well as in U.S. Pat. No. 6,167,370 (Reference III above). The SAO KB  260  contains the following fields: subjects, actions, objects, and “main parts of objects” extracted from the object. For example, the semantic processor converts the sentence: “A thin aluminum layer is heated by reflected laser radiation” into following fields of the SAO KB  260 :  
         [0045]    Subject—“reflected laser radiation”;  
         [0046]    Action—“heat”;  
         [0047]    Object—“thin aluminum layer”;  
         [0048]    Main part of object—“aluminum layer”;  
         [0049]    The volume of entries in the SAO KB  260  should be about 10 6  SAOs or more. The natural language texts can belong to various disciplines such as (science, engineering, culture, business, etc.). A customized SAO KB can also be used. Texts for a customized SAO KB should be selected from a single discipline. If the user query and customized SAO KB belong to similar disciplines, query expansion will be more complete and precise. According to an embodiment the SAO KB  260  is prepared from natural language texts in a specific discipline or a group of related disciplines.  
         [0050]    Validation module  250  performs search queries according to the following rules. Here the sequence is not relevant although all are performed:  
         [0051]    1) [All verbs from list of verbs relevant to action  200  through OR] AND [all expressions from list of synonymous to object expressions  240  through OR];  
         [0052]    the search of verbs is accomplished in the “action” field of the SAO KB  260 , and search of expressions from list of synonymous to object expressions is accomplished in “main part of object” field of SAO KB  260 ;  
         [0053]    2) [All verbs from list of “verbsA” through OR] AND [all nouns from list of “verbsA—verbal noun”expressions relevant to action  210  through OR] AND [all expressions from list of synonymous to object expressions  240  through OR];  
         [0054]    the search of verbs is accomplished in the “action” field of the SAO KB  260 , search of verbal nouns from “verbsA—verbal noun” expressions is accomplished in the “main part of object” field of the SAO KB  260 ; and search of expressions from list of synonymous to object expressions is accomplished in the “object” field of SAO KB  260 ;  
         [0055]    3) [All verbs from list of “verbsB” through OR] AND [all participles2 from list of “verbsB-participle2” expressions relevant to action  220  through OR] AND [all expressions from list of synonymous to object expressions  240  through OR];  
         [0056]    the search of verbs is accomplished in the “action” field of the SAO KB  260 , the search of participles2 from list of “verbsB-participle2” expressions is accomplished in the “object” field of SAO KB; and the search of expressions from the list of synonymous to object expressions is accomplished in the “main part of object” field of the SAO KB.  
         [0057]    4) [All verbs from list of “verb—noun” expressions relevant to action  230  through OR] AND [all nouns from list of “verbs—noun” expressions relevant to action  230  through OR] AND [all expressions from list of synonymous to object expressions  240  through OR];  
         [0058]    the search of verbs is accomplished in the “action” field of the SAO KB  260 , the search of nouns from the “verbs—noun” expressions is accomplished in the “main part of object” field of the SAO KB; and search of expressions from list of synonymous to object expressions is accomplished in the “object” field of the SAO KB  260 ;  
         [0059]    For example, it is possible to obtain the following search queries from “heat aluminum layer” (for simplification, not all the verbs and expressions from the dictionaries are used):  
         [0060]    {[heat OR warm] in “action” field of SAO KB} AND {[aluminum layer OR Al layer] in “main part of object” field of SAO KB};  
         [0061]    {[perform OR realize] in “action” field of SAO KB} AND {[heating] in “main part of object” field of SAO KB} AND {[aluminum layer OR Al layer] in “object” field of SAO KB};  
         [0062]    {[produce OR create] in “action” field of SAO KB} AND {[aluminum layer OR Al layer] in “main part of object” field of SAO KB} AND {[heated] in “object” field of SAO KB};  
         [0063]    {[increase OR rise] in “action” field of SAO KB} AND {[temperature] in “main part of object” field of SAO KB} AND {[aluminum layer OR Al layer] in “object” field of SAO KB}.  
         [0064]    The search queries are used by validation module  250  for searching in SAO KB  260 . The module  250  counts the quantity of found SAOs for every query. If an SAO isn&#39;t found, the query is considered non-valid. Then the validation module  250  forms the list of validated SAOs  280  comprising the SAOs found according to the above-mentioned queries in SAO KB  260 . Module  310  shows the user validated SAOs, as illustrated in FIG. 5 which is a view of a screen displaying data from the program.  
         [0065]    Furthermore, the validation module  250  can form the list of validated AOs (action-object)  270  from the list of validated SAOs  280 . For that, module  250  removes subjects from all validated SAOs and all words from objects, except those contained in search queries. A list of validated AOs  270  can be used in module  300  of search (or search module  300 ) for searching external information sources  290 .  
         [0066]    Two examples (for simplification, using only the actions dictionary; with the volume of an SAO KB=5×10 6  SAOs) are shown in following table.  
                                                                                                                       Queries after   Results of search in SAO   Queries after       expansion   KB with frequencies   validation                                User query - form           magnetic film.                    Form   Magnetic   Form   Magnetic   3724    Form   Magnetic           Film       Film           Film       Produce   Magnetic   Produce   Magnetic   262   Produce   Magnetic           Film       Film           Film       Obtain   Magnetic   Obtain   Magnetic   220   Obtain   Magnetic           Film       Film           Film       Provide   Magnetic   Provide   Magnetic   211   Provide   Magnetic           Film       Film           Film       Make   Magnetic   Make   Magnetic   126   Make   Magnetic           Film       Film           Film       Grow   Magnetic   Grow   Magnetic    87   Grow   Magnetic           Film       Film           Film       Fabri-   Magnetic   Fabri-   Magnetic    42   Fabri-   Magnetic       cate   Film   cate   Film       cate   Film       Give   Magnetic   Give   Magnetic    42   Give   Magnetic           Film       Film           Film       Create   Magnetic   Create   Magnetic    24   Create   Magnetic           Film       Film           Film       Manu-   Magnetic   Manu-   Magnetic    15   Manu-   Magnetic       facture   Film   facture   Film       facture   Film       Prepare   Magnetic   Prepare   Magnetic    14   Prepare   Magnetic           Film       Film           Film       Gen-   Magnetic   Gen-   Magnetic    11   Gen-   Magnetic       erate   Film   erate   Film       erate   Film       Synthe-   Magnetic   Synthe-   Magnetic    6   Synthe-   Magnetic       size   Film   size   Film       size   Film       Emit   Magnetic   Emit   Magnetic    0           Film       Film       Radiate   Magnetic   Radiate   Magnetic    0           Film       Film       Give   Magnetic   Give   Magnetic    0       Off   Film   Off   Film       Ema-   Magnetic   Ema-   Magnetic    0       nate   Film   nate   Film       Con-   Magnetic   Con-   Magnetic    0       struct   Film   struct   Film       Yield   Magnetic   Yield   Magnetic    0           Film       Film       Acquire   Magnetic   Acquire   Magnetic    0           Film       Film       Derive   Magnetic   Derive   Magnetic    0           Film   Film                    User query -           produce laser       radiation                    Form   Laser   Emit   Laser   834   Emit   Laser           Radiation       Radiation           Radiation       Produce   Laser   Gen-   Laser   271   Gen-   Laser           Radiation   erate   Radiation       erate   Radiation       Obtain   Laser   Produce   Laser   173   Produce   Laser           Radiation       Radiation           Radiation       Provide   Laser   Provide   Laser    81   Provide   Laser           Radiation       Radiation           Radiation       Make   Laser   Form   Laser    19   Form   Laser           Radiation       Radiation           Radiation       Grow   Laser   Make   Laser    10   Make   Laser           Radiation       Radiation           Radiation       Fabri-   Laser   Radiate   Laser    9   Radiate   Laser       cate   Radiation       Radiation           Radiation       Give   Laser   Obtain   Laser    5   Obtain   Laser           Radiation       Radiation           Radiation       Create   Laser   Yield   Laser    5   Yield   Laser           Radiation       Radiation           Radiation       Manu-   Laser   Grow   Laser    0       facture   Radiation       Radiation       Prepare   Laser   Fabri-   Laser    0           Radiation   cate   Radiation       Gen-   Laser   Give   Laser    0       erate   Radiation       Radiation       Synthe-   Laser   Create   Laser    0       size   Radiation       Radiation       Emit   Laser   Manu-   Laser    0           Radiation   facture   Radiation       Radiate   Laser   Prepare   Laser    0           Radiation       Radiation       Give   Laser   Synthe-   Laser    0       Off   Radiation   size   Radiation       Ema-   Laser   Give   Laser    0       nate   Radiation   Off   Radiation       Con-   Laser   Ema-   Laser    0       struct   Radiation   nate   Radiation       Yield   Laser   Con-   Laser    0           Radiation   struct   Radiation       Acquire   Laser   Acquire   Laser    0           Radiation       Radiation       Derive   Laser   Derive   Laser    0           Radiation       Radiation                  
 
         [0067]    Results with zero frequencies are deleted. These examples show that use of validation based on the SAO KB  260  provides an exact and relevant expansion of a user query. At the same time, used dictionaries have acceptable values.  
         [0068]    The invention refines a synonym expansion of a user query by comparison of automatically generated set of synonym queries in the form “action—object” with actually existing “action—object” relations of an SAO KB. This results in a set of relevant synonyms for queries to provide exact and complete search results  
         [0069]    It will be understood that various other display symbols, emblems, colors, and configurations can be used instead of those disclosed for the exemplary embodiments herein. Also, various improvements and modifications can be made to the herein-disclosed exemplary embodiments without departing from the spirit and scope of the present invention. The system and method according to the inventive principles herein are necessarily not dependent upon the precise exemplary hardware or software architecture disclosed herein.