Method of improving the lookup performance of three-type knowledge base searches
First Claim
1. A computer-implemented method for retrieving an attribute associated with a data packet comprising a search object using a decision tree structure comprising a plurality of search nodes defining a plurality of paths through the decision tree structure, at least one path comprising a plurality of search nodes, one or more joining links between adjacent search nodes, and a leaf, said method comprising:
- storing a first portion of the decision tree structure in a first memory, having a first memory access time, wherein the first portion comprises a first set of one or more search nodes, zero or more joining links, and zero or more leaves;
storing a second portion of the decision tree structure in a second memory, having a second memory access time, wherein the second portion comprises a second set of one or more search nodes, zero or more joining links, and one or more leaves, and wherein the first memory access time is less than the second memory access time;
implementing one or more times, starting with a root search node in the first memory, the steps of;
(1) reading at least a portion of one or more paths through a current search node from one of the first memory and the second memory;
(2) comparing, the current search node, at least a portion of the search object with the at least a portion of the one or more paths through the current search node; and
(3) based on a result of the step of comparing, traversing a search path from the current search node to;
(i) a next search node via the joining link therebetween, or (ii) a leaf, wherein the search path terminates atthe leaf providing the attribute associated with the data packet; and
retrieving the attribute associated with the data packet.
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.
53 Citations
34 Claims
-
1. A computer-implemented method for retrieving an attribute associated with a data packet comprising a search object using a decision tree structure comprising a plurality of search nodes defining a plurality of paths through the decision tree structure, at least one path comprising a plurality of search nodes, one or more joining links between adjacent search nodes, and a leaf, said method comprising:
-
storing a first portion of the decision tree structure in a first memory, having a first memory access time, wherein the first portion comprises a first set of one or more search nodes, zero or more joining links, and zero or more leaves; storing a second portion of the decision tree structure in a second memory, having a second memory access time, wherein the second portion comprises a second set of one or more search nodes, zero or more joining links, and one or more leaves, and wherein the first memory access time is less than the second memory access time; implementing one or more times, starting with a root search node in the first memory, the steps of; (1) reading at least a portion of one or more paths through a current search node from one of the first memory and the second memory; (2) comparing, the current search node, at least a portion of the search object with the at least a portion of the one or more paths through the current search node; and (3) based on a result of the step of comparing, traversing a search path from the current search node to;
(i) a next search node via the joining link therebetween, or (ii) a leaf, wherein the search path terminates atthe leaf providing the attribute associated with the data packet; and retrieving the attribute associated with the data packet. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. An apparatus for retrieving an attribute associated with a data packet comprising a search object using a decision tree structure comprising a plurality of search nodes defining a plurality of paths through the decision tree structure, at least one path comprising a plurality of search nodes, one or more joining links between adjacent search nodes, and a leaf, said apparatus comprising:
-
a first memory for storing a first portion of the decision tree structure, the first memory having a first memory access time; a second memory for storing a second portion of the decision tree structure, the second memory having a second memory access time wherein the first memory access time is less than the second memory access time; and a processor for retrieving the attribute associated with the data packet by implementing one or more times, starting with a root search node in the first memory, the steps of; (1) reading at least a portion of one or more paths through a current search node from one of the first memory and the second memory; (2) comparing, at the current search node, at least a portion of the search object with the at least a portion of the one or more paths through the current search node; and (3) based on a result of the step of comparing, traversing a search path from the current search node to;
(i) a next search node via the joining link therebetween, or (ii) a leaf,wherein the search path terminates at the leaf. - View Dependent Claims (21, 22)
-
-
23. An apparatus for retrieving an attribute associated with a data packet comprising a search object using a decision tree structure comprising a plurality of paths through the decision tree structure, at least one path comprising a plurality of search nodes, one or more joining links between adjacent search nodes, and a leaf, said apparatus comprising:
-
a first processor for accessing a first memory; a second processor for accessing a second memory; the first memory having a first memory access time and for storing a first portion of the decision tree structure; and the second memory having a second memory access time and for storing a second portion of the decision tree structure wherein the first memory access time is less than the second memory access time, wherein said first processor and said second processor are for retrieving the attribute associated with the data packet by implementing one or more times, starting with a root search node in the first memory, the steps of; (1) reading at least a portion of one or more paths through a current search node from one of the first memory and the second memory; (2) comparing, at the current search node, at least a portion of the search object with the at least a portion of the one or more paths through the current search node; (3) based on a result of the step of comparing, traversing a search path from the current search node to;
(i) a next search node via the joining link therebetween, or (ii) a leaf,wherein the search path terminates at the leaf. - View Dependent Claims (24, 25)
-
-
26. Apparatus comprising:
-
a first memory for storing a first portion of a decision tree structure, the first memory having a first access time; a second memory for storing a second portion of the decision tree structure, the second memory having a second access time greater than the first access time; and at least one processor for traversing a search path in the decision tree structure corresponding to a specified search object, wherein; the specified search object comprises (1) a first part contained in the first portion of the decision tree structure and (2) a second part contained in the second portion of the decision tree structure; and the at least one processor traverses (1) a first part of the search path by accessing the first memory to identify the first part of the specified search object and (2) a second part of the search path by accessing the second memory to identify the second part of the specified search object. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34)
-
Specification