Split Counting Bloom Filter and its Application in Hbase Secondary Index
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [16]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    A new variant of Counting Bloom Filter was set up to build Hbase secondary index to support the retrieval of non-primary key data, which solved the problem that Hbase only supported the main index structure and retrieve data through the primary key and the primary key range. The new variant, Split Counting Bloom Filter(SCBF), was proposed according to the high overflow probability problem of Counting Bloom Filter(CBF) after analyzing existing CBF technology. SCBF divided standard CBF into multiple independent regions, which stored elements' fingerprint by all these areas. Comparing SCBF with CBF, the experimental result shows that, SCBF contributes to much lower overflow probability, which improves the performance of filter, and can be used to build the Hbase secondary index.

    Reference
    1 Burton HB. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7):422-426.
    2 Fan L, Cao P, Almeida J, et al. Summary cache:A scalable wide-area web cache sharing protocol. IEEE/ACM Trans. on Networking(TON), 2000, 8(3):281-293.
    3 Bonomi F, Mitzenmacher M, Panigrahy R, et al. An improved construction for counting bloom filters. Algorithms-ESA 2006 Lecture Notes in Computer Science, 2006. Zurich:Springer Berlin Heidelberg. 2006. 684-695.
    4 张震,汪斌强,陈庶樵,等.几何布鲁姆过滤器的设计与分析.电子学报,2012,40(9):1852-1857.
    5 李珺,刘晓光,王刚,等.K分组合型Bloom Filter方法的设计.计算机研究与发展,2008,45:48-52.
    6 孙智超,徐蕾.二路平衡动态布隆过滤器.数学的实践与认识,2014,44(5):199-205.
    7 侯颖,郭云飞,黄海,等.基于同源组合布鲁姆过滤器的早期流量抽样算法.通信学报,2014,35(10):117-126.
    8 Aguilar-Saborit J, Trancoso P, Muntes-Ulero V. Dynamic count filters. New York. ACM, 2006:26-32.
    9 Meng J. Partial Bloom Filter. http://blog.csdn.net/jiaomeng/article/details/1502910.[2015-04-13].
    10 魏静波,蒋平,朱劲.计数型Bloom Filter及其在机器人导航中的应用.微计算机信息,2008,24(35):241-243.
    11 王键.d-Left CBF技术在 P2P中的研究.计算机工程与设计,2008,29(7):1711-1713.
    12 严华云,关佶红.Bloom Filter研究进展.电信科学,2010, 26(2):31-35.
    13 Paulo SA, Carlos B, Nuno P, et al. Scalable bloom filters. Information Processing Letters, 2007, 101(6):255-261.
    14 Cheng X, Li HY, Wang Y, et al. BF-matrix:A secondary index for the cloud storage. In:Li FF, Li GL, eds. Web-Age Information Management:Lecture Notes in Computer Science. Macau:Springer International Publishing, 2014:384-396.
    15 严华云,关佶红.基于Bloom滤波器的对等网多关键字检索.计算机应用,2010,30(9):2335-2443.
    16 张华,郑世珏,童德茂.Bloom Filter技术及应用.阜阳师范学院学报(自然科学版),2014,31(3):62-66.
    Cited by
Get Citation

黄璨,方旭昇,张朝泉.分片计数布隆过滤器及其在Hbase二级索引的应用.计算机系统应用,2016,25(3):119-123

Copy
Share
Article Metrics
  • Abstract:1702
  • PDF: 3051
  • HTML: 0
  • Cited by: 0
History
  • Received:June 24,2015
  • Revised:September 06,2015
  • Online: March 17,2016
Article QR Code
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063