NDLI: A Scalable Bloom Filter for Membership Queries

Content Provider	IEEE Xplore Digital Library
Author	Kun Xie Yinghua Min Dafang Zhang Jigang Wen Gaogang Xie
Copyright Year	2007
Description	Author affiliation: Hunan Univ., Changsha (Kun Xie)
Abstract	Bloom filters allow membership queries over sets with allowable errors. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. However, the false positive errors are unavoidable, and the false positive rate increases intolerantly along with the date set expanding. To solve the scalability problem of Bloom filters, this paper presents a new design of a scalable Bloom filter (SBF) for an expanding data set. The SBF keeps a low false positive rate by adding Bloom filter vectors with double length when necessary. The paper proposes algorithms for element insertion and query operation of SBF by employing the $H_{3}$ class of universal hash functions. Theoretical and experimental results demonstrate that the new SBF provides false positive rate as low as 21.3% of the dynamic Bloom filter presented before and the querying CPU time increasing with logarithmic rather than linear. Therefore, the proposed SBF outperforms other current scalable Bloom filters significantly.
Starting Page	543
Ending Page	547
File Size	353902
Page Count	5
File Format	PDF
ISBN	9781424410422
DOI	10.1109/GLOCOM.2007.107
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-11-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Scalability Information filtering Information filters Nonlinear filters Routing Distributed databases Distributed information systems Distributed computing Data structures Dictionaries
Content Type	Text
Resource Type	Article

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

Improving distributed join efficiency with extended bloom filter operations

Basket Bloom Filters for Membership Queries

Applicability of Probablistic Data Structures for Filtering Tasks in Data Loss Prevention Systems

Scalable Semantic Overlay Routing in MANETs

Bloom filter-based XML packets filtering for millions of path queries

Quotient Filters: Approximate Membership Queries on the GPU

A variable length counting Bloom filter

False Rate Analysis of Bloom Filter Replicas in Distributed Systems

Bloom Filters: One Size Fits All?

A Scalable Bloom Filter for Membership Queries

Similar Documents

Improving distributed join efficiency with extended bloom filter operations

Basket Bloom Filters for Membership Queries

Applicability of Probablistic Data Structures for Filtering Tasks in Data Loss Prevention Systems

Scalable Semantic Overlay Routing in MANETs

Bloom filter-based XML packets filtering for millions of path queries

Quotient Filters: Approximate Membership Queries on the GPU

A variable length counting Bloom filter

False Rate Analysis of Bloom Filter Replicas in Distributed Systems

Bloom Filters: One Size Fits All?

A Scalable Bloom Filter for Membership Queries