Method and apparatus to automatically test and modify a searchable knowledge base

[0002] 1. Field of the Invention

[0003] The present invention pertains to the field of searchable knowledge bases. More particularly, this invention relates to the art of eliminating duplicate information, identifying missing information, and verifying the validity of information in a searchable knowledge base.

[0004] 2. Background

[0005] Searchable knowledge bases, such as databases, are used in a wide range of applications. For instance, a database can be used for customer service support at a help desk. A help desk operator may use a customer's question as a query to a database of solutions or to a database of an index to solutions. In which case, a search engine may retrieve one or more solutions, or links to solutions, based on a comparison of the query to the database entries.

[0006] When database entries are retrieved, one or more of the entries, or the items of information to which the entries point, may be duplicates. For instance, a database may index items of information on a network, such as the internet. The same items of information may be accessible at multiple host systems, so that each duplicate item of information may be separately indexed in the database. In which case, a search engine may retrieve database entries that point to different locations, although the locations may contain duplicate information. Sorting through a list of duplicate information, or pointers to duplicate information, can be time consuming and misleading.

[0007] Furthermore, a knowledge base generally will not have a response for every query. For instance, certain queries may not retrieve any responses at all. Even if one or more responses are retrieved, the responses may still be invalid. That is, a response may have nothing to do with the subject matter of a query. For instance, a search engine may simply look for database entries which contain one or more of the same words as the query, and rank the entries based on the number of times one or more words from the query appear in the database entry. If a query is not carefully crafted to avoid potentially misleading words, responses to the query may be irrelevant. Also, words may have different meanings in different contexts, so even a carefully crafted query may retrieve responses that are not related to the topic of the query. A query for which no response, or only irrelevant responses, are retrieved may indicate a “hole” in the knowledge base. If “holes” are not identified as they are encountered, a potentially valuable source of information may be lost that could be used to improve the content of the database over time.

[0008] Therefore, a need exists for an improved method and apparatus to automatically eliminate duplicate database information and identify potential holes in a knowledge base.

[0009] In accordance with a first aspect of the present invention, duplicate responses to a query are automatically determined and eliminated. In accordance with a second aspect of the present invention, invalid responses to a query are automatically determined and eliminated. In accordance with a third aspect of the present invention, an indication is generated if no responses are returned from a knowledge base for a query, in which case provision of a response is automatically facilitated so that at least one response will be returned from the knowledge base for future resubmissions of the query. In one embodiment, all three aspects of the present invention are performed for a given query.

[0010] Examples of the present invention are illustrated in the accompanying drawings. The accompanying drawings, however, do not limit the scope of the present invention whatsoever. Like references in the drawings indicate similar elements.

[0011] FIG. 1 illustrates one embodiment of the present invention.

[0012] FIG. 2 illustrates one embodiment of a stripped query.

[0013] FIG. 3 illustrates one embodiment of part of a stripped response and some synonyms of the words remaining in the stripped response.

[0014] FIG. 4 demonstrates one embodiment of the present invention.

[0015] FIG. 5 illustrates a hardware system operative to perform the functions of one embodiment of the present invention.

[0016] FIG. 6 illustrates one embodiment of a storage medium to contain machine readable instructions for one embodiment of the present invention.

[0017] In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details and that the present invention may be practiced in a variety of alternate embodiments. In other instances, well known methods, procedures, components, and circuits have not been described in detail.

[0018] FIG. 1 illustrates one embodiment of the present invention. As discussed below, database testing unit 110 automatically tests and modifies a searchable knowledge base stored or indexed database 130. Database testing unit 110 eliminates duplicate database entries, either from a list of entries retrieved from database 130 or from database 130 itself, and identifies potential holes in the knowledge base when no entries, or potentially invalid entries, are retrieved in response to a query.

[0019] As shown in FIG. 1, a query is provided to search engine 120 and database testing unit 110. Search engine 120 accesses database 130 and provides search output to database testing unit 110. Any number of search engines and databases can be used for search engine 120 and database 130. Search engine 120 may be locally accessed or remotely accessed over a network.

