String Searching in Dispersed Files using MDS Convolutional Codes

Authors: A. S. Poornima, R. Aparna, B. B. Amberker, Prashant Koulgi

Abstract:

In this paper, we propose use of convolutional codes for file dispersal. The proposed method is comparable in complexity to the information Dispersal Algorithm proposed by M.Rabin and for particular choices of (non-binary) convolutional codes, is almost as efficient as that algorithm in terms of controlling expansion in the total storage. Further, our proposed dispersal method allows string search.

Keywords: Convolutional codes, File dispersal, Filereconstruction, Information Dispersal Algorithm, String search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335344

References:

[1] G.A.Alvarez, W.A.Burkhard and F.Cristian. Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering. In proceedings of the 24th International Symposium on Computer Architecture,pages 62-72, Denever,CO,ACM. June 1997.
[2] D.Bitton and J.Gray. Disk Shadowing. In proceedings of the 14th conference on Very Large Databases (VLDB), pages 331-338, 1988.
[3] W.A.Burkhard and J.Menon. Disk array storage system reliability. In Proceedings of the 23rd International Symposium on Fault-Tolerant Computing (FTCS-93), Pages 432-441, June 1993.
[4] W. Cary Huffman and Vera Plees Fundamentals of Error-Correcting Codes Cambridge University Press, 2003.
[5] P.M.Chen, E.K.Lee, G.A.Gibson, R.H.Kartz, and D.A.Patterson. RAID: High-Performance, reliable secondary storage. ACM Computing Surveys,26(2), June 1994.
[6] Gui-Lang Feng, Robert H. Deng, Feng Bao, JiaChen Shen, New Efficient MDS Array Codes for RAID part II: Rabin-Like codes for Tolerating Multiple (greater than or equal to 4) Disk Failures, IEEE Transactions on Computers,V.54 n.12,p.1473-1483, December 2005.
[7] R. Johannesson and K. Sh. Zigangirov , Fundamentals of Convolutional Coding, University Press (India) Limited, 2001.
[8] R. Johannesson and K. S. Zigangirov Fundamentals of Convolutional Coding IEEE Press, Newyork, 1999.
[9] M. Rabin. Effecient Dispersal of Information for Security, Load Balancing, and Fault Tolerance. Journal of the ACM, 36(2): 335-348, 1989.
[10] J. Rosenthal and R. Smarandache. Maximum Distance Separable Convolutional codes. Appl. Algebra Engrg. Comm.Comput., 10(1): 15-32,1999.