Back to Search
Start Over
Coding for locality in reconstructing permutations.
- Source :
- Designs, Codes & Cryptography; Feb2018, Vol. 86 Issue 2, p387-418, 32p
- Publication Year :
- 2018
-
Abstract
- 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 <italic>locality</italic>, 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 <italic>query complexity</italic> 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- CODING theory
PERMUTATIONS
DATA encryption
DATA compression
COMBINATORICS
Subjects
Details
- Language :
- English
- ISSN :
- 09251022
- Volume :
- 86
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Designs, Codes & Cryptography
- Publication Type :
- Academic Journal
- Accession number :
- 127735623
- Full Text :
- https://doi.org/10.1007/s10623-017-0378-9