×

Coding for locality in reconstructing permutations. (English) Zbl 1386.68050

Summary: The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. Both approaches must present low query complexity to allow the user to find an element efficiently. We discuss both approaches, and give a particular focus to the combinatorial one. In the combinatorial approach, we provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using a variety of tools, such as Reed-Solomon codes, permutation polynomials, and multi-permutations. In addition, several low-rate constructions of particular interest are discussed. In the coding approach we discuss an alternative representation of permutations, present a paradigm for supporting arbitrary powers of the stored permutation, and conclude with a proof of concept that permutations may be stored more efficiently than ordinary strings over the same alphabet.

MSC:

68P20 Information storage and retrieval of data
05A05 Permutations, words, matrices
68M14 Distributed systems
68R05 Combinatorics in computer science
94B05 Linear codes (general theory)

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon N., Spencer J.H.: The Probabilistic Method. Wiley, New York (2004). · Zbl 1333.05001
[2] Barg A., Mazumdar A.: Codes in permutations and error correction for rank modulation. IEEE Trans. Inf. Theory 56(7), 3158-3165 (2010). · Zbl 1366.94657 · doi:10.1109/TIT.2010.2048455
[3] Bellare M., Goldreich O., Goldwasser S.: Incremental Cryptography: The Case of Hashing and Signing. Advances in Cryptology (CRYPTO), pp. 216-233. Springer, Berlin (1994). · Zbl 0939.94530
[4] Bellare M., Goldreich O., Goldwasser S.: Incremental cryptography and application to virus protection. In: ACM 27th Annual Symposium on Theory of Computing (STOC), pp. 45-56 (1995). · Zbl 0916.94005
[5] Beyer I., Smith T.F., Stein M.L., Ulam S.M.: Metrics in biology, an introduction. Los Alamos Scientific Laboratory Report, LA-4973 (1972). · Zbl 1163.65022
[6] Blake I.F., Cohen G., Deza M.: Coding with permutations. Inf. Control 43(1), 1-19 (1979). · Zbl 0415.94010 · doi:10.1016/S0019-9958(79)90076-7
[7] Bóna M.: Combinatorics of Permutations. CRC Press, Boca Raton (2012). · Zbl 1255.05001 · doi:10.1201/b12210
[8] Buzaglo S., Yaakobi E.: On the capacity of constrained permutation codes for rank modulation. IEEE Trans. Inf. Theory 62(4), 1649-1666 (2016). · Zbl 1359.94229 · doi:10.1109/TIT.2016.2519400
[9] Chu W., Colbourn C.J., Dukes P.: Constructions for permutation codes in powerline communications. Des. Codes Cryptogr. 32(1-3), 51-64 (2004). · Zbl 1065.94003 · doi:10.1023/B:DESI.0000029212.52214.71
[10] Cooper C.: A lower bound for the number of good permutations. In Data Recording, Storage and Processing (The National Academy of Sciences of Ukraine), vol. 213, pp. 15-25 (2000). · Zbl 1359.94890
[11] Deza M., Huang T.: Metrics on permutations, a survey. J. Comb. Inf. Syst. Sci. (1998). · Zbl 1217.05038
[12] Dummit D.S., Foote R.M.: Abstract Algebra. Prentice Hall, Englewood Cliffs, NJ (1991). · Zbl 0751.00001
[13] Eberhard S., Manners F., Mrazović R.: Additive triples of bijections, or the toroidal semiqueens problem. arXiv:1510.05987 (2015). · Zbl 1405.05013
[14] Farnoud F., Skachek V., Milenkovic O.: Error-correction in flash memories via codes in the Ulam metric. IEEE Trans. Inf. Theory 59(5), 3003-3020 (2013). · Zbl 1364.94711 · doi:10.1109/TIT.2013.2239700
[15] Gabrys R., Yaakobi E., Farnoud F., Sala F., Bruck J., Dolecek L.: Codes correcting erasures and deletions for rank modulation. IEEE Trans. Inf. Theory 62(1), 136-150 (2016). · Zbl 1359.94890 · doi:10.1109/TIT.2015.2493147
[16] Jiang A., Mateescu R., Schwartz M., Bruck J.: Rank modulation for flash memories. IEEE Trans. Inf. Theory 55(6), 2659-2673 (2009). · Zbl 1367.94121 · doi:10.1109/TIT.2009.2018336
[17] Konstantinova E., Levenshtein V., Siemons J.: Reconstruction of permutations distorted by single transposition errors. arXiv:math/0702191 (2007). · Zbl 1163.65022
[18] McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42(44), 114-116 (1978).
[19] McKay B.D., McLeod J.C., Wanless I.M.: The number of transversals in a Latin square. Des. Codes Cryptogr. 40(3), 269-284 (2006). · Zbl 1200.05039 · doi:10.1007/s10623-006-0012-8
[20] Munro J.I., Raman R., Raman V., Rao S.: Succinct representations of permutations and functions. Theor. Comput. Sci. 438, 74-88 (2012). · Zbl 1245.68075 · doi:10.1016/j.tcs.2012.03.005
[21] Patrascu M.: Succincter. In: 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 305-313 (2008). · Zbl 0415.94010
[22] Prakash N., Kamath G.M., Lalitha V., Kumar P.V.: Optimal linear codes with a local-error-correction property. In: IEEE International Symposium on Information Theory (ISIT), pp. 2776-2780 (2012).
[23] Raviv N., Yaakobi E., Médard M.: Coding for locality in reconstructing permutations. In: IEEE International Symposium on Information Theory (ISIT), pp. 450-454 (2016). · Zbl 1386.68050
[24] Rouayheb, S.E., Goparaju, S.E., Kiah, H.M., Milenkovic, O.: Synchronizing edits in distributed storage networks. arXiv:1409.1551 (2014). · Zbl 0415.94010
[25] Schwartz M.: Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices. Linear Algebra Appl. 430(4), 1364-1374 (2009). · Zbl 1163.65022 · doi:10.1016/j.laa.2008.10.029
[26] Tamo I., Barg A.: A family of optimal locally recoverable codes. IEEE Trans. Inf. Theory 60(8), 4661-4676 (2014). · Zbl 1360.94385 · doi:10.1109/TIT.2014.2321280
[27] Tamo I., Schwartz M.: Correcting limited-magnitude errors in the rank-modulation scheme. IEEE Trans. Inf. Theory 56(6), 2551-2560 (2010). · Zbl 1366.94672 · doi:10.1109/TIT.2010.2046241
[28] Tamo I., Wang Z., Bruck J.: Long MDS codes for optimal repair bandwidth. In: IEEE International Symposium on Information Theory (ISIT), pp. 1182-1186 (2012). · Zbl 0424.68029
[29] Wu A., Rosenfeld A.: Cellular graph automata. I. Basic concepts, graph property measurement, closure properties. Inf. Control 42(3), 305-329 (1979). · Zbl 0424.68029 · doi:10.1016/S0019-9958(79)90288-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.