Method and system for testing filter rules using caching and a tree structure
US6529897B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 31, 2000 |
| Grant date | Mar 4, 2003 |
| Priority date | — |
| Expiry date | Mar 31, 2020 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and system for testing a plurality of filter rules in a computer system is disclosed. The plurality of filter rules are used with a key that is capable of matching at least one of the plurality of filter rules. The at least one filter rule corresponds to at least one action. The computer system has a cache including a plurality of bins and a decision tree. The method and system include searching a plurality of stored keys in the cache for the key. Preferably, this search of the cache for the key includes determining whether a stored key exactly matches the key. A plurality of stored filter rules corresponds to the plurality of stored keys. A plurality of stored actions corresponds to the plurality of stored filter rules. The cache stores each of the plurality of stored keys and at least one stored action in each bin of a portion of the bins. The method and system also include obtaining the at least one action from the cache if the key is found in plurality of stored keys and otherwise obtaining the at least one action using the decision tree. Preferably, searches of the decision tree and cache start simultaneously. The decision tree search is terminated if the key is found…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.