Filter Rule Tree with Frequent Choices Moved to Root
Original Publication Date: 2000-Nov-01
Included in the Prior Art Database: 2003-Jun-19
The goal filtering is to perform tests to eliminate all but one or a few filter rules which might apply to a key. We seek to minimize both the time required to test and the complexity of the tests--competing desiderata. In prior art, bits are chosen to be tested. The tests occur in a binary search tree. At a leaf of such a tree, a certain combination of bits in a key has been tested and all but one or all but a few filter rules have been eliminated from further consideration. In the present disclosure, we can force certain rules to become the first tests of a tree. The selected rules for forcing might be fed to the bit choosing algorithm as a subapplication of it. The rules to force would be rules which appear in many leafs after straightforward bit choosing. For example, any rule which appears in at least 10% of the leafs might be forced to the root of the tree or to the first few nodes after the root. Especially beneficial would be rules selected for forcing which have no intersections among themselves (no one key fulfills the forced rules). In tests with a set of real filter rules, the size of the decision tree was reduced from 67 nodes to 50 nodes by one application of forcing a frequently occurring rule to the root of the tree. We anticipate that the invention would be useful with large rule sets when storage resources for a software managed tree are limited.