×

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

  • US 7,246,102 B2
  • Filed: 12/21/2001
  • Issued: 07/17/2007
  • Est. Priority Date: 12/21/2001
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 8 Assignments
Timeline View
Assignment View
    ×
    ×