Dynamic reordering bloom filter

Da Chung Chang, Chien Chen, Mahadevan Thanavel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

In order to check a membership in multiple sets of bloom filter in a dynamic bloom filter, a sequential search is usually used. Since the distribution of queried data is unpredictable because the distribution has a feature of temporal locality. Therefore more search cost is incurred if queried data is stored in the peer which is corresponded to the Bloom Filter has lower query priority. In this paper, we introduce Dynamic Reordering Bloom Filter that can save the cost of searching Bloom Filter by dynamically reorder the searching sequence of multiple bloom filters in a dynamic bloom filter with One Memory Access Bloom Filter (OMABF) and checked in the order saved in Query Index (QI). The performance of the system is evaluated by Markov Chain. Simulation results show that our scheme on average has 43% better in searching performance comparing with the sequential methods, which is verified via three different trace log files.

Original languageEnglish
Title of host publication19th Asia-Pacific Network Operations and Management Symposium
Subtitle of host publicationManaging a World of Things, APNOMS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages288-291
Number of pages4
ISBN (Electronic)9781538611012
DOIs
StatePublished - 1 Nov 2017
Event19th Asia-Pacific Network Operations and Management Symposium, APNOMS 2017 - Seoul, Korea, Republic of
Duration: 27 Sep 201729 Sep 2017

Publication series

Name19th Asia-Pacific Network Operations and Management Symposium: Managing a World of Things, APNOMS 2017

Conference

Conference19th Asia-Pacific Network Operations and Management Symposium, APNOMS 2017
CountryKorea, Republic of
CitySeoul
Period27/09/1729/09/17

Keywords

  • bloom filter
  • distributed system
  • dynamic bloom filter
  • one memory access bloom filter
  • temporal locality

Fingerprint Dive into the research topics of 'Dynamic reordering bloom filter'. Together they form a unique fingerprint.

Cite this