KBF: Towards Approximate and Bloom Filter based Key-Value Storage for Cloud Computing Systems

Sisi Xiong, Yanjun Yao, Shuangjiang Li, Qing Cao, Tian He, Hairong Qi, Leon Tolbert, Yilu Liu

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


As one of the most popular cloud services, data storage has attracted great attention in recent research efforts. Key-value (k-v) stores have emerged as a popular option for storing and querying billions of key-value pairs. So far, existing methods have been deterministic. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, we present an approximate k-v storage for cloud-based systems that is more compact than existing methods. The tradeoff is that it may, theoretically, return errors. Its design is based on the probabilistic data structure called 'bloom filter', where we extend the classical bloom filter to support key-value operations. We call the resulting design as the kBF (key-value bloom filter). We further develop a distributed version of the kBF (d-kBF) for the unique requirements of cloud computing platforms, where multiple servers cooperate to handle a large volume of queries in a load-balancing manner. Finally, we apply the kBF to a practical problem of implementing a state machine to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

Original languageEnglish (US)
Pages (from-to)85-98
Number of pages14
JournalIEEE Transactions on Cloud Computing
Issue number1
StatePublished - Jan 1 2017

Bibliographical note

Funding Information:
This work was supported in part by the National Science Foundation grant CNS-0953238, CNS-1017156, CNS-1117384, and CNS-1239478.

Publisher Copyright:
© 2013 IEEE.


  • Bloom filter
  • key-value storage


Dive into the research topics of 'KBF: Towards Approximate and Bloom Filter based Key-Value Storage for Cloud Computing Systems'. Together they form a unique fingerprint.

Cite this