MA Wenming, ZHANG Yujie, MENG Xiangwu. Optimizing Bloom Filter Settings for Multi-keyword Search in Kademlia-like DHT Peer-to-Peer Networks[J]. Chinese Journal of Electronics, 2014, 23(2): 388-393.
Citation: MA Wenming, ZHANG Yujie, MENG Xiangwu. Optimizing Bloom Filter Settings for Multi-keyword Search in Kademlia-like DHT Peer-to-Peer Networks[J]. Chinese Journal of Electronics, 2014, 23(2): 388-393.

Optimizing Bloom Filter Settings for Multi-keyword Search in Kademlia-like DHT Peer-to-Peer Networks

Funds:  This work is supported by the Natural Science Foundation of China (No.60872051).
  • Received Date: 2012-12-01
  • Rev Recd Date: 2013-05-01
  • Publish Date: 2014-04-05
  • This paper has proposed a novel method to reduce the multi-keyword query traffic in Kademlia-like Peer-to-peer (P2P) networks by optimizing the Bloom filter settings. We build some models to estimate the communication cost, the union set size, and the loss rate of performing union and intersection operations. We implement a Kademlia-like system and generate a group of datasets. We use one part of the datasets to obtain the functions how to compute the optimal parameters and use another part of datasets to verify our method. Each query can determine the optimal settings of Bloom filter with no extra configuration. Our simulation experimental results show that with optimal Bloom filters settings, we can greatly reduce the communication cost under an acceptable loss rate.
  • loading
  • D. Tsoumakos, N. Roussopoulos, "Adaptive probabilistic search for peer-to-peer networks", Proc. of 3rd International Conference on Peer-to-Peer Computing, Linkoping, Sweden, pp.102-109, 2003.
    Q.B. Zheng, X.C. Lu, P.D. Zhu, et al., "An efficient random walks based approach to reducing file locating delay in unstructured P2P network", IEEE Global Telecommunications Conference, St. Louis. MO, USA, pp.980-984, 2005.
    I. Filali, F. Huet, "Dynamic TTL-based search in unstructured peer-to-peer networks", 10th IEEE/ACM International Conference on Cluster, Cloud, and Grid Computing, Melbourne, VIC, Australia, pp.438-447, 2010.
    M. Xu, S.G. Zhou, J.H. Guang, et al., "A path-traceable query routing mechanism for search in unstructured peer-topeer networks", Journal of Network and Computer Applications, Vol.33, No.2, pp.115-127, 2010.
    Y.X. Zhao, C.J. Chen, B.X. Zhang, "Modeling multi-point transport protocol in P2P networks", Chinese Journal of Electronics, Vol.20, No.4, pp.641-645, 2011.
    X.T. Liu, K. Cai, Q. Yue, et al., "A versatile crawler for Kademlia-based networks and its convergence analysis ", Chinese Journal of Electronics, Vol.22, No.1, pp.7-14, 2013.
    Y.S. Huang, X.W. Meng, Y.J. Zhang, "Strategy of content location of P2P based on the social network", Journal of Software, Vol.21, No.10, pp.2622-2630, 2010. (in Chinese)
    W.M. Ma, X.W. Meng, Y.J. Zhang, "Bidirectional random walk search mechanism for unstructured P2P network", Journal of Software, Vol.23, No.4, pp.894-911, 2012. (in Chinese)
    S. Ratnasamy, P. Francis, M. Handley, et al., "A scalable content addressable network", Computer Communication Review, Vol.31, No.4, pp.161-172, 2001.
    I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, et al., "Chord: A scalable peer-to-peer lookup protocol for internet applications", IEEE/ACM Transactions on Networking, Vol.11, No.1, pp.17-32, 2003.
    B.Y. Zhao, L. Huang, J. Stribling, et al., "Tapestry: A resilient global-scale overlay for service deployment", IEEE Journal on Selected Areas in Communications, Vol.22, No.1, pp.41-53, 2004.
    A. Rowstron, P. Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems", IFIP/ACM International Conference on Distributed Systems Platforms, Heidelberg, Germany, pp.329-350, 2001.
    P. Maymounkov, D. Mazieres, "Kademlia: A peer-to-peer information system based on the XOR metric", Proc. of 1st International Workshop on Peer-to-Peer Systems, Cambridge, MA, USA, pp.53-65, 2002.
    S. Robertson, "Understanding inverse document frequency: On theoretical arguments for Idf", Journal of Documentation, Vol.60, No.5, pp.503-520, 2004.
    I. Podnar, M. Rajman, T. Luu, et al., "Scalable peer-to-peer web retrieval with highly discriminative keys", Proc. of 23rd International Conference on Data Engineering, Istanbul, Turkey, pp.1096-1105, 2007.
    G. Skobeltsyn, T. Luu, I.P. Zarko, et al., "Web text retrieval with a P2P query-driven index", Proc. of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Amsterdam, Netherlands, pp.679-686, 2007.
    H.H. Chen, L. Chen, Y.H. Liu, et al., "Optimizing bloom filter settings in Peer-to-Peer multikeyword searching", IEEE Transcations on Knowledge and Data Engineering, Vol. 24, No.4, pp.692-706, 2012.
    A. Broder, M. Mitzenmacher, "Network applications of bloom filters: A Survey", Internet Mathematics, Vol. 1, No.4, pp.485-509, 2004.
    A. Montersor, M. Jelasity, "PeerSim: A scalable P2P simulator", IEEE P2P'09 -9th International Conference on Peer-to-Peer Computing, Seattle, WA, USA, pp.99-100, 2009.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (345) PDF downloads(1324) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint