A multi-attribute data structure with parallel Bloom filters for network services

Yu Hua, Bin Xiao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

A Bloom filter has been widely utilized to represent a set of items because it is a simple space-efficient randomized data structure. In this paper, we propose a new structure to support the representation of items with multiple attributes based on Bloom filters. The structure is composed of Parallel Bloom Filters (PBF) and a hash table to support the accurate and efficient representation and query of items. The PBF is a counter-based matrix and consists of multiple submatrixes. Each submatrix can store one attribute of an item. The hash table as an auxiliary structure captures a verification value of an item, which can reflect the inherent dependency of all attributes for the item. Because the correct query of an item with multiple attributes becomes complicated, we use a two-step verification process to ensure the presence of a particular item to reduce false positive probability.
Original languageEnglish
Title of host publicationHigh Performance Computing - HiPC 2006 - 13th International Conference Proceedings
Pages277-288
Number of pages12
DOIs
Publication statusPublished - 1 Dec 2006
Event13th International Conference on High Performance Computing, HiPC 2006 - Bangalore, India
Duration: 18 Dec 200621 Dec 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4297 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on High Performance Computing, HiPC 2006
CountryIndia
CityBangalore
Period18/12/0621/12/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this