String Searching in Dispersed Files using MDS Convolutional Codes

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.

Authors:

• A. S. Poornima
• R. Aparna
• B. B. Amberker
• Prashant Koulgi

Keywords:

• Convolutional codes
• File dispersal
• Filereconstruction
• Information Dispersal Algorithm
• String search.

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.