Abstract

Today's storage systems have a major issue for the long-term storage of massive amounts of unstructured data. The reliability and availability of that fortune of data become important factors. So, distributed storage system is essential for many large-scale organizations. It is challenging that how to access the distributed data from a place. In this paper, a structure of the Bloom filter array (BFA) is proposed to get time and space efficiency in distributed storage system. The proposed structure that can efficiently lookup the queries will be discussed from the algorithm perspective and then evaluate BFA through simulations.

References

• A. Broder, M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics, 2002, pp. 636-646.
• B. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol. 13, 1970.
• F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, Beyond Bloom ?lters: From approximate membership checks to approximate state machines, SIGCOMM, 2006.
• F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, "An Improved Construction for Counting Bloom Filters," in 14th Annual European Symposium on Algorithms, LNCS 4168, 2006, pp. 684–695.
• S. Czerwinski, B. Y. Zhao, T. Hodes, A. D. Joseph, and R. Katz, An Architecture for a Secure Service Discovery Service, In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99), pp. 24—35. New York: ACM Press, 1999.
• D. Guo, J. Wu, H. Chen, and X. Luo, Theory and network application of dynamic Bloom ?lters, INFOCOM, 2006.
• A. Kumar, J. Xu, and E. W. Zegura, Ef?cient and scalable query routing for unstructured peer-to-peer networks, INFOCOM, 2005.
• J. Kubiatowicz, D. Bindel, P. Eaton, Y. Chen, D. Geels, R. Gummadi, S. Rhea, W. Weimer, C. Wells, H. Weatherspoon, and B. Zhao, OceanStore: An Architecture for Global-Scale Persistent Storage, ACM SIGPLAN Notices 35:11 (2000), 190—201.
• P. Maymounkov and D. M. Kademlia, A Peer-to-peer Information Systems Based on the XOR Metric, In Proceedings of the IPTPS 2002, Boston, March 2002.
• M. Mitzenmacher, Compressed Bloom ?lters, IEEE/ACM Trans. on Networking, vol. 10, no. 5, pp. 604–612, 2002.
• S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, A Scalable Content Addressable Network, In Proceedings of the ACM SIGCOMM 2001 Technical Conference, San Diego, CA, USA, August 2001.
• A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329-350, November 2001.
• S. C. Rhea and J. Kubiatowicz, Probabilistic Location and Routing, In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Volume 3, pp. 1248—1257. Los Alamitos, CA: IEEE Computer Society, 2002.
• I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, In Proceedings of the ACM SIGCOMM 2001, San Diego, CA, USA, August 2001.
• K. Sato, N. Matsumoto and N. Yoshida, Multi Keyword Search for DHT P2P Networks, IPSJ/IEICE Forum on Information Technology (FIT)2006, (2006).
• F. Sato, Evaluation of the Structured Bloom Filter, In Proceedings of CISIS '10 of the 2010 International Conference on Complex Intelligent and Software Intensive Systems, pp. 313-320.
• C. Saar and M. Yossi, Spectral Bloom ?lters, SIGMOD, 2003.
• H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood, Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing, Proc. ACM SIGCOMM, 2005.
• Y. Zhang, D. Li, L. Chen, and X. Lu, Collaborative Search in Large-scale Unstructured Peer-to-Peer Networks, ICPP, 2007.