Partition search filter and its performance analysis

A search filter is used to filter out the items that do not exist in the se arch space. For a search filter, the false drop probability and the average testing time are two important factors estimated. Bloom filter and Random filter are two kinds of well-known search filters proposed by Bloom and by Wang et al., respectively. Chang and Leu had proved that Random filter does not guarantee to be superior to Bloom filter. In other words, both Random and Bloom filters have their own fittest performance conditions. This paper proposes a new search filter mechanism, Partition filter, which improves t he above two methods with respect to the two criteria, the false drop proba bility and the average testing time, by taking the advantages of Bloom and Random filters. (C) 1999 Elsevier Science Inc. All rights reserved.