Abstract:
Bloom filtering is an important technique for space efficient
storage of a conservative approximation of a set 
. The set stored may have
up to some specified number of ``false positive'' members, but all elements
of are included. In this paper we consider lossy dictionaries
that are also allowed to have ``false negatives'', i.e., leave out elements
of . The aim is to maximize the weight of included keys within a given
space constraint. This relaxation allows a very fast and simple data
structure making almost optimal use of memory. Being more time efficient than
Bloom filters, we believe our data structure to be well suited for replacing
Bloom filters in some applications. Also, the fact that our data structure
supports information associated to keys paves the way for new uses, as
illustrated by an application in lossy image compression
. The set stored may have
up to some specified number of ``false positive'' members, but all elements
of are included. In this paper we consider lossy dictionaries
that are also allowed to have ``false negatives'', i.e., leave out elements
of . The aim is to maximize the weight of included keys within a given
space constraint. This relaxation allows a very fast and simple data
structure making almost optimal use of memory. Being more time efficient than
Bloom filters, we believe our data structure to be well suited for replacing
Bloom filters in some applications. Also, the fact that our data structure
supports information associated to keys paves the way for new uses, as
illustrated by an application in lossy image compressionAvailable as PostScript, PDF.