ALCOMFT-TR-01-126

Rasmus Pagh and Flemming Friche Rodler
Lossy Dictionaries
Århus. Work package 4. May 2001.

Abstract: Bloom filtering is an important technique for space efficient storage of a conservative approximation of a set S. The set stored may have up to some specified number of ``false positive'' members, but all elements of S are included. In this paper we consider ``lossy dictionaries'' that are allowed to also have false negatives. 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 applications, as illustrated by an application in lossy image compression.

Postscript file: ALCOMFT-TR-01-126.ps.gz (115 kb).