Method of improving the lookup performance of tree-type knowledge base searches
First Claim
1. A method for determining whether a search object matches an entry in a knowledge base, wherein the knowledge base comprises a decision tree structure comprising a plurality of search nodes, and a plurality of links joining two search nodes, said method comprising:
- storing a first portion of the decision tree structure in a first memory, wherein the first portion comprises a first plurality of search nodes and interconnecting links;
storing a second portion of the decision tree structure in a second memory, wherein the second portion comprises a second plurality of search nodes and interconnecting links;
reading a first search node from the first memory;
comparing the first search node with at least a portion of the search object; and
based on the comparing step, traversing a search path from the first search node to a second search node via the joining link.
8 Assignments
0 Petitions
Accused Products
Abstract
A decision tree, representing a knowledge base, is segmented into at least two decision tree portions. The lower portion includes the tree entry point and is stored in a memory element with a faster access time than the upper portion, which includes the terminating element of the decision tree. Thus during the process of reading the tree entries for comparing them with the search object, the search entries in the lower portion of the tree can be read faster than the search entries in the upper portion, resulting in a faster traversal through the entire decision tree.
-
Citations
25 Claims
-
1. A method for determining whether a search object matches an entry in a knowledge base, wherein the knowledge base comprises a decision tree structure comprising a plurality of search nodes, and a plurality of links joining two search nodes, said method comprising:
-
storing a first portion of the decision tree structure in a first memory, wherein the first portion comprises a first plurality of search nodes and interconnecting links;
storing a second portion of the decision tree structure in a second memory, wherein the second portion comprises a second plurality of search nodes and interconnecting links;
reading a first search node from the first memory;
comparing the first search node with at least a portion of the search object; and
based on the comparing step, traversing a search path from the first search node to a second search node via the joining link. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An apparatus for determining whether a search object matches any entry in a knowledge base, wherein the knowledge base comprises a decision tree structure comprising a plurality of links between adjacent search nodes, said apparatus comprising:
-
a first memory storing a first portion of the decision tree structure;
a second memory storing a second portion of the decision tree structure;
a processor for matching at least a portion of the search object with a search node and for traversing through the decision tree structure in response to the match. - View Dependent Claims (19, 20, 21, 22)
-
-
23. An apparatus for determining whether a search object matches any entry in a knowledge base, wherein the knowledge base comprises a decision tree structure comprising a plurality of links connecting adjacent search nodes, said method comprising:
-
a first processor;
a second processor;
a first memory storing a first portion of the decision tree structure;
a second memory storing a second portion of the decision tree structure;
wherein said first processor accesses said first memory, and wherein said second processor accesses said second memory for determining the search node that matches at least a portion of said search object. - View Dependent Claims (24, 25)
-
Specification