Using parallel bloom filters for multiattribute representation on network services

Bin Xiao, Yu Hua

Research output: Journal article publicationJournal articleAcademic researchpeer-review

43 Citations (Scopus)

Abstract

One widely used mechanism for representing membership of a set of items is the simple space-efficient randomized data structure known as Bloom filters. Yet, Bloom filters are not entirely suitable for many new network applications that support network services like the representation and querying of items that have multiple attributes as opposed to a single attribute. In this paper, we present an approach to the accurate and efficient representation and querying of multiattribute items using Bloom filters. The approach proposes three variant structures of Bloom filters: Parallel Bloom Filter (referred as PBF) structure, PBF with a hash table (PBF-HT), and PBF with a Bloom filter (PBF-BF). PBF stores multiple attributes of an item in parallel Bloom filters. The auxiliary HT and BF provide functions to capture the inherent dependency of all attributes of an item. Compared to standard Bloom filters to represent items with multiple attributes, the proposed PBF facilitates much faster query service and both PBF-HT and PBF-BF structures achieve much lower false positive probability with a result to save storage space. Simulation and experimental results demonstrate that the new space-efficient Bloom filter structures can efficiently and accurately represent multiattribute items and quickly respond queries at the cost of a relatively small false positive probability.
Original languageEnglish
Article number4798158
Pages (from-to)20-32
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Jan 2010

Keywords

  • Data structure
  • False positives
  • Network services
  • Parallel Bloom filters

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this