Patent ID: 8005869

Claim:
A method for compressing search tree structures used in rule classification, the method comprising: classifying packets of information based on filter rules; compressing a tree structure comprising multiple levels of single bit test nodes and leaf nodes, the tree structure having been previously built from the filter rules in which each leaf node of the tree structure includes a given filter rule for classifying a given packet; storing the compressed tree structure in a first memory structure of a storage such that the multiple levels of single bit test nodes and leaf nodes can be accessed from the first memory structure through a single memory access of the storage; collecting single bit test nodes of the tree structure that are in a lowest level of the tree structure; separately storing only the collected single bit test nodes of the tree structure that are in the lowest level of the tree structure within a second memory structure of the storage that is contiguous to the first memory structure; collecting leaf nodes of the tree structure; and separately storing only the collected leaf nodes of the tree structure within a third memory structure of the storage that is contiguous to the second memory structure.