Patent Number: 6,298,340

Title: System and method and computer program for filtering using tree structure

Abstract: A classification system includes a software managed tree testing bits from a key which labels an item. The bits are chosen by application of the Choice Bit Algorithm to the Rules in a Database of Rules. A controller including logic parses an unknown Key for bits to be tested in the decision nodes of a binary tree. Tests dictated by the tree are conducted in a predetermined way until all but one Rule from the database or all but a few Rules from the database are eliminated from consideration, whereupon the Key is fully tested by the one remaining Rule or in a lattice constructed of the remaining plurality of Rules, to determine an action to enforce on the item. Certain compare tests are used in the binary tree for the case that otherwise identical or similar rules are applied to integer ranges of key values which do not fall upon power of 2 boundaries. Furthermore, some very frequently occurring rules in such final tests might be designated as secondary rules, the remaining rules designated as primary rules, the entire decision tree recalculated using only primary rules, and the primary rules then connected to secondary rules only when logically necessary by means of a system of pointers making use of relative priorities of rules.

Inventors: Calvignac; Jean Louis (Cary, NC), Corl, Jr.; Everett Arthur (Raleigh, NC), Gallo; Anthony Matteo (Apex, NC), Heddes; Marco C. (Raleigh, NC), Jeffries; Clark Debs (Durham, NC), Patel; Piyush Chunilal (Cary, NC), Rinaldi; Mark Anthony (Durham, NC), Verrilli; Colin Beaton (Apex, NC)

Assignee: International Business Machines Corporation

International Classification: G06F 17/30 (20060101); G06F 017/30 ()

Expiration Date: 10/02/2018