2d random filter and analysis ^∗

^∗This research was supported by the National Science Council, Taiwan, R.O.C. under contract:NSC 79-0408-E009-01 (1989)

Abstract

Search filter is an additional search mechanism working well in case that most items to be searched fall outside of search space. We propose a new search filter and the new approach is better than existing search filters. The new strategy, 2D Random filter, configurates its hash space as a two-dimensional bit array rather than a one-dimensional bit vector as in previous works. The new filter will be analyzed both on its false drop probability and response time. A generalization to k-Dimensional configuration is also given and analyzed. Analytical results show that 2D Random filter has smaller false drop probability and needs less response time than original Random filter. For example in case that two filters both use a hash space of 10000 bits, and set 4 bits of hash space when storing each of the 4000 keys in the key set, false drop probability and response time of 2D Random filter are 0.399294 and 12009.67 micro seconds, respectively; while those of Random filter are 0.405763 and 12199.37 micro seconds.

Keywords:

• Search filter
• differential file
• hash

C.R. Categories:

• H.3.3

^∗This research was supported by the National Science Council, Taiwan, R.O.C. under contract:NSC 79-0408-E009-01 (1989)

^†To Whom all correspondence should be sent

^∗This research was supported by the National Science Council, Taiwan, R.O.C. under contract:NSC 79-0408-E009-01 (1989)

^†To Whom all correspondence should be sent

Notes

^∗This research was supported by the National Science Council, Taiwan, R.O.C. under contract:NSC 79-0408-E009-01 (1989)

^†To Whom all correspondence should be sent