Patent ID: 7349415
Filing Date: 2008-03-25
Classification: G06F,H04L

Abstract:
1. A method performed by a traversal engine for traversing a tree data structure stored in one or more memory devices based on an input search data string, the method comprising: receiving a search progression context of a partially completed traversal of the tree data structure from a requesting device external to the traversal engine, the search progression context including a next node address; and resuming said traversal of the tree data structure from state identified by said received search progression context, said resumed traversal of the tree data structure including performing operations for further traversing the tree data structure based on one or more particular portions of the input string, said operations including: distributing a lookup request including the next node address to one of said one or more memory devices; receiving a lookup result from said one or more memory devices, the lookup result including a search node; updating a current best match identifier in response to determining that a new best match exists; indexing into a current level extending bitmap of the search node based on said particular portion to determine whether or not a matching next level node exists; in response to said determining that a matching next level node does not exist: determining a search result for said traversing of the tree data structure based on the current best match identifier or on a pointer in the search node to a leaf node; else in response to said determining that a matching next level node does exist: generating a new value of the next node address, and either continuing said further traversal of the tree data structure for a next particular portion of the input string or sending a new value for the search progression context corresponding to a further partial traversal of the tree data structure to the requesting device external to the traversal engine.