Multiclass Membership Determination Integrating an ID-Bound Method with Bloom Filter

Abstract

Membership determination with classification is an essential function for a variety of applications, such as network routing and packet inspection. We aim to constitute a mechanism capable of performing such a service with the considerations of efficiency and error ratio issues. The proposed method employs an array structure, in which each unit composes of multiple bits. The array houses a circular bound representation and a Bloom filter, where the former encodes the members and makes judgments of queries, while the latter acts as a secondary means for programming cases indeterministic by the former. Experimental results show that the error ratios were competitive and consistent with different levels of classification, as well as the memory space utilized. The lookup time decreased as the memory space increased. We depict specific characteristics for tackling the problem, including simplicity of data structure for encoding the members, avoidance of checking all classification IDs in the lookup process, and adoption of an auxiliary means for improving the error ratios. The ID-bound method is novel, and with the Bloom filter as the assistant, the proposed approach is robust in performances of both efficiency and error ratio.