Random filter and its analysis*

Abstract

The search filter is a special mechanism that can be used to speed up the search process of any search technique. In this paper, we propose a new search filter and show that the new approach is better than the Bloom filter, which is a well-known search filter proposed by B. H. Bloom in 1970. We shall show the superiority of our approach by proving theorems concerned about the average time required for testing a given key and the probability of false drop. We also observe that the operating environment plays an important role in the performance of search filters. Hence, we shall show the way to obtain an optimal search filter under a given operating environment by mathematical model.

Keywords:

• Search filter
• differential file
• hash