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.
Titolo: | Achieving perfect hashing through an improved construction of bloom filters |
Autori interni: | |
Anno del prodotto: | 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. |
Handle: | http://hdl.handle.net/11568/202807 |
ISBN: | 9781424464029 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |