Abstract
For the big data, the fingerprints of the data chunks are very huge and cannot be stored in the memory completely. Accordingly, a new query mechanism namely Two-stage Bloom Filter mechanism is proposed. First, each bit of the second grade bloom filter represents the chunks having the identical fingerprints which reducing the rate of false positives. Second, a two-dimensional list is created corresponding to the two grade bloom filter to gather the absolute addresses of the data chunks with the identical fingerprints. Finally, we suggest a new hash function class with the strong global random characteristic. Two-stage Bloom Filter decreases the number of accessing disks, improves the speed of detecting the redundant data chunks, and reduces the rate of false positive. Our experiments indicate that Two-stage Bloom Filter reduces about 30~40% storage accessing of false positive with the same length of the first grade Bloom Filter.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
The International Data Corporation website, http://www.idc.com
Zhu, B., Li, K., Patterson, H.: Avoiding the Disk Bottleneck in the Data Domain Deduplication File System. In: Proceedings of 6th USENIX Conference on File and Storage Technologies, pp. 1–14. USENIX Association, San Jose (2008)
Bobbarjung, D.R., Jaqannathan, S., Dubnicki, C.: Improving Duplicate Elimination in Storage Systems. ACM Transactions on Storage 2, 424–448 (2006)
Lillibridge, M.: Sparse Indexing, Large Scale, Inline Deduplication Using Sampling and Locality. In: Proceedings of 7th USENIX Conference on File and Storage Technologies, pp. 111–123. USENIX Association, San Francisco (2009)
Thewl, T.T., Thein, N.L.: An Efficient Indexing Mechanism for Data Deduplication. In: Proceedings of 2009 International Conference on the Current Trends in Information Technology, pp. 1–5. IEEE Press, Dubai (2009)
Bhagwat, D., Eshghi, K., Long, D.D.E., Lillibridge, M.: Extreme Binning: Scalable, Parallel Deduplication for Chunk-based File Backup. In: Proceedings of 17th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 1–9. IEEE Press, London (2009)
Kruus, E., Ungureanu, C., Dubnicki, C.: Bimodal Content Defined Chunking for Backup Streams. In: Proceedings of 8th USENIX Conference on File and Storage Technologies, pp. 239–252. USENIX Association, Berkeley (2010)
Lu, G.L., Jin, Y., Du, D.H.C.: Frequency Based Chunking for Data De-Duplication. In: Proceedings of 18th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 287–296. IEEE Press, Miami (2010)
Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: A Distributed Storage System for Structured Data. In: Proceedings of 7th USENIX Symposium on Operating Systems Design and Implementation, pp. 205–218. USENIX Association, Berkeley (2006)
Jain, N., Dahlin, M., Tewari, R.: TAPER: Tiered Approach for Eliminating Redundancy in Replica Synchronization. In: Proceedings of 4th USENIX Conference on File And Storage Technologies, pp. 281–294. USENIX Association, Berkeley (2005)
Bhattacherjee, S., Naranq, A., Garq, V.K.: High Throughput Data Redundancy Removal Algorithm with Scalable Performance. In: Proceedings of 6th International Conference on High Performance and Embedded Architectures and Compilers, pp. 87–96. ACM, New York (2011)
Debnath, B., Sengupta, S., Li, J., Lilja, D.J., Du, D.: BloomFlash: Bloom Filter on Flash-Based Storage. In: Proceedings of 31th International Conference on Distributed Computing Systems, pp. 635–644. IEEE Computer Society, Washington (2011)
Bender, M.A., Farach-Colton, M., Johnson, R., Kuszmaul, B.C., Medjedovic, D., Montes, P., Shetty, P., Spillane, R.P., Zadok, E.: Don’t Thrash: How to Cache Your Hash on Flash. In: Proceedings of 3rd USENIX Conference on Hot Topics in Storage and File Systems, p. 1. USENIX Association, Berkeley (2011)
Guo, D., Wu, J., Chen, H.H., Yuan, Y., Luo, X.S.: The Dynamic Bloom Filters. IEEE Transactions on Knowledge and Data Engineering 22, 120–133 (2010)
Song, H.Y., Dharmapurikar, S., Turner, J., Lockwood, J.: Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing. In: Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 181–192. ACM, New York (2005)
Guo, D., Chen, H.H., Luo, X.S.: Theory and Network Application of Dynamic Bloom Filters. In: Proceedings of 25th Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1–12. IEEE Press, Spain (2006)
Ahmadi, M., Wong, S.: Modified Collision Packet Classification Using Counting Bloom Filter in Tuple Space. In: Proceedings of 25th IASTED International Conference on Parallel and Distributed Computing and Networks, pp. 70–76. ACTA Press, Anaheim (2007)
Ahmadi, M., Wong, S.: A Memory-optimized Bloom Filter Using an Additional Hashing Function. In: Proceedings of Global Telecommunications Conference, pp. 1–5. IEEE Press, New Orleans (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, B., Jin, H., Xie, X., Yuan, P. (2012). TBF: A High-Efficient Query Mechanism in De-duplication Backup System. In: Li, R., Cao, J., Bourgeois, J. (eds) Advances in Grid and Pervasive Computing. GPC 2012. Lecture Notes in Computer Science, vol 7296. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30767-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-30767-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30766-9
Online ISBN: 978-3-642-30767-6
eBook Packages: Computer ScienceComputer Science (R0)