Patent ID: 7546281
Filing Date: 2009-06-09
Classification: G06F

Abstract:
1. A method to reduce the size of a ternary data structure database, the method comprising the acts of: providing the database in a memory such that the database includes a listing of N rules, where N>=2, such that each rule (R) of the N rules represents a row of data in the database and has an associated integer index having a value of 0, 1, 2 . . . N and includes bit characters 0, 1 and * (wild card or don't care) representing values of bits included in each rule in the database; tagging each rule with a valid bit having an initial value of 1; processing the N rules using a redundancy test algorithm that identifies which rules of the database are included in other rules of the database and therefore should be deleted from the data base as being redundant, such that the redundancy test algorithm includes the following steps: deleting redundant rules Ri from the database for which an associated tagged valid bit has been reset to 0; processing remaining N rules of the database which have not been deleted as being redundant and which have a value of 1 for an associated tagged valid bit using a rule reduction algorithm to identify which of the remaining N rules are identical to other remaining N rules in all bit positions except exactly one bit position; and deleting from the database remaining N rules which have been identified as being identical to other remaining N rules in all bit positions except exactly one bit position.