In one aspect, the present invention reduces the amount of low-latency memory needed for rules-based packet classification by representing a packet classification rules database in compressed form. A packet processing rules database, e.g., an ACL database comprising multiple ACEs, is preprocessed to obtain corresponding rule fingerprints. These rule fingerprints are much smaller than the rules and are easily accommodated in on-chip or other low-latency memory that is generally available to the classification engine in limited amounts. The rules database in turn can be stored in off-chip or other higher-latency memory, as initial matching operations involve only the packet key of the subject packet and the fingerprint database. The rules database is accessed for full packet classification only if a tentative match is found between the packet key and an entry in the fingerprint database. Thus, the present invention also advantageously minimizes accesses to the rules database.