Methods for searching a knowledge base

• US 6,185,554 B1
• Filed: 09/11/1998
• Issued: 02/06/2001
• Est. Priority Date: 10/22/1993
• Status: Expired due to Term

• Current Assignee: Nodel Corporation
• Original Assignee: Nodel Corporation
• Inventors: Bennett, Victor A.
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/151,573
• Time in Patent Office: 879 Days
• Field of Search: 707/1-6, 706/21, 706/15
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 370/911 Bridge, e.g. brouter, bus extender
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and apparatus is provided for searching a knowledge base to determine whether a search object matches any of a plurality of knowledge base entries. Initially, at least one search object bit is selected and examined to determine whether the knowledge base includes a partially matched entry that represents the same bit pattern in its corresponding bits, and when it does not, the search is terminated indicating no match. When the knowledge base does include a partially matched entry, the group of partially matched entries is identified. Thereafter, at least one previously unselected search object bit is selected and examined to determine whether the group of partially matched entries includes a further matched entry that represents the same bit pattern in its bits that correspond to the previously unselected search object bit and when it does not, the search is terminated indicating no match. When the knowledge base does include a further matched entry, the group of partially matched entries is updated to identify only the further partially matched entries. A determination is then made as to whether each bit of the search object has been selected and when it has, an indication is made of a match for the group of partially matched entries and the search is terminated. When it is determined that each search object bit has not been selected, a new search object bit is selected and the search proceeds in the manner described above.

Claims

1. An apparatus for determining whether a search object matches any entry in a knowledge base comprising:

a plurality of nodes, each node corresponding to a partial match for an entry in the knowledge base; and

a plurality of arcs connecting the nodes, each arc forming a submap which indicates a subset of nodes which correspond to entries in the knowledge base that include the partial match from the previous node, the plurality of nodes and arcs forming a neural network such that the apparatus determines whether the search object matches an entry in the knowledge base by dividing the search object into a plurality of search object bits, using a first group of search object bits to access a first node, the first node including a first submap which is used with a subsequent group of search object bits to access a subsequent node having a subsequent submap, and thereby repeating the search until all the groups of search object bits have been searched and a last submap accessed indicates that the search object either matches or does not match an entry in the knowledge base.

2. The apparatus as defined in claim 1 wherein the nodes are memory locations in a memory and the submaps are the contents of the memory location.

3. The apparatus as defined in claim 2 wherein the submap is appended to the subsequent group of search object bits to create an address to the subsequent location in the memory, which address is dependent on all prior groups of search object bits.

4. The apparatus as defined in claim 2 wherein the contents of the memory location accessed indicate a miss or a match according to a value of the contents, such that a zero value indicates a miss and a non-zero value provides the submap which is dependent on the groups of search object bits utilized.

5. The apparatus as defined in claim 1 wherein the plurality of groups of search object bits comprises five groups of search object bits.

6. An apparatus for determining whether a search object matches any entry in a knowledge base comprising:

means for selecting at least one search object bit;

means for determining whether the at least one search object bit matches a corresponding at least one bit in any entry in the knowledge base by accessing a memory location associated with the at least one search object bit, the memory location storing a submap corresponding to a subset of entries in the knowledge base which match the at least one search object bit;

means for selecting at least one subsequent search object bit such that the submap and the at least one subsequent search object bit are used to determine if the at least one subsequent search object bit matches a subsequent corresponding at least one bit in any entry in the subset of entries in the knowledge base by accessing a subsequent memory location associated with the submap and the at least one subsequent search object bit, the subsequent memory location storing a subsequent submap; and

means for repeating steps (c) and (d) using each subsequent group of search object bits and each subsequent submap until all the bits of the search object have been searched.

7. The apparatus as defined in claim 6 further comprising means for determining whether the search object matches any entry in the knowledge base based on the submap stored in the last memory location accessed.

8. The apparatus as defined in claim 6 wherein searching is terminated whenever one of the submaps indicates there is no matching entry in the knowledge base.

9. The apparatus as defined in claim 6 wherein each submap corresponds to a subset of entries in the knowledge base which have the associated group of search object bits and each subsequent group of search object bits.

10. An apparatus for determining whether a search object matches any entry in a knowledge base comprising:

a memory having a plurality of memory locations, each memory location containing a submap associated with that memory location, the memory locations and the submaps forming a neural network, wherein the memory locations are accessed by a portion of the search object, or by subsequent portions of the search object in conjunction with a submap from the previous memory location accessed, and wherein the apparatus determines whether the search object matches an entry in the knowledge base by the value of the last submap.

11. The apparatus as defined in claim 10 wherein searching is terminated whenever one of the submaps indicates there is no matching entry in the knowledge base.

12. The apparatus as defined in claim 10 wherein each submap indicates whether the associated group of bits correspond to a single match or multiple matches.

13. An apparatus which aids in searching a knowledge base to determine if an entry in the knowledge base matches a search object comprising:

a memory having a plurality of memory locations such that a group of bits from an entry in the knowledge base corresponds to at least a partial address for a particular memory location;

a submap in each memory location which has a value indicating either a subsequent group of submaps that match the portion of the search object searched thus far, or the submap indicating that a search object matches the entry in the knowledge base, wherein the structure of the memory and submaps forms a neural network.

14. The apparatus as defined in claim 13 wherein each submap indicates whether the associated group of bits correspond to a single match or to multiple matches.