Method of improving the lookup performance of tree-type knowledge base searches

• US 20030120621A1
• Filed: 12/21/2001
• Published: 06/26/2003
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Calle, Mauricio, Vangati, Narender R., Kirk, James T., Baker, William Edward, McDaniel, Betty A.
• Granted Patent: US 7,246,102 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: Y10S 706/934 Information retrieval or Information management
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

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.

2. The method of claim 1 further comprising reading the second search node and comparing at least a portion of the search object with the second search node.

3. The method of claim 2 wherein the steps of reading, comparing and traversing are repeated until the second portion of the decision tree is traversed to an end thereof.

4. The method of claim 1 wherein the step of reading is executed by a processor formed in an integrated circuit, and wherein the first memory is formed on the integrated circuit, such that the step of reading search nodes from the first memory executes faster than the step of reading search nodes from the second memory.

5. The method of claim 1 wherein the first portion of the decision tree structure comprises the search nodes near the first search entry.

6. The method of claim 1 wherein the decision tree structure comprises a plurality of levels, each comprising a plurality of search nodes, and wherein the search nodes comprising one of the plurality of levels are connected to search nodes comprising another one of the plurality of levels by links.

7. The method of claim 1 wherein a predetermined number of lower levels of the plurality of levels are stored in the first memory, and wherein the remaining plurality of levels are stored in the second memory.

8. The method of claim 7 wherein the predetermined number of lower levels of the plurality of levels have a faster read access time than the remaining plurality of levels.

9. The method of claim 1 wherein the access time parameter of the first memory is lower than the access time of the second memory.

10. The method of claim 1 wherein the search object comprises a plurality of symbols.

11. The method of claim 10 wherein the symbols comprise a plurality of binary bits.

12. The method of claim 1 wherein the knowledge base comprises a classification engine of a communications network processor for determining an attribute of the data input thereto, and wherein the second portion of the decision tree ends in a plurality of terminating nodes, the method further comprising repeating the steps of reading, comparing and traversing until a terminating node is reached, wherein the terminating node identifies the attribute of the input data.

13. The method of claim 1 wherein the second portion of the decision tree ends in a plurality of terminating nodes, the method further comprising repeating the steps of reading, comparing and traversing until a terminating node is reached, such that the terminating node matches at least a portion of the search object.

14. The method of claim 1 wherein each one of the plurality of search nodes comprises an instruction and an address field, wherein the step of comparing further comprises comparing at least a portion of the search object with the instruction, and wherein the address field determines the second search node based on the comparing step.

15. The method of claim 1 wherein the decision tree structure comprises a plurality of contiguous tree levels, wherein each tree level further comprises a search node and link to a search node of the next adjacent tree level.

16. The method of claim 15 wherein the first portion of the decision tree structure comprises a predetermined number of contiguous tree levels and the second portion of the decision tree structure comprises the remaining contiguous tree levels.

17. The method of claim 15 wherein the first portion of the decision tree structure comprises a portion of one or more contiguous tree levels.

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.

19. The apparatus of claim 18 wherein the decision tree structure ends in a plurality of terminating nodes and wherein the processor traverses through the decision tree structure until a terminating node is reached, wherein the terminating node matches at least a portion of the search object.

20. The apparatus of claim 18 wherein the processor and the first memory are formed in the same integrated circuit, such that reading search entries from the first memory is faster than reading search entries from the second memory.

21. The apparatus of claim 18 wherein the first memory has a first access time and the second memory has a second access time, and wherein the first access time is faster than the second access time.

22. The apparatus of claim 18 wherein the decision tree structure comprises a plurality of levels, each comprising a plurality of search nodes, and wherein the search nodes comprising one of the plurality of levels are connected to search nodes comprising an adjacent one of the plurality of levels by a link, and wherein the first memory stores at least the first level.

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.

24. The apparatus of claim 23 wherein the first processor compares at least a portion of the search object with one or more search nodes stored in the first memory to traverse through the first portion;

and

wherein after the first portion of the decision tree has been traversed, the second processor compares at least a portion of the search object with one or more search entries stored in the second memory to traverse through the second portion until a search node matching at least a portion of the search object is determined.

25. The apparatus of claim 23 wherein the first processor and the second processor simultaneously execute tree searches for a plurality of search trees.