NDLI: One memory access bloom filters and their generalization

Content Provider	IEEE Xplore Digital Library
Author	Yan Qiao Tao Li Shigang Chen
Copyright Year	2011
Description	Author affiliation: Department of Computer & Information Science & Engineering, University of Florida, Gainesville, 32611, USA (Yan Qiao; Tao Li; Shigang Chen)
Abstract	The Bloom filters have been extensively applied in many network functions. Their performance is judged by three criteria: processing overhead, space overhead, and false positive ratio. Due to wide applicability, any improvement to the performance of Bloom filters can potentially have broad impact in many areas of networking research. In this paper, we propose Bloom-1, a new data structure that performs membership check in one memory access, which compares favorably with the k memory accesses of a classical Bloom filter. We also generalize Bloom-1 to Bloom-g, allowing performance tradeoff between membership query overhead and false positive ratio. We thoroughly examine the variants in this new family of filters, and show that they can be configured to outperform the Bloom filters with a smaller number of memory accesses, a smaller or equal number of hash bits, and a smaller and comparable false positive ratio in practical scenarios. We also perform experiments based on a real traffic trace to support our new filter design.
Starting Page	1745
Ending Page	1753
File Size	689900
Page Count	9
File Format	PDF
ISBN	9781424499199
ISSN	0743166X
e-ISBN	9781424499212
DOI	10.1109/INFCOM.2011.5934972
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-04-10
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Arrays Throughput Memory management Random access memory Hardware Information filters
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fast Bloom Filters and Their Generalization

An FPGA implementation of high-throughput key-value store using Bloom filter

IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards

A Comment on “Fast Bloom Filters and Their Generalization”

L-CBF: A Low-Power, Fast Counting Bloom Filter Architecture

Rethinking Flash in the Data Center

MultiLayer Compressed Counting Bloom Filters

The Variable-Increment Counting Bloom Filter

A Synergetic Use of Bloom Filters for Error Detection and Correction

One memory access bloom filters and their generalization

Similar Documents

Fast Bloom Filters and Their Generalization

An FPGA implementation of high-throughput key-value store using Bloom filter

IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards

A Comment on “Fast Bloom Filters and Their Generalization”

L-CBF: A Low-Power, Fast Counting Bloom Filter Architecture

Rethinking Flash in the Data Center

MultiLayer Compressed Counting Bloom Filters

The Variable-Increment Counting Bloom Filter

A Synergetic Use of Bloom Filters for Error Detection and Correction

One memory access bloom filters and their generalization