[0020] In the illustrated embodiment, database 130 stores a knowledge base wherein each database entry is an item of information in the knowledge base. Database 130 may be locally accessed or remotely accessed over a network. In alternate embodiments, database 130 may store an index wherein each database entry is a link to an item of information in a knowledge base stored elsewhere. In an index database, a database entry may include the full text of the item of information to which the entry points, or just key words from the item of information. An indexed knowledge base may be centrally stored or distributively stored on a network such as the internet.

[0021] When search engine 120 identifies a database entry corresponding to a query, a response is included in the search output for the identified entry. The search output may include several responses. In the illustrated embodiment, a response consists of an item of information from the knowledge base. In alternate embodiments, a response may be an index to an item of information stored elsewhere.

[0022] The search output is provided to response detector 135 within database testing unit 110 to determine if no responses were retrieved for the query. That is, if the search output does not include at least one response, a “hole” in the knowledge base may be indicated. In one embodiment, responses are provided in an identifiable format. If anything other than the identifiable format is provided, response detector 135 can recognize it as something other than a response. If no responses are received, response detector 135 asserts the NO RESPONSE signal.

[0023] The NO RESPONSE signal can flag the query for later consideration. For instance, if the query is related to the subject matter of the knowledge base, a new item of information may be added to the knowledge base, or an existing item of information may be modified, so that an appropriate response will be retrieved for that particular query or a similar query in the future.

[0024] If one or more responses are retrieved, the responses are provided to duplicate remover 140 to identify and remove the duplicates, if any. In certain embodiments, duplicate remover 140 removes duplicate responses from the search output so that the list of responses a user receives contains no duplicates. For instance, duplicate remover 140 can perform a text comparison of each response it receives to determine if one or more responses are duplicate, and then remove the duplicates. Any number of text comparison schemes can be used.

[0025] In alternate embodiments, duplicate remover 140 may also remove duplicate database entries from database 130 so that search engine 120 will not provide the duplicate information in the future. For instance, database testing unit 110 can access database 130 with the ELIMINATE DUPLICATES signal to eliminate unnecessary duplicate entries.

[0026] In alternate embodiments in which database 130 stores an index to a knowledge base stored elsewhere, each response received from database 130 may be unique, but the items of information to which the responses point may be duplicative. For instance, if the knowledge base is distributively stored on a network, such as the internet, the same information may be stored at, or be accessible from, multiple host systems. Then, if search engine 120 generates or updates the index stored in database 130 with an automatic procedure, such as a “web crawler,” database 130 may include entries for each host system even though the information stored at the host systems is duplicative. For instance, a web crawler may visit each host system where items of information can be stored and look for changes or additions. If an item of information is copied from one location to another, and the web crawler visits both locations, two unique database entries may be created for the same information.

[0027] In which case, duplicate remover 140 may access the items of information at their respective host systems to identify the duplicates. In one embodiment, duplicate remover 140 performs a content comparison wherein the textual content of each indexed item of information is compared to the textual content of every other indexed item of information. If duplicate items or substantially identical items are identified, only one database entry needs to be retained for that item of information and the rest can be eliminated. Any number of text or content comparison schemes can be used.

[0028] Under certain circumstances, however, eliminating indexed database entries may result in failure to locate the most recent data. For instance, if duplicate information is remotely located at two separate host systems, one item of information may be updated without corresponding updates being made to the other. If only one index entry has been retained, the updated information may not be indexed in database 130. If search engine 120 refreshes the database frequently, however, loosing the most recent information will be less likely. For instance, a web crawler can update database 130 more or less frequently depending on the nature of the information being indexed.

[0029] Duplicate remover 140 can use any number of criteria to decide which one of a plurality of duplicate entries to keep. For instance, duplicate remover 140 may simply keep the first occurrence of an entry and remove all duplicates. In other embodiments, particularly for a distributed knowledge base, duplicate remover 140 may also take into consideration the accessibility of the respective items of information. For instance, the database entry that points to the fastest host system, or least trafficked host system, may be preferred over database entries that point to slower or busier host systems. Similarly, a master copy may be preferred over other copies.

[0030] In addition to eliminating duplicate responses, if any, database testing unit 110 uses validation unit 145 to test the validity of the responses. In the illustrated embodiment, duplicate responses are eliminated first and only the remaining responses are tested for validity.

[0031] Depending on how search engine 120 operates, one or more responses retrieved from database 130 may be irrelevant to the subject matter of the query and therefore invalid. For instance, in one embodiment, search engine 120 compares words in a query to words in all of the database entries, and ranks the database entries based on the number of times words in the query appear in each database entry. If a query is not carefully crafted, or if the meaning of a word depends on its context, search engine 120 may retrieve invalid responses.

[0032] In the illustrated embodiment, database testing unit 110 first provides the query and the responses to language stripper 150. Language stripper 150 filters out common words in the query and the responses. For instance, conjunctions, articles, prepositions, pronouns, etc., can all be filtered out. Then, synonym generator 155 generates a list of synonyms for each remaining word in the stripped responses. Key word comparison unit 160 compares the words from the synonym list to the remaining words in the query. If at least a certain percentage of the words in a query also appear in the synonym list, then the solution is presumed to be valid. If less than the certain percentage of words appear in the synonym list, the INVALID RESPONSE signal can flag the response and the corresponding query for later consideration. For instance, if the query is valid and all of the responses to the query are irrelevant, a new item of information may be added to the knowledge base, or an existing item of information may be modified, so that an appropriate response will be retrieved for that particular query or a similar query in the future.

[0033] In certain embodiments, responses that are presumed invalid are also removed from a list of responses provided to a user. In which case, if duplicate responses have also been removed, a user is more likely to receive a shorter list of more relevant responses. At the same time, any flagged queries and/or responses can be saved and provided to a database manager for appropriate evaluation.

[0034] In one example, the apparatus shown in FIG. 1 may be used for computer-related customer service support. In which case, a customer service operator may accept calls from computer users and submit queries based on the calls to a computer-related knowledge base stored in database 130. An example query is, “My mouse cursor fails to track the movement of my mouse.” Response detector 135 determines if no responses are retrieved. Duplicate remover 140 eliminates duplicate information, if any. Then, remaining responses are tested for validity. The word “track” may be misleading for search engine 120. For instance, some responses may deal with tracks on compact disks or tracking a video tape. Specifically, part of an example response is, “If your CD player fails to find a track on a CD, start by cleaning the surface of the compact disk . . . ” Language stripper 150 strips the query and the responses. FIG. 2 illustrates one embodiment of the stripped query. FIG. 3 illustrates one embodiment of part of a stripped response. Synonym generator 155 generates synonyms, as shown in FIG. 3, for words remaining in the responses. Synonyms can be compiled from a thesaurus database, including topic-related lexicon, such as “drive” for “player,” and “compact disk” for “CD.” The words from the stripped response as well as their synonyms can be added to the synonym list and compared to the words in the stripped query. In the illustrated example, 40% of the words in the query appear on the synonym list. According to one embodiment, a 40% match suggests an invalid response. In which case, keyword comparison unit 160 can flag the response and the query for later consideration and eliminate the response from those retrieved by asserting the INVALID RESPONSE signal.

[0035] In alternate embodiments in which database 130 stores an index to a knowledge base stored elsewhere, database testing unit 110 may use the responses provided by search engine 120 to retrieve the items of information and provide the items of information to language stripper 150, synonym generator 155, and keyword comparison unit 160 for validation. Alternately, the validation may be performed based on the text indexed in database 130.

[0036] In alternate embodiments, one or more of the components in FIG. 1 may be re-arranged, combined, eliminated, and/or duplicated. Additional elements may also be added, such as a storage medium to store queries for which no responses or only potentially invalid responses were retrieved. Furthermore, alternate embodiments may use different validation criteria, wherein, for instance, a synonym list may be generated for a query instead of or in addition to a synonym list for a response. The valid response threshold level, or the percentage of matching words between query and response, may be a user specified variable, a function of the respective lengths of the query and the responses, etc. In certain embodiments, synonym generator 155 attempts to classify each word as a noun, verb, adjective, etc. based on context before generating a synonym list.

