A Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. Bloom Filters (BFs) are very attractive for their limited memory requirements and their easy construction which make them a popular choice for many tasks in network devices. However, in a number of network applications, more than simple probabilistic membership queries is required, and BFs can be adopted as a coarse filtering stage, leaving the ultimate filtering and classification process to other techniques, such as hash tables or tree-like structures. In this paper we propose a scheme to extend BFs with ``indexing'' features so that when an element $x$ is queried, an univocal index of that element is returned, which in turn can be used as an address for a table, just as a perfect hashing scheme. This extension, called indexed Bloom Filter (iBF), comes at the cost of a small increment of false positive probability and simply fits in existing BF-based applications.

Achieving perfect hashing through an improved construction of bloom filters

ANTICHI, GIANNI;GIORDANO, STEFANO;RUSSO, FRANCO;VITUCCI, FABIO
2010

Abstract

A Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. Bloom Filters (BFs) are very attractive for their limited memory requirements and their easy construction which make them a popular choice for many tasks in network devices. However, in a number of network applications, more than simple probabilistic membership queries is required, and BFs can be adopted as a coarse filtering stage, leaving the ultimate filtering and classification process to other techniques, such as hash tables or tree-like structures. In this paper we propose a scheme to extend BFs with ``indexing'' features so that when an element $x$ is queried, an univocal index of that element is returned, which in turn can be used as an address for a table, just as a perfect hashing scheme. This extension, called indexed Bloom Filter (iBF), comes at the cost of a small increment of false positive probability and simply fits in existing BF-based applications.
9781424464029
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/202807
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact