×

Enhanced searching method and apparatus for variable bit chains

  • US 6,421,660 B1
  • Filed: 12/18/1998
  • Issued: 07/16/2002
  • Est. Priority Date: 12/19/1997
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for searching input variable bit chain keys having a maximum length value, in a Patricia tree based data base, each node in the data base storing a direct parent address pointing to a previous node, two addresses pointing to following nodes, a data value or a pointer to a data value, a bit chain key zero padded up to said maximum length value, the length of said key and the rank of a bit to be tested at this node in the input key;

  • said method comprising the steps of;

    A. pointing to a root node of the tree, B. padding the input key with zeros up to the maximum length value and reading the bit to test in the input key and according to the value of the bit to test pointing to the following node address, C. repeating step B and reaching the following nodes until the rank of the bit to test of a following node is equal to or greater than the rank of the bit to test of the previous node, the previous node thereby becoming a terminating node, D. comparing the key stored in said terminating node on its stored length with the zero padded input key, E. if a match is found in step D, terminating the search, F. if a match is not found in step D, pointing to the parent node of the terminating node using the direct parent address, the parent node thereby becoming a new terminating node, and G. repeating steps D, E and F until the root node is reached or a match is found in step D.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×