[0037] Queries may come from a number of different sources. For instance, a query may come from an on-line self help service, a help desk operator, etc. Queries from numerous sources may be accumulated to provide test cases for a knowledge base. Duplicate entries can automatically be removed and potential holes in the knowledge base can automatically be flagged by applying the accumulated test cases to the knowledge base. The percentage of potentially invalid responses can also be used as an indication of how well a search engine is working.

[0038] FIG. 4 demonstrates the operation of one embodiment of database testing unit 110. In step 410, database testing unit 110 receives a query and a corresponding response or responses, if any. In step 420, response detector 135 checks for responses. If no responses are found, an indication of no responses is given in step 425, and the process ends. If at least one response is found, duplicate remover 140 eliminates duplicate responses, if any, in step 430. Then language stripper 150 strips the query of common words in step 440, and strips a response of common words and provides synonyms of the remaining words in step 450. In step 460, keyword comparison unit 160 compares the stripped query with the stripped response and synonyms. In step 470, if less than X percentage of the words in the stripped query appear in the stripped response and synonyms, an invalid response is indicated in step 480. If additional responses remain in step 490, the process returns to step 450. Otherwise, the process ends.

[0039] Any number of hardware systems can be used to perform the functions of database testing unit 110. For example, database testing unit 110 may be represented by a broad category of computer systems known in the art, such as a computer system equipped with a high performance microprocessor(s), such as the Pentium® processor, Pentium® Pro processor, or Pentium® II processor manufactured by and commonly available from Intel Corporation of Santa Clara, Calif., or the Alpha® processor manufactured by Digital Equipment Corporation of Maynard, Mass..

[0040] FIG. 5 illustrates one embodiment of a suitable hardware system. In the illustrated embodiment, the hardware system includes processor 510 coupled to high speed bus 505, which is coupled to input/output (I/O) bus 515 through bus bridge 530. Temporary memory 520 is coupled to bus 505. Permanent memory 540 is coupled to bus 515. Display device 570, keyboard 580, and communications interface 590 are also coupled to bus 515.

[0041] Certain embodiments may include additional components, may not require all of the above components, or may combine one or more components. For instance, temporary memory 520 may be on-chip with processor 510. Alternatively, permanent memory 540 may be eliminated and temporary memory 520 may be replaced with an electrically erasable programmable read only memory (EEPROM), wherein software routines are executed in place from the EEPROM. Some implementations may employ a single bus to which all of the components are coupled. Additional components may be included in the hardware system, such as additional processors, storage devices like a CD ROM, memories, and other peripheral components known in the art, and the additional components may be coupled to one or more additional buses through additional bus bridges.

[0042] In one embodiment, database testing unit 110 as discussed above, is implemented as a series of software routines run by the hardware system of FIG. 5. These software routines comprise a plurality or series of instructions to be executed by a microprocessor in a hardware system, such as processor 510 of FIG. 5. Initially, the series of instructions can be stored on a storage device, such as permanent memory 540. As shown in FIG. 6, it is to be appreciated that the series of instructions can be machine executable instructions 610 stored using any machine readable storage medium 620, such as a diskette, CD-ROM, magnetic tape, digital video or versatile disk (DVD), laser disk, ROM, Flash memory, etc. It is also to be appreciated that the series of instructions need not be stored locally, and could be received from a remote storage device, such as a server on a network, a CD ROM device, a floppy disk, etc., through, for instance, communications interface 590. The instructions may be copied from the storage device into temporary memory 520 and then accessed and executed by processor 510. In one implementation, these software routines are written in the C++ programming language. It is to be appreciated, however, that these routines may be implemented in any of a wide variety of programming languages.

[0043] In alternate embodiments, the present invention is implemented in discrete hardware or firmware. For example, one or more application specific integrated circuits (ASICs) could be programmed with the above described functions of the present invention. In another example, database testing unit 110 could be implemented in one or more ASICs on an additional circuit board and the circuit board could be inserted into the hardware system of FIG. 5.

[0044] Thus, a method and apparatus to automatically eliminate duplicate database information and identify holes in a knowledge base is described. Whereas many alterations and modifications of the present invention will be comprehended by a person skilled in the art after having read the foregoing description, it is to be understood that the particular embodiments shown and described by way of illustration are in no way intended to be considered limiting. Therefore, references to details of particular embodiments are not intended to limit the scope of the claims.