# Image compression overview

(M. Prantl††thanks<EMAIL_ADDRESS>
Compression plays a significant role in a data storage and a transmission. If
we speak about a generall data compression, it has to be a lossless one. It
means, we are able to recover the original data 1:1 from the compressed file.
Multimedia data (images, video, sound…), are a special case. In this area, we
can use something called a lossy compression. Our main goal is not to recover
data 1:1, but only keep them visually similar. This article is about an image
compression, so we will be interested only in image compression. For a human
eye, it is not a huge difference, if we recover RGB color with values
[150,140,138] instead of original [151,140,137]. The magnitude of a difference
determines the loss rate of the compression. The bigger difference usually
means a smaller file, but also worse image quality and noticable differences
from the original image.

We want to cover compression techniques mainly from the last decade. Many of
them are variations of existing ones, only some of them uses new principes.

##  1 Introduction

Someone may ask the important question “Why compress data at all”. Well, lets
dive into some facts. Single image at 1920x1080 resolution (with RGB colors)
gives us the uncompressed (raw) size of 6075KB for a single image. Many of the
digital cameras takes even larger pictures. To keep them uncompressed would be
a waste of space and also energy (a bigger storage space consumes more
electricity and produce more heat, that needs to be cooled down with another
energy etc.).

The lossless compression is suitable for images, that will be later edited or
need to keep fine details. Sometimes, we can accept a small change in a
compressed data. Those methods are called near-lossless and are often used in
medical images. The largest group is covered by a lossy compression.

The quality of the compression can be expressed by the compression ratio. For
lossless methods, we can get the average of 3-4 times smaller files than the
original ones. With lossy methods, we can obtain ratios up to 50:1 while
maintain good perceptual quality of a reconstructed data. Rating factor of
compression is not only in its efficiency in term of compression ratio. Very
significant is also a compression time complexity. Many compression algorithms
are asymmetric, which means that compression takes more time than
decompression. That is usually not problem for images, since we compress file
only once, but decompress it repeatedly. This could cause some problems in
real time applications.

There are many different approaches for compression of different data types.
Its not possible to cover all of them. In this paper we are going to focus on
compressions of common images. We are not considerating special methods based
on the prior knowledge of data types, such as medical images, satellite
images, GIS. We decided to take wider range of approaches and each of them
support with small example of existing algorithms. Our main interest is in the
last ten years of research. Both, lossless and lossy methods are discussed.

##  2 Lossless methods

Lossless methods are very general. In theory, we can use any lossless
compression algorithm and apply it to images. In practice, that is not usually
the best idea. There are several approaches, that are designed to be more
efficient with images. Compressions can be divided into several categories,
based on algorithm main idea. There are three main directions – dictionary,
prediction and wavelet based methods.

###  2.1 Dictionary based

Those algorithm are based on a dictionary methods. Most of them are variations
of LZ-family algorithms (LZ77, LZ78, LZSS, LZW…) [36]. Main idea comes from
LZ77 [48] algorithm. Superior version further improved compression ratio.

LZ77 is working with two parts of data at the same time – actual window and
sliding window. We are searching for match from actual window in sliding
window. If match is found, reference to the sliding window is stored. This
first version is not optimal, because it has fixed structure of coded word
[position, length, next character].

  * Compression

example

  * Abracadabra

= [0,0,a][0,0,b][0,0,r][3,1,c][2,1,a][7,3,a]

There are two typical, well known, formats, where we can find that type of
compression. Those are PNG [9] and GIF. While GIF is using LZW (patented), PNG
uses open-source variant of original version of LZ77 algorithm.

Recently, LZW method in a combination with BCH codes (error correcting codes)
for removal of repeating parts after the compression was proposed by [2].

###  2.2 Prediction based

Prediction methods use prediction of a next value based on a special
predictor. There can be different versions of them. Those predictors are
designed to be efficient with image data. Algorithm has two major steps:

  1. 1.

Prediction of a next value from previous ones. The predicted values are very
close to the original ones

  2. 2.

Calculate an error of a prediction as a difference of the original and the
predicted value. Only resulting error is coded, mostly by entropy coding.

There are many types of predictors.

####  2.2.1 Gradient Adaptive Predictor (GAP)

Firstly used in CALIC [46]. Its adaptive and non-linear. Due to its adaptivity
its better than classic linear predictors. This improvement can be best seen
along strong edges. Basic equation is simple and can recognize six types of
edge - sharp, classic and weak in vertical or horizontal direction. Full
equation to compute predicted value can be found in [46].

####  2.2.2 Adaptive Linear Prediction and Classification (ALPC)

Another adaptive and non-linear predictor was proposed by _[23]_. It uses
weighted pixel values. Weights can be updated during compression process to
improve prediction accuracy. This predictor is not based on a single equation,
but it uses a simple algorithm to generate weights for the neighbouring
pixels. The pseudo-code of the algorithm is clearly explained in [23].

####  2.2.3 Median Edge Detection predictor (MED)

Successor of GAP. Firstly used as a part of LOCO-I algorithm [43] known from
JPEG-LS. The prediction scheme is presented in an equation 1.

$\left[\begin{array}[]{cc}C&B\\\ A&x\end{array}\right]$

$x_{i+1}=\left\\{\begin{array}[]{c}min(A,B)\;\;if\>c\geq max(A,B)\\\
max(A,B)\;\;if\>c\leq min(A,B)\\\ A+B-C\;\;otherwise\end{array}\right.$ (1)

This predictor was further improved. Predicted errors are decorrelated in
their bit-planes using XOR operator and further reduced with logical
minimization using Quine-McCluskey algorithm. This approach is described in
[34].

####  2.2.4 Neural Network predictor

Fixed formula based on previous values in not used as a predictor. Feed
forward neural network is used instead. Inputs are based on previous pixels
values and the output is a predicted value. In the learning phase, the output
is set to the correct value. The neural network is trained using back-
propagation algorithm. This method was proposed by [3]. Similar method with
neural predictor was proposed by [28]. This scheme is using larger area than
[3], from which predicted value is calculated.

####  2.2.5 Gradient Edge Detection predictor (GED)

Combination of MED and GAP predictor was proposed by [5]. Their prediction
template uses five neighbouring pixels, as shown on image X.

Prediction scheme is simple and very similar to MED as we can see from
equation 2.

$\left[\begin{array}[]{ccc}.&.&E\\\ .&C&B\\\ D&A&x\end{array}\right]$

$g_{v}=|C-A|+|E-B|$

$g_{h}=|D-A|+|C-B|$

$x_{i+1}=\left\\{\begin{array}[]{c}A\;\;if\>(g_{v}-g_{h})>T\\\
B\;\;if\>(g_{v}-g_{h})<-T\\\
\frac{3(A+B)}{8}+\frac{C+D+E}{12}\end{array}\right.$ (2)

###  2.3 Wavelet based

First a discrete wavelet transform (DWT) is applied. This results in a wavelet
coefficients. There is no compression at that moment, because the count of
coefficients is the same as of image pixels. However, values are more
compressible, because they are concentrated in just few different
coefficients. Those coefficients are further coded using ordering scheme and
entropy coding.

Two main ordering algorithms are commonly used – Embedded Zerotrees of Wavelet
(EZW) [40] and Set partitioning in hierarchical trees (SPIHT) [35]. EZW and
SPIHT are both progressive algorithm and uses quad-tree scheme with a
predefined scan order of coefficients, where the most important coefficients
are encoded as first. SPIHT can be seen as an improved version of EZW.

Main disadvantage of DWT is its speed. Compression and decompression takes
usually more time than prediction and dictionary based methods, but
compression ratio results are often comparable. Well known format based on DWT
is JPEG2000 [29]. In [6] better compression of DWT coefficients via improved
SPIHT is proposed. Latest research proposed by [18] further improved
compression ratio. There is also a binary version of this transform. Its
faster than full DWT and used primary for binary images. [27] extend binary
transform for grayscaled images.

###  2.4 Other

Apart from a classic and commonly used algorithms, there can be found other
solutions. Many compressions can be improved by histogram update in
preprocessing step. This improvement was discussed in article [13]. Method
using binary trees and a prediction is described in [17]. Compression based on
a bit-planes and context modelling is discussed in [16].

In 2011 [22] proposed method based on contour compression. They are traversing
along contours with the same pixel brightness value and store resulting
contours using the run length encoding (RLE) algorithm and an entropy coding.

##  3 Near-Lossless methods

Special category between lossless and lossy methods are near-lossless ones.
They allow a small loss of quality, which is almost non-observable. Their PSNR
(see section 5 for details) is usually very high (50+). For example, if two
neighbouring pixels have values 159, 160, decompressed values can be 160, 160.
Algorithms often proceed from lossless versions, with some modifications.

Very suitable are prediction-based methods, where prediction can include some
kind of quality loss. The typical example is MED predictor and LOCO-I
algorithm [43]. At the end, every predictor mentioned in a previous chapter
can be updated to support near-lossless compression.

A different method for near-lossless mode only based on the prediction was
proposed by _[25]_. Their algorithm uses prediction and graph of predicted
errors (referred as trellis). For each row of an image, a graph is
constructed. Its edges are labelled with the prediction error. The graph is
later processed to found edges that has the same or similar error value. For
those values, run length encoding (RLE) is used.

Another approach is described in [21]. First, pixels are divided by 2P (P is
number of bits of loss) and rounded. Pixels are rearranged using different
scan orders (Zig-Zag, Snake, Hilbert…). Only differences between consecutive
values are stored and compressed with the Huffman coding. Best scan order is
selected with brute-force, simple by trying all combinations and choose the
best one.

Attempt to used dictionary based method (LZW) was proposed by _[7]_. LZW has
been modified. Entries in dictionary are searched with error threshold. There
can be more than one result. Selected entry is the one with minimal error. In
decompression, different data are obtained, but their error is lower than
threshold value. Article also contains comparison with quadtree based near-
lossless method. Quadtree recursive division stop condition has been changed.
If block error is within selected boundaries, no further division occurs and
block is represented by its mean value.

##  4 Lossy methods

The lossy methods are of great importance in an image compression. Human eyes
can be tricked and loss of details does not much affect the overall
perception. If we are talking about lossy compressions, there is always a rate
of loss. We can compress the whole image by only using one dominant color, but
what the result will be? Important is to find a good trade off between the
quality and overall image size. Most of the methods are transform based. Image
is transformed to discrete spectrum and coefficients are quantized and
truncated. Resulted data are losslessly compressed. Pipelined process can be
seen on Figure 1.

Figure 1: Lossy compression / decompression pipeline

The typical representatives of these methods are discrete cosine transform
(DCT), generalized Karhunen-Loewe transform (KLT) and wavelet based transform
(DWT). Those are basically state-of-the art approaches.

###  4.1 Transform based methods

####  4.1.1 DCT

The most well-known methods are based on the discrete cosine transform (DCT).
It was first presented in [42]. Basic version of the algorithm is very fast
and simple. Image is divided to blocks of size MxM. Each block is transformed
with DCT. Resulting coefficients are quantized with respect to the loss of
quality. Quantized coefficients are finally compressed with the Huffman or
Arithmetic coding. For its simplicity, a lot of improvements were proposed.
[30] proposed different scheme based on 3D DCT. MxM blocks of image are
grouped to sections of size M, which gives as „cube“. Values are than
processed with 3D DCT. The rest of the algorithm is very similar to the
classic DCT. Some research has also been done in a calculation of DCT matrix.
Its approximation for faster compression and decompression was proposed by
[39]. Another approach from [8] modifies classic matrix and replace its values
with only -1, 0, 1. That leads to faster calculation, because no division or
multiplication is needed. However, result image has a lower visual quality.

####  4.1.2 KLT (PCA)

Karhunen-Lowe transform is based on a principal component analysis (PCA). In
its core, its same as DCT. The main difference is in a transform matrix. KLT
matrix is obtained from eigen vectors of covariance matrix. Eigen vectors are
reordered with respect to their eigen values. Ordered vectors are used as rows
(or columns) of a transform matrix. More related information can be found in
[33]. DCT can be considered as averaged KLT. KLT is, unlike DCT, optimal
transform. That means, we can achieve better quality with smaller size. Main
disadvantages comes from transform matrix. This matrix need to be stored along
with a compressed image. Second, its computation can be slow. One solution to
this problem is proposed in [47].

####  4.1.3 DWT

The main core is almost identical with the one used for lossless compression
(as described before). Transformed values are quantized before final step
(using EZW or SPIHT [35]). Apart integer transformation, the floating point
version can be used for lossy compression. Well known format based on DWT is
JPEG2000 [29]. Its result for lower bitrates were improved by [38]. Their
method use image division similar to the one used by quadtree based methods.
Division is done based on an error of the block reconstruction. For
reconstruction, colors are interpolated with anisotropic diffusion.

###  4.2 Other methods

####  4.2.1 Neural Networks

Image can be compressed with an usage of artificial neural networks. Basic
idea is to take a feed-forward neural network with the same number of inputs
and outputs. The hidden layer of a network represents the compressed data.
Simple network scheme can be seen on Figure 2. Apart from storing hidden
layer, neural network weights must be stored as well.

Figure 2: Scheme of feed-forward neural network for lossy compression

The compression process consist of two main steps. First, the neural network
must be trained to adjust weights, that were randomly selected. With those
adjusted weights, the result hidden layer is generated. Input image is usually
divided into N dimensional vectors. Those vectors are inputs of an neural
network. In the compression step, each of N vector is replaced with M values
from the hidden layer. One of the main disadvantages is the compression time.
Adjusting weights is a slow process. An improvement of a compression speed was
proposed in [31]. Initialized weights are not randomly selected, but they are
chose as a result from genetic algorithm. Later, weights are improved with
traditional back-propagation. Another approach is to improve back-propagation
[14] or use a different training method. One possibility is theLevenberg-
Marquardt method as proposed in [26]. Use of this method can be significant
speed up for the networks with only one hidden layer ([44], [45]). Improvement
in compression ratio and quality can be achieved witch histogram equalization
[12].

####  4.2.2 Contours

The main idea is to compress only important parts of an image. The
reconstructed image is than very similar to a vector graphics representation
of bitmap image. Level of details in image depends on the compression ratio.
Those method achieves a very good results for a cartoon based images, where
contours are the most important parts. Areas are usually filled with not much
detail. Such method was described by [20]. Same author in [19] further
improved method and test it also on natural images. They used the Marr-Hidreth
detector to obtain image edges (but any other edge detector can be used as
well). Obtained edges are filtered to preserve only those, that are important.
Result is binary image, losslessly encoded with JBIG algorithm. For color
compression is used quantization scheme. Colors from both sides of contours
are obtained and quantized. Result is again losslessly saved with PAQ
algorithm. Its computational cost is balanced with compression ratio. For
decompression, quantized colors are interpolated with homogeneous diffusion.
For targeting cartoon images, quality is very good (no artefacts like in
transform based methods), but for natural ones, the quality is worse. The
method for natural images was proposed in [37]. Edges are not obtained with an
edge detector, but with a method similar to marching squares. Its advantage
is, that we can obtain enclosed areas. For every brightness value in the
image, set of contours is obtained. According to the threshold level, some of
them are omitted and rest is stored with its brightness value. Level of detail
can be also controlled. One possibility is to store only those contours that
are longer than a certain threshold. Second possibility is to simplification
using e.g. the Ramer–Douglas–Peucker algorithm [10]. A contour can be later
stored by its significant points or using chain code. Chain codes can be more
compact.

####  4.2.3 SVD

With an image representation as a matrix in a mathematical sort of view, work
methods based on SVD (Singular Value Decomposition), first introduced in [4].
Image is decomposed to three matrices (equations 3 and 4).

$A=U\Sigma V^{T}$ (3)

$A=\left[u_{1}.....u_{n}\right]\left[\begin{array}[]{ccccc}\sigma_{1}\\\ &.\\\
&&.\\\ &&&.\\\
&&&&\sigma_{n}\end{array}\right]\left[\begin{array}[]{c}v_{1}\\\ .\\\ .\\\
.\\\ v_{n}\end{array}\right]$ (4)

There is no compression at this point, since we enlarged original 8bit values
to floating point numbers. Matrix $\sum$ is diagonal, U and V members are
vectors ($u_{n}$ with size M and $v_{n}$ N for MxN image). Compression can be
achieved by removing columns and rows from matrices, as illustrated on Figure
3.

Figure 3: Process of SVD compression. First line are full SVD matrices. Second
line represent compression form after removing unnecessary values in black
areas.

Main disadvantage is a speed of the compression. Quality is also lower with
comparison to DCT. SVD method was improved for example in [32], where image is
preprocessed before SVD step. In this article can also be found comparison of
SVD with KLT transform. SVD variation for color images can be found in [1].

####  4.2.4 Other

There are other methods that were researched. One of such approaches is based
on a spline interpolation of image [24]. Only a few pixels of image are taken
and those are interpreted with a cubic spline. Control points of a spline are
selected to minimize overall error of approximation. One of possible approach
can be bisection method. If error of section is lower than selected threshold,
no further division occurs. Non-control points are set as empty value and
image is stored. In a reconstruction, missing values are computed from a cubic
spline interpolation. The proposed technique is tested on RGB images, but same
approach also works in grayscale.

Quadtree based structures can also be used for image compression. One of the
first algorithms with this approach was presented in [41]. In [15] improved
algorithm was used. Quadtree leaf is further divided according to its analysis
(high or low detail image block). Analysis is done using quantized histogram
of difference block (mean is subtracted from each block value). Peaks bigger
than threshold are found in histogram. Number of peaks is used as block
classificator. If block is low-detailed, its mean value is stored, otherwise
division continue. If block is 4x4, no further division is performed. Block is
stored with binary mask instead. The best mask is chosen from predefined
patterns.

Dictionary based methods are well known in a lossless image compression (PNG,
GIF). Its modification for lossy compressions was proposed in [11]. Basic
ideas is to create longer sequences of the same value using quantization. This
can be best shown on simple example. Assuming data sequence 159, 160, 159,
157, 170, we quantize this and obtain 159, 159, 159, 159, 170. This can be
better compressed using dictionary method. Second option is to used similarity
of blocks. If difference error of two blocks is lower than threshold, block
can be replaced one with another. That also improves compression. Dictionary
based methods are similar to near-lossless ones and can also be used that way.

##  5 Comparison

In this section, comparison of earlier discussed methods is conducted.
Compressed size is expressed in bits per pixel (_bpp_). Using this metric is
more readable, because it is image dimension independent. This value can be
very easily computed using equation 5.

$bpp=\frac{8}{M\cdot N}\cdot size$ (5)

$M$and $N$ refer to image dimensions, $size$ is size of compressed image in
bytes.

Besides compressed size, visual quality of reconstructed image is very
important for lossy compressions. As one of standards in this area is PSNR
(Peak signal-to-noise ratio). We can found results using this metric in almost
every article dealing with lossy image compression. PSNR is computed based on
MSE (Mean Square Error). Full equation is shown in 6.

$MSE=\frac{1}{M\cdot N}\sum_{i=0}^{M}\sum_{j=0}^{N}||I(i,j)-K(i,j)||^{2}$

$PSNR=10\cdot log\frac{255^{2}}{MSE}$ (6)

$M$and $N$ refer to image dimensions, $I(i,j)$ signifies original pixel
intensity at location (i,j) and $K(i,j)$ denotes pixel intensity in
reconstructed image.

###  5.1 Lossless compression

Lossless compression was tested on the image set from Figure 4 (their
histograms can be found on Figure 5). Results are taken directly from cited
articles and compared to each other. Same methods can be often found in
different articles for comparison with their methods. We collect all those
data and created summarized table. Sometimes, tests for certain image were not
provided, in that case value “$-$” is used. Collected results can be seen in
Table 1.

Figure 4: Test images used in Table 1. From left to right: Airplane, Crowd, Baboon (or Mandrill), Goldhill, Lake, Landsat, Lenna, Peppers.  Figure 5: Histograms of test images from Figure 4. The order of images is same as in Figure 4.  | [9] | [35] | [46] | [23] | [43] | [29] | [27] | [6] | [16] | [28] | [5] | [2] | [18]
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Airplane | 5.69 | 3.97 | 3.51 | 3.62 | 3.78 | 3.98 | 3.92 | 4.03 | 3.90 | - | 4.23 | 4.39 | -
Baboon | 7.30 | 6.16 | 5.74 | 5.65 | 6.04 | 6.11 | 5.93 | 5.98 | 6.04 | 5.08 | 6.88 | - | 3.60
Crowd | 5.84 | - | 3.76 | 4.03 | 3.91 | 4.19 | - | - | - | - | - | - | -
Goldhill | 6.66 | 4.63 | 4.63 | 4.66 | 4.71 | 4.84 | 4.54 | - | 4.48 | - | 4.73 | 5.08 | 4.30
Lake | 6.84 | - | 4.90 | 4.93 | 4.92 | 5.90 | - | - | - | 8.53 | 5.37 | 5.35 | -
Landsat | 3.98 | - | 3.99 | 4.04 | 7.17 | 7.36 | - | - | - | - | - | - | -
Lenna | 6.84 | 4.18 | 4.11 | 4.05 | 4.23 | 4.31 | 4.15 | 4.44 | 4.24 | 5.07 | 4.54 | 5.09 | 3.80
Peppers | 5.34 | 4.68 | 4.20 | 4.16 | 4.85 | 4.93 | 4.55 | 4.59 | 4.51 | - | 4.81 | 5.30 | 2.80
AVG | 6.06 | 4.91 | 4.50 | 4.54 | 4.95 | 5.20 | 4.80 | 4.76 | 4.63 | 4.42 | 5.21 | 5.04 | 3.63
Table 1: Lossless compression sizes in bpp for standard set of images with
resolution _512x512_. PNG is [9], CALIC is [46], JPEG-LS is [43] and JPEG2000
is [29]. Other methods are not acknowledged as standards.

Even though there are some missing data, we can see the overall compression
performance. The worst overall result came from the oldest tested algorithm,
PNG ([9]). The only image, where this method is competitive, is landsat. Its
because of its character - image has only 20 brightness values (see Figure 5).
On the other hand, the best result is from the newest one, that is using DWT
transform ([18]).

There can also be seen some kind of dependency between compressed size and
histogram. If we look at image of Airplane and Crowd, they have very similar
histograms (only reversed). Their compression ratios are also very similar for
all tested methods.

###  5.2 Lossy compression

For the lossy compression test, standard image, that can be found in
practically every publication, is Lenna (mostly in resolution 256x256). Our
tests will be summarized in graph, because of its clarity. In lossless test,
there was only one possible result. For lossy compression, we can get
different PSNR values for different compressed size. In our tests we used
images from Figure 6.

Figure 6: Test images used in Figure 7 and Figure 8. From left to right:
Lenna, Trui

First test is using Lenna image in resolution 256x256. Results can be seen on
Figure 7. Best result were achieved with JPEG2000 compression, that
significantly outperforms other methods. Very similar results were achieved
with JPG and both tested quadtree methods ([41] and [15]). For larger
compression ratios, neural network from [31] is also competitive. The worst
results were, as aspected, achieved with contour based compression ([37]).
This method is more suitable for specialized images, mostly cartoon graphic
(as was discussed in [19]).

We also added one of near-lossless methods for comparison. That is JPEG-LS,
based on [43]. We set different quality loss and simulated classic lossy
method. As we can see, for higher bitrates, the quality improves very fast,
which is basic of near-lossless method.

We can see some strange behaviour for neural network based compression ([14]).
For lower bitrate, we have better PSNR. This effect can be caused by learning
problems with neural networks. We have tried to bypass this problem by taking
the best results from several independent tests, but as we can see, problem
still persist in a lower bitrates.

Figure 7: PSNR and compression in bpp for image Lenna in resolution of
256x256. Graph legend is sorted from the best to worst overall method.

Second test is using Trui image in resolution 256x256. Results can be seen on
Figure 8. Results for our second image are similar to first one. The best
method is again JPEG2000, but this time with lower lead. Improvement for lower
bitrates of JPEG2000, [38], provides better results as expected. However, for
larger bitrates, quality can be outperformed by JPG. Spline based method [24]
provides better results, than for Lenna image. If we look at Trui, we can see
the consequence of this behaviour. Trui has more smooth areas, and spline can
better describe them. Lenna has more hard edges, were spline is not quite
accurate.

Test with near-lossless JPEG-LS (based on [43]) behave similar to one with
Lenna image. Only for now, the progress of quality loss is slower. The reason
is similar to one, why spline methods works better.

The worst result is, again, achieved with [37].

Figure 8: PSNR and compression in bpp for image Trui in resolution of 256x256.
Graph legend is sorted from the best to worst overall method.

##  6 Conclusion

We have discussed and compared various image compression methods. There are
many more techniques, that were not covered. The need for a better quality and
compression ratio is very important. However, as we can see today, compression
techniques commonly used for images are not very modern. The question of
compression is much more complicated.

New compression algorithm is just the beginning. Second step, to carry through
that method, is much more difficult. We can take simple example from our
comparison. Prediction based method (JPEG-LS) has been developed in year 2000
and it is recognized as industrial standard. It outperforms PNG and lossless
JPEG2000 (in both, quality and speed). And how common can we found images in
this format?

## References

  * [1] Bethany Adams and Nina Manual.  Using the singular value decomposition particularly for the compression of color images, 2005.
  * [2] A. Alarabeyyat, S. Al-Hashemi, T. Khdour, M. Hjouj Btoush, S. Bani-Ahmad, R. Al-Hashemi, and S. Bani-Ahmad.  Lossless image compression technique using combination methods.  Journal of Software Engineering and Applications, 05(10):752–763, 2012.
  * [3] Florin Alexa, Vasile Gui, Catalin Caleanu, and Corina Botoca.  Lossless data compression using neural networks.  In Proceedings of the 7th conference on Circuits, systems, electronics, control and signal processing, CSECS’08, pages 128–132, Stevens Point, Wisconsin, USA, 2008. World Scientific and Engineering Academy and Society (WSEAS).
  * [4] Harry C. Andrews and III Patterson, C.  Singular value decomposition (svd) image coding.  Communications, IEEE Transactions on, 24(4):425–432, 1976.
  * [5] A. Avramovic and B. Reljin.  Gradient edge detection predictor for image lossless compression.  In ELMAR, 2010 PROCEEDINGS, pages 131–134, 2010.
  * [6] Tahar Brahimi, Ali Melit, and Fouad Khelifi.  An improved {SPIHT} algorithm for lossless image coding.  Digital Signal Processing, 19(2):220 – 228, 2009.
  * [7] Macarie Breazu, Antoniu Pitic, Daniel Volovici, and Remus Brad.  Near-lossless lzw image compression.  In SINTES 10 Conference, Caiova, Romania, 2003.
  * [8] R.J. Cintra and F.M. Bayer.  A dct approximation for image compression.  Signal Processing Letters, IEEE, 18(10):579–582, 2011.
  * [9] Lee Daniel Crocker.  PNG: The Portable Network Graphic format.  Dr. Dobb’s Journal, 20(7):36–44, Jully 1995.
  * [10] DAVID H DOUGLAS and THOMAS K PEUCKER.  Algorithms for the reduction of the number of points required to represent a digitized line or its caricature.  Cartographica: The International Journal for Geographic Information and Geovisualization, 10:112–122, 1973.
  * [11] Gabriela Dudek, Przemyslaw Borys, and Zbigniew J. Grzywna.  Lossy dictionary-based image compression method.  Image and Vision Computing, 25(6):883 – 889, 2007.
  * [12] S. Anna Durai and E. Anna Saro.  Image compression with back-propagation neural network using cumulative distribution function, September 2006.
  * [13] P.J.S.G. Ferreira and A.J. Pinho.  Why does histogram packing improve lossless compression rates?  Signal Processing Letters, IEEE, 9(8):259–261, 2002.
  * [14] Saeid Iranmanesh.  A differential adaptive learning rate method for back-propagation neural networks.  In Proceedings of the 10th WSEAS international conference on Neural networks, NN’09, pages 30–34, Stevens Point, Wisconsin, USA, 2009. World Scientific and Engineering Academy and Society (WSEAS).
  * [15] F. Keissarian.  A new quadtree-based image compression technique using pattern matching algorithm.  International Conference on Computational & Experimental Engineering and Sciences, 12:137–144, 2009.
  * [16] H. Kikuchi, K. Funahashi, and S. Muramatsu.  Simple bit-plane coding for lossless image compression and extended functionalities.  In Picture Coding Symposium, 2009. PCS 2009, pages 1–4, 2009.
  * [17] Juan Ignacio Larrauri.  A new algorithm for lossless compression applied to two-dimensional static images.  In Proceedings of the 6th international conference on Communications and Information Technology, and Proceedings of the 3rd World conference on Education and Educational Technologies, WORLD-EDU’12/CIT’12, pages 56–60, Stevens Point, Wisconsin, USA, 2012. World Scientific and Engineering Academy and Society (WSEAS).
  * [18] Jia Li.  An improved wavelet image lossless compression algorithm.  Optik - International Journal for Light and Electron Optics, 124(11):1041 – 1044, 2013.
  * [19] Markus Mainberger, AndrÃ©s Bruhn, Joachim Weickert, and SÃžren Forchhammer.  Edge-based compression of cartoon-like images with homogeneous diffusion.  Pattern Recognition, 44(9):1859 – 1873, 2011.  <ce:title>Computer Analysis of Images and Patterns</ce:title>.
  * [20] Markus Mainberger and Joachim Weickert.  Edge-based image compression with homogeneous diffusion.  In Xiaoyi Jiang and Nicolai Petkov, editors, Computer Analysis of Images and Patterns, volume 5702 of Lecture Notes in Computer Science, pages 476–483. Springer Berlin Heidelberg, 2009.
  * [21] A.S. Mamatha and V. Singh.  Near lossless image compression system.  In Microelectronics and Electronics (PrimeAsia), 2012 Asia Pacific Conference on Postgraduate Research in, pages 35–41, 2012.
  * [22] T. Meyyappan, S.M. Thamarai, and N.M. Jeya Nachiaban.  A new method for lossless image compression using recursive crack coding.  In Dhinaharan Nagamalai, Eric Renault, and Murugan Dhanuskodi, editors, Advances in Digital Image Processing and Information Technology, volume 205 of Communications in Computer and Information Science, pages 128–135. Springer Berlin Heidelberg, 2011.
  * [23] G. Motta, J.A. Storer, and B. Carpentieri.  Lossless image coding via adaptive linear prediction and classification.  Proceedings of the IEEE, 88(11):1790–1796, 2000.
  * [24] R. Muthaian, K. NeelaKantan, Sharma V., and Arora A.  Image compression and reconstruction using cubic spline interpolation technique.  American Journal of Applied Sciences, 5:1562–1564, November 2008\.
  * [25] E. Nasr-Esfahani, S. Samavi, N. Karimi, and S. Shirani.  Near-lossless image compression based on maximization of run length sequences.  In Image Processing, 2007. ICIP 2007. IEEE International Conference on, volume 4, pages IV – 177–IV – 180, 2007.
  * [26] N. Sreekumar P. Karthikeyan.  A study on image compression with neural networks using modified levenberg maruardt method.  Global Journal of Computer Science and Technology, 11, March 2011\.
  * [27] H. Pan, W. C Siu, and N.F. Law.  Lossless image compression using binary wavelet transform.  Image Processing, IET, 1(4):353–362, 2007.
  * [28] E. Puthooran, R.S. Anand, and S. Mukherjee.  Lossless image compression using bpnn predictor with contextual error feedback.  In Multimedia, Signal Processing and Communication Technologies (IMPACT), 2011 International Conference on, pages 145–148, 2011.
  * [29] Majid Rabbani and Rajan Joshi.  An overview of the {JPEG} 2000 still image compression standard.  Signal Processing: Image Communication, 17(1):3 – 48, 2002.  <ce:title>JPEG 2000</ce:title>.
  * [30] V.N.P. Raj and T. Venkateswarlu.  A novel approach to medical image compression using sequential 3d dct.  In Conference on Computational Intelligence and Multimedia Applications, 2007. International Conference on, volume 3, pages 146–152, 2007\.
  * [31] G G Rajput and Vrinda Shivashetty.  Modeling of neural image compression using ga and bp : a comparative approach.  IJACSA - International Journal of Advanced Computer Science and Applications, (Special Issue):26–34, 2011.
  * [32] Abhiram Ranade, Srikanth S. Mahabalarao, and Satyen Kale.  A variation on svd based image compression.  Image and Vision Computing, 25(6):771 – 777, 2007.
  * [33] Kamisetty Ramamohan Rao and Pat Yip, editors.  The Transform and Data Compression Handbook.  CRC Press, Inc., Boca Raton, FL, USA, 2000.
  * [34] Vinay Rawat, Ravindra Singh, Mayank Pawar, and Raj Mishra.  Lossless gray image compression using logic minimization.  Recent Research in Science and Technology, 4(1), 2012.
  * [35] A. Said and W.A. Pearlman.  A new, fast, and efficient image codec based on set partitioning in hierarchical trees.  Circuits and Systems for Video Technology, IEEE Transactions on, 6(3):243–250, 1996.
  * [36] David Salomon.  Data Compression: The Complete Reference.  Second edition, 2000.
  * [37] G. Scarmana.  A contour-based approach to image compression.  In Digital Image Computing Techniques and Applications (DICTA), 2011 International Conference on, pages 186–190, 2011.
  * [38] Christian Schmaltz, Joachim Weickert, and Andres Bruhn.  Beating the quality of jpeg 2000 with anisotropic diffusion.  In Joachim Denzler, Gunther Notni, and Herbert Susse, editors, Pattern Recognition, volume 5748 of Lecture Notes in Computer Science, pages 452–461. Springer Berlin Heidelberg, 2009.
  * [39] R.K. Senapati, U.C. Pati, and K.K. Mahapatra.  A low complexity orthogonal 8x8 transform matrix for fast image compression.  In India Conference (INDICON), 2010 Annual IEEE, pages 1–4, 2010\.
  * [40] J.M. Shapiro.  Embedded image coding using zerotrees of wavelet coefficients.  Signal Processing, IEEE Transactions on, 41(12):3445–3462, 1993\.
  * [41] E. Shusterman and M. Feder.  Image compression via improved quadtree decomposition algorithms.  Image Processing, IEEE Transactions on, 3(2):207–215, 1994.
  * [42] G.K. Wallace.  The jpeg still picture compression standard.  Consumer Electronics, IEEE Transactions on, 38(1):xviii–xxxiv, 1992\.
  * [43] M.J. Weinberger, G. Seroussi, and G. Sapiro.  The loco-i lossless image compression algorithm: principles and standardization into jpeg-ls.  Image Processing, IEEE Transactions on, 9(8):1309–1324, 2000.
  * [44] B.M. Wilamowski, Yixin Chen, and A. Malinowski.  Efficient algorithm for training neural networks with one hidden layer.  In Neural Networks, 1999. IJCNN ’99. International Joint Conference on, volume 3, pages 1725–1728 vol.3, 1999.
  * [45] B.M. Wilamowski and Hao Yu.  Improved computation for levenberg-marquardt training.  Neural Networks, IEEE Transactions on, 21(6):930–937, 2010.
  * [46] Xiaolin Wu and N. Memon.  Calic-a context based adaptive lossless image codec.  In Acoustics, Speech, and Signal Processing, 1996. ICASSP-96. Conference Proceedings., 1996 IEEE International Conference on, volume 4, pages 1890–1893 vol. 4, 1996.
  * [47] Daoqiang Zhang and Songcan Chen.  Fast image compression using matrix k-l transform.  Neurocomput., 68:258–266, October 2005.
  * [48] J. Ziv and A. Lempel.  A universal algorithm for sequential data compression.  Information Theory, IEEE Transactions on, 23(3):337–343, 1977.


# Dual-Code Bounds on Multiple Concurrent
(Local) Data Recovery

Gianira N. Alfarano G. N. Alfarano is supported by Swiss Science Foundation
grant n. 188430. University of Zurich, Switzerland  Alberto Ravagnani A.
Ravagnani is in part supported by Dutch Research Council grant
VI.Vidi.203.045. Eindhoven University of Technology, the Netherlands  Emina
Soljanin E. Soljanin is in part supported by NSF Award CIF-2122400. Rutgers
University, NJ, USA

###### Abstract

We are concerned with linear redundancy storage schemes regarding their
ability to provide concurrent (local) recovery of multiple data objects. This
paper initiates a study of such systems within the classical coding theory. We
show how we can use the structural properties of the generator matrix defining
the scheme to obtain a bounding polytope for the set of data access rates the
system can support. We derive two dual distance outer bounds, which are sharp
for some large classes of matrix families.

##  1 Introduction

Distributed computing systems rely on their storage layers to provide data
access services for executing applications. Thus, the system’s overall
performance depends on the underlying storage system’s data access
performance. Distributed storage systems strive to maximize the number of
concurrent data access requests they can support with fixed resources.
Replicating data objects according to their relative popularity and access
volume helps achieve this goal. However, these quantities are often
unpredictable. In emerging applications such as edge computing, the expected
number of users and their data interests fluctuate, and data storage schemes
should support such dynamics [1]. Erasure-coding has emerged as an efficient
and robust form of redundant storage, which can flexibly handle skews in the
request rates.

Recent work on redundant distributed storage access introduced the notion of
the service rate region of a redundancy scheme that includes all data access
requests that the system can serve [2, 3, 4, 5, 6, 7]. To understand this
concept, consider a distributed system that stores $k$ different data objects
by encoding them into $n$ and storing the $n$ coded objects on $n$ different
nodes. Each of the $n$ nodes can serve requests at a rate $\mu$ (i.e., has
service capacity $\mu$). The system can serve requests to access the $k$ data
objects that arrive at rates $\lambda_{1}$, $\lambda_{2}$, …, $\lambda_{k}$ if
each request can be routed to a group of nodes that can jointly fulfill the
request, and the total request rate allocated to each node does not exceed its
service capacity $\mu$. We call the set of such request vectors
($\lambda_{1}$, $\lambda_{2}$, …, $\lambda_{k}$) the _service rate region_ of
a coded distributed system.

The overview paper [2] postulated the service rate region as an important
consideration in the design of erasure-coded distributed systems. It
highlights several open problems that can be grouped into two broad threads:
1) characterizing the service rate region of a given code and finding the
optimal request allocation, and 2) designing the underlying erasure code for a
given service rate region. The paper argued that the presented problems not
only require expertise from different areas, but have also already been
addressed in those areas in some special forms and under different names.
Moreover, it explained how some problems associated with the service rate
region generalize previously studied distributed problems such as batch codes,
codes with locality and availability, and private information retrieval [8, 9,
10, 11, 12, 13, 14, 15, 16].

The numerous open problems described in [2] (in both groups mentioned above)
could be seen as performance analysis and networking problems as well as
coding theory and data allocation problems. These problems could be addressed
by a wide variety of scientists according to their interests and expertise.
Our contribution. The goal of this paper is to initiate a study of redundancy
schemes within the classical coding theory. We focus on characterizing the
service rate region of a storage scheme defined by a rank $k$ generator matrix
$G$, which is a convex polytope in $\mathbb{R}^{k}$. Our ultimate goal is to
establish a series of inequalities that, when combined, cut out the service
region. This paper makes a first step towards this goal by showing how some
structural properties of $G$ can be used to find a polytope that contains the
service rate region, giving an outer bound for the latter. More precisely, we
establish a Total Capacity Bound for the service rate region determined by a
matrix $G$, as well as two Dual Distance Bounds that take into account
different structural properties of $G$. We also show that the bounding
polytope we find coincides with the service rate region in some special cases,
e.g. for some large classes of MDS codes.

This paper is organized as follows. Sec. 2 defines the problem. Sec. 3 shows
some properties of the recovery sets of a linear redundancy scheme and
introduces a way to compare storage schemes. Sec. 4 derives the Total Capacity
Bound for the service rate region and two Dual Distance Bounds. Sec. 5
outlines future work plans.

##  2 Distributed Coded Recovery Systems

In this section we establish the notation for the rest of the paper, define
distributed coded systems and their service rate region.

######  Notation 2.1.

Throughout the paper, $\mathbb{F}_{q}$ denotes the finite field with $q$
elements where $q$ is a prime power. We work with integers $n>k\geq 2$, a real
number $\mu\geq 1$, and a fixed matrix $G\in\mathbb{F}_{q}^{k\times n}$ of
rank $k$. We assume that $G$ has no all-zero column and denote by $G^{j}$ its
$j$th column.

We consider coded distributed systems where $k$ data objects are linearly
encoded into $n$ objects stored on $n$ servers. Each server stores exactly one
object and the objects are elements of $\mathbb{F}_{q}$.

Such a distributed coded system is fully specified by a rank $k$ matrix
$G\in\mathbb{F}_{q}^{k\times n}$, which we call the generator matrix of the
system. If $(x_{1},\dots,x_{k})\in\mathbb{F}_{q}^{k}$ is the $k$-tuple of
objects to be stored, then the $j$th server stores the $j$th component of the
vector

$(x_{1},\dots,x_{k})\cdot G\in\mathbb{F}_{q}^{n}.$

We say that the matrix $G$ is systematic if its first $k$ columns form the
identity $k\times k$ matrix.

We consider $k$-tuples $(\lambda_{1},\ldots,\lambda_{k})\in\mathbb{R}^{k}$ of
rate requests to access the $k$ objects. More precisely, $\lambda_{i}$ is the
rate request for the $i$th object. Each of the $n$ servers can serve request
at the rate of at most $\mu\geq 1$. The parameter $\mu$ is called the server’s
capacity.

Each user gets assigned to a set of servers that, together, allow recovering
the desired object. An object can be recovered from different server sets,
which motivates the following terminology.

######  Definition 2.2.

For $i\in\\{1,\dots,k\\}$, let

$\mathscr{R}^{\textnormal{all}}_{i}:=\\{R\subseteq\\{1,\dots,n\\}\mid
e_{i}\in\langle G^{j}\mid j\in R\rangle\\},$

where $e_{i}\in\mathbb{F}_{q}^{k}$ denotes the $i$th standard basis vector and
$\langle G^{j}\mid j\in R\rangle$ is the span of the columns of $G$ indexed by
$R$. The elements of $\mathscr{R}^{\textnormal{all}}_{i}$ are the recovery
sets for the $i$th object.

Note that, in the above definition, we have
$\mathscr{R}^{\textnormal{all}}_{i}\neq\emptyset$ for all
$i\in\\{1,\ldots,k\\}$. This is a simple consequence of the fact that $G$ has
rank $k$. Moreover, $R\neq\emptyset$ for all $i\in\\{1,\dots,k\\}$ and
$R\in\mathscr{R}^{\textnormal{all}}_{i}$. We use the superscript “all” to
indicate that $\mathscr{R}_{i}^{\textnormal{all}}$ contains all the recovery
sets for the symbol $i$.

######  Example 2.3.

Let $k=2$, $n=4$, $q=3$ and

$G:=\begin{pmatrix}1&0&1&1\\\ 0&1&2&1\end{pmatrix}\in\mathbb{F}_{3}^{2\times
4}.$

Then, we have

$\displaystyle\mathscr{R}^{\textnormal{all}}_{1}$
$\displaystyle=\\{\\{1\\},\\{2,3\\},\\{2,4\\},\\{3,4\\},\\{2,3,4\\}\\},$
$\displaystyle\mathscr{R}^{\textnormal{all}}_{2}$
$\displaystyle=\\{\\{2\\},\\{1,3\\},\\{1,4\\},\\{3,4\\},\\{1,3,4\\}\\}.$

When designing a recovery system starting from $G$, not all recovery sets need
to be considered.

######  Definition 2.4.

A recovery $G$-system is a $k$-tuple
$\mathscr{R}=(\mathscr{R}_{1},\ldots,\mathscr{R}_{k})$ of subsets of
$\\{1,\ldots,n\\}$ with
$\mathscr{R}_{i}\subseteq\mathscr{R}_{i}^{\textnormal{all}}$ and
$\mathscr{R}_{i}\neq\emptyset$ for all $i\in\\{1,\ldots,k\\}$.

The service rate region of a recovery $G$-system $\mathscr{R}$ is the set of
all request rate tuples $(\lambda_{1},\ldots,\lambda_{k})\in\mathbb{R}^{k}$
that can be served by the system.

######  Definition 2.5.

Let $\mathscr{R}=(\mathscr{R}_{1},\ldots,\mathscr{R}_{k})$ be a recovery
$G$-system. The service rate region associated with $\mathscr{R}$ and $\mu$ is
the set of all $(\lambda_{1},\ldots,\lambda_{k})\in\mathbb{R}^{k}$ for which
there exists a collection of real numbers

$\\{\lambda_{i,R}\mid i\in\\{1,\ldots,k\\},\,R\in\mathscr{R}_{i}\\}$

with the following properties:

$\displaystyle\sum_{R\in\mathscr{R}_{i}}\lambda_{i,R}$
$\displaystyle=\lambda_{i}$ $\displaystyle\textnormal{ for }1\leq i\leq k,$
(1)
$\displaystyle\sum_{i=1}^{k}\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
j\in R\end{subarray}}\lambda_{i,R}$ $\displaystyle\leq\mu\ $
$\displaystyle\textnormal{ for }1\leq j\leq n,$ (2)
$\displaystyle\lambda_{i,R}$ $\displaystyle\geq 0\ $
$\displaystyle\textnormal{ for }1\leq i\leq k,\,R\in\mathscr{R}_{i}.$ (3)

A collection $\\{\lambda_{i,R}\\}$ of real numbers that satisfy the above
three properties is called a feasible allocation for $(\mathscr{R},\mu)$. The
service rate region associated with $\mathscr{R}$ and $\mu$ is denoted by

$\Lambda(\mathscr{R},\mu)\subseteq\mathbb{R}^{k}.$

######  Remark 2.6.

We have $\Lambda(\mathscr{R},\mu)=\mu\cdot\Lambda(\mathscr{R},1)$ for any
recovery $G$-system $\mathscr{R}$. Therefore, we will simply call
$\Lambda(\mathscr{R},1)$ the service rate region of $G$.

Our main goal is to establish outer bounds for the service rate region
$\Lambda(\mathscr{R},1)$ of a recovery $G$-system $\mathscr{R}$, in the form
of a bounding polytope.

######  Example 2.7.

Let $G$ be as in Example 2.3. Corollary 4.7 will give us the bounding polytope
for $\Lambda(\mathscr{R}^{\textnormal{all}},1)$ depicted in Figure 1. The
outer bound is sharp.

Figure 1: Service rate region for the $G$-system in Example 2.7. The lines
bounding the polytope are obtained from Corollary 4.7.

##  3 Minimal Recovery Sets

A natural question is how the service rate region changes when changing the
recovery $G$-system. An immediate observation is the following. The result
easily follows from Definition 2.5 and is therefore left to the reader.

######  Proposition 3.1.

Suppose that $\mathscr{R}=(\mathscr{R}_{1},\ldots,\mathscr{R}_{k})$ and
$\mathscr{R}^{\prime}=(\mathscr{R}^{\prime}_{1},\ldots,\mathscr{R}^{\prime}_{k})$
are recovery $G$-systems with
$\mathscr{R}^{\prime}_{i}\subseteq\mathscr{R}_{i}$ for all
$i\in\\{1,\ldots,k\\}$. Then
$\Lambda(\mathscr{R},1)\supseteq\Lambda(\mathscr{R}^{\prime},1)$. In
particular,
$\Lambda(\mathscr{R},\mu)\subseteq\Lambda(\mathscr{R}^{\textnormal{all}},\mu)$
for any recovery $G$-system $\mathscr{R}$.

The service rate region, however, does not change when selecting from
$\mathscr{R}^{\textnormal{all}}$ the recovery sets that are minimal with
respect to inclusion, in the following precise sense.

######  Definition 3.2.

A set $R\in\mathscr{R}^{\textnormal{all}}_{i}$ is $i$-minimal if there is no
$R^{\prime}\in\mathscr{R}^{\textnormal{all}}_{i}$ with $R^{\prime}\subsetneq
R$. We define $\mathscr{R}^{\textnormal{min}}$ as the recovery $G$-system
defined, for all $i$, by

$\mathscr{R}_{i}^{\textnormal{min}}:=\\{R\in\mathscr{R}^{\textnormal{all}}_{i}\mid
R\mbox{ is $i$-minimal}\\}.$

######  Proposition 3.3.

We have
$\Lambda(\mathscr{R}^{\textnormal{min}},1)=\Lambda(\mathscr{R}^{\textnormal{all}},1)$.

Therefore, when studying the service rate region of the system defined by $G$
one may or may not restrict to the minimal recovery sets.

###### Proof of Proposition 3.3.

The inclusion “$\subseteq$” follows directly from Proposition 3.1. To prove
the inclusion “$\supseteq$”, let
$(\lambda_{1},\ldots,\lambda_{k})\in\Lambda(\mathscr{R}^{\textnormal{all}},1)$.
By definition, there exist a collection of real numbers

$\\{\lambda_{i,R}\mid
i\in\\{1,\ldots,k\\},\,R\in\mathscr{R}^{\textnormal{all}}_{i}\\},$

satisfying (1)–(3). We will show that
$(\lambda_{1},\ldots,\lambda_{k})\in\Lambda(\mathscr{R}^{\textnormal{min}},1)$.
In order to do so, for each $i\in\\{1,\ldots,k\\}$ and
$R\in\mathscr{R}^{\textnormal{all}}_{i}$ we fix a set
$\mbox{min}_{i}(R)\in\mathscr{R}_{i}^{\textnormal{min}}$ such that
$R\supseteq\mbox{min}_{i}(R)$. For $Q\in\mathscr{R}_{i}^{\textnormal{min}}$
define

$\lambda_{i,Q}:=\sum_{\begin{subarray}{c}R\in\mathscr{R}^{\textnormal{all}}_{i}\\\
\textnormal{min}_{i}(R)=Q\end{subarray}}\lambda_{i,R}.$

Then the numbers $\\{\lambda_{i,Q}\mid
i\in\\{1,\ldots,k\\},\,Q\in\mathscr{R}_{i}^{\textnormal{min}}\\}$ satisfy
(1)–(3). ∎

##  4 A Total Capacity Bound

We here put forward a simple but powerful idea to obtain outer bounds for the
service rate region of a coded system. As an application of this idea, we
derive two dual-distance-type bounds in this context.

######  Lemma 4.1 (Total Capacity Bound).

Let $\mathscr{R}$ be a recovery $G$-system and let $\\{\lambda_{i,R}\\}$ be a
feasible allocation for $(\mathscr{R},1)$. We have

$\displaystyle\sum_{i=1}^{k}\sum_{R\in\mathscr{R}_{i}}|R|\lambda_{i,R}\leq n.$
(4)

###### Proof.

The bound is obtained by summing the inequalities in (2), for $1\leq j\leq n$,
∎

######  Remark 4.2.

The Total Capacity Bound of Lemma 4.1 put in evidence the cardinality of the
recovery sets. It can be applied directly when a lower bound for this quantity
is known. More precisely, if every recovery set of a $G$-system $\mathscr{R}$
has size at least $M$, then every
$(\lambda_{1},\ldots,\lambda_{k})\in\Lambda(\mathscr{R},1)$ satisfies

$\lambda_{1}+\cdots+\lambda_{k}\leq n/M.$

Lemma 4.1 motivates us to determine the properties of $G$ that determine the
cardinalities of the recovery sets, and how they shape the service rate
region. This is the program we initiate in this paper.

###  4.1 First Dual Distance Bound

We next establish a connection between the recovery sets of a systematic coded
system and the codewords of the code whose parity-check matrix is $G$. By
combining this with the Total Capacity Bound, we obtain our First Dual
Distance Bound.

######  Notation 4.3.

In the sequel, we denote by $\mathscr{C}$ the linear code generated by $G$,
and by $\mathscr{C}^{\perp}$, its dual code. Note that $\mathscr{C}$ is an
$[n,k]_{q}$ code. We let $d^{\perp}$ be the minimum distance of
$\mathscr{C}^{\perp}$. Recall that the (Hamming) support of a vector
$x\in\mathbb{F}_{q}^{n}$ is $\sigma(x):=\\{1\leq i\leq n\mid x_{i}\neq 0\\}$.

######  Proposition 4.4.

Suppose that $G$ is systematic. Let $R\subseteq\\{1,\dots,n\\}$ and
$i\in\\{1,\dots,k\\}$. Then $R\in\mathscr{R}^{\textnormal{all}}_{i}$ if and
only if $R=\\{i\\}$ or there exists a codeword $x\in\mathscr{C}^{\perp}$ with
$\sigma(x)\subseteq R\cup\\{i\\}$ and $i\in\sigma(x)$.

###### Proof.

By definition, $R\in\mathscr{R}^{\textnormal{all}}_{i}$ if and only if the
span of the columns of $G$ indexed by $R\cup\\{i\\}$ contains $e_{i}$. This
happens if and only if $R=\\{i\\}$ or there exists a linear combination of the
columns of $G$ indexed by $R$, where the $i$th column of $G$ is taken with a
nonzero coefficient, that gives zero. The latter condition is equivalent to
the existence of a codeword $x\in\mathscr{C}^{\perp}$ with $i\in\sigma(x)$ and
$\sigma(x)\subseteq R$. ∎

######  Corollary 4.5.

If $G$ is systematic, $i\in\\{1,\ldots,k\\}$ and
$R\in\mathscr{R}^{\textnormal{all}}_{i}$, then $R=\\{i\\}$ or $|R|\geq
d^{\perp}-1$.

We are now ready to present the First Dual Distance Bound.

######  Theorem 4.6 (First Dual Distance Bound).

Suppose that $G$ is systematic and let $\mathscr{R}$ be a recovery $G$-system.
If $(\lambda_{1},\dots,\lambda_{k})\in\Lambda(\mathscr{R},1)$, then

$\sum_{i=1}^{k}\Bigl{(}\min\\{\lambda_{i},1\\}+(d^{\perp}-1)\max\\{0,\lambda_{i}-1\\}\Bigr{)}\leq
n.$

###### Proof.

Let $(\lambda_{1},\dots,\lambda_{k})\in\Lambda(\mathscr{R},1)$ and let
$\\{\lambda_{i,R}\\}$ be a feasible allocation. By Corollary 4.5, for every
$i\in\\{1,\ldots,k\\}$ and every set $R\in\mathscr{R}_{i}$ with $R\neq\\{i\\}$
we have $|R|\geq d^{\perp}-1$. We can therefore rewrite and bound the LHS of
(4) as follows:

$\displaystyle\allowdisplaybreaks\sum_{i=1}^{k}$
$\displaystyle\lambda_{i,\\{i\\}}+\sum_{i=1}^{k}\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
R\neq\\{i\\}\end{subarray}}|R|\lambda_{i,R}$
$\displaystyle\geq\sum_{i=1}^{k}\lambda_{i,\\{i\\}}+(d^{\perp}-1)\sum_{i=1}^{k}\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
R\neq\\{i\\}\end{subarray}}\lambda_{i,R}$
$\displaystyle=\sum_{i=1}^{k}\lambda_{i,\\{i\\}}+(d^{\perp}-1)\sum_{i=1}^{k}(\lambda_{i}-\lambda_{i,\\{i\\}})$
$\displaystyle=(d^{\perp}-1)\sum_{i=1}^{k}\lambda_{i}-(d^{\perp}-2)\sum_{i=1}^{k}\lambda_{i,\\{i\\}}.$
(5)

Since $G$ has no all-zero column, we have $d^{\perp}\geq 2$. Therefore, since
$\lambda_{i,\\{i\\}}\leq\min\\{\lambda_{i},1\\}$ for all $i$, we can further
say that the right-hand side of (4.1) is at least

$\displaystyle(d^{\perp}-1)\sum_{i=1}^{k}\lambda_{i}-(d^{\perp}-2)\sum_{i=1}^{k}\min\\{\lambda_{i},1\\}$
$\displaystyle=\sum_{i=1}^{k}\Bigl{(}\min\\{\lambda_{i},1\\}+(d^{\perp}-1)\max\\{0,\lambda_{i}-1\\}\Bigr{)},$

which, combined with (4), gives the statement. ∎

We can apply Theorem 4.6 to families of systematic codes whose dual distance
is known. For example, by considering the class of systematic MDS codes we
obtain the following result.

######  Corollary 4.7.

Suppose that $G$ is systematic and that it generates an MDS code. Then for all
$(\lambda_{1},\dots,\lambda_{k})\in\Lambda(\mathscr{R},1)$ we have

$\sum_{i=1}^{k}\Bigl{(}\min\\{\lambda_{i},1\\}+k\cdot\max\\{0,\lambda_{i}-1\\}\Bigr{)}\leq
n.$

######  Remark 4.8.

The previous corollary on MDS codes is sharp whenever $k\leq n-k$; see [7,
Theorem 2].

###  4.2 Second Dual Distance Bound

The goal of this subsection is to identify and study new, non-classical
parameters of the matrix $G$ that play a role in determining the associated
service rate region. As an application, we obtain a second outer bound for the
service rate region of a coded system, which refines the First Dual Distance
Bound of Theorem 4.6 under some assumptions.

######  Notation 4.9.

In the sequel, for all $i\in\\{1,\ldots,k\\}$, we let

$G_{i}=\Bigl{(}G\mid e_{i}^{\top}\Bigr{)}\in\mathbb{F}_{q}^{k\times(n+1)}$

be the matrix obtained from $G$ by appending the $i$th standard basis vector
as the $(n+1)$-th column. Then $G_{i}$ generates an $[n+1,k]_{q}$ code, which
we denote by $\mathscr{C}_{i}\subseteq\mathbb{F}_{q}^{n+1}$. Its dual is
$\mathscr{C}_{i}^{\perp}$. For $i\in\\{1,\ldots,k\\}$, we introduce the
following sets and parameters:

$\displaystyle\Gamma_{i}$ $\displaystyle:=\\{\textnormal{wt}(x)\mid
x\in\mathscr{C}_{i}^{\perp},\,n+1\in\sigma(x)\\},$ $\displaystyle\gamma_{i}$
$\displaystyle:=|\Gamma_{i}|~{}~{}\text{and}~{}~{}\delta_{i}^{1}:=\min(\Gamma_{i}).$

Moreover, we let

$\delta_{i}^{2}:=\min\\{\textnormal{wt}(x)\mid
x\in\mathscr{C}_{i}^{\perp},\,n+1\in\sigma(x),\textnormal{wt}(x)>\delta_{i}^{1}\\},$

with the convention that $\delta_{i}^{2}=\delta_{i}^{1}$ when $\gamma_{i}=1$.
Finally, we define

$\omega_{i}:=\frac{|\\{x\in\mathscr{C}_{i}^{\perp}:n+1\in\sigma(x),\,\textnormal{wt}(x)=\delta_{i}^{1}\\}|}{q-1}.$

The structural parameters defined in Notation 4.9 play an essential role in
determining the corresponding service rate region. In this conference paper,
we give preliminary evidence of this with a result that extends the First Dual
Distance Bound of Theorem 4.6 to possibly non-systematic matrices.

We start by describing the recovery sets of $\mathscr{R}^{\textnormal{all}}$
in terms of the codes $\mathscr{C}_{i}$, $i\in\\{1,\ldots,k\\}$. The proof of
the next result is similar to the one of Proposition 4.4, and we, therefore,
omit it.

######  Proposition 4.10.

Let $R\subseteq\\{1,\ldots,n\\}$ and $i\in\\{1,\ldots,k\\}$. Then
$R\in\mathscr{R}^{\textnormal{all}}_{i}$ if and only if there is
$x\in\mathscr{C}_{i}^{\perp}$ with $\sigma(x)\subseteq R\cup\\{n+1\\}$ and
$n+1\in\sigma(x)$. In particular, if $R\in\mathscr{R}^{\textnormal{all}}_{i}$
then $|R|\geq\delta_{i}^{1}-1$.

Proposition 4.10 means that there are $\omega_{1}$ sets
$R\in\mathscr{R}^{\textnormal{all}}_{i}$ with size $\delta_{i}^{1}$. All the
other sets have size at least $\delta_{i}^{2}$.

######  Theorem 4.11 (Second Dual Distance Bound).

Let $\mathscr{R}$ be a recovery $G$-system and let
$(\lambda_{1},\ldots,\lambda_{k})\in\Lambda(\mathscr{R},1)$. For each
$i\in\\{1,\ldots,k\\}$, define $\ell_{i}:=\min\\{\lambda_{i},1\\}$. Then

$\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{2}-1)(\lambda_{i}-\omega_{i}\ell_{i})+(\delta_{i}^{1}-1)\,\omega_{i}\ell_{i}\Bigr{)}\leq
n.$

###### Proof.

Let $(\lambda_{1},\ldots,\lambda_{k})\in\Lambda(\mathscr{R},1)$ and let
$\\{\lambda_{i,R}\\}$ be a feasible allocation. By Proposition 4.10 and (1) we
have that, for all $i\in\\{1,\ldots,k\\}$,

$\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|>\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R}=\lambda_{i}-\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|=\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R},$ (6)

where the sum over an empty set is $0$. Thus the LHS of (4) can be rewritten
as

$\displaystyle\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{1}-1)\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|=\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R}+\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|>\delta_{i}^{1}-1\end{subarray}}|R|\,\lambda_{i,R}\Bigr{)}.$ (7)

Using (6), Proposition 4.10, and the definition of $\delta_{i}^{2}$, we find
that the quantity in (7) is at least

$\displaystyle\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{1}-1)\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|=\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R}+(\delta_{i}^{2}-1)\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|>\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R}\Bigr{)}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{2}-1)\lambda_{i}-(\delta_{i}^{2}-\delta_{i}^{1})\sum_{\begin{subarray}{c}R\in\mathscr{R}_{i}\\\
|R|=\delta_{i}^{1}-1\end{subarray}}\lambda_{i,R}\Bigr{)}$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{2}-1)\lambda_{i}-(\delta_{i}^{2}-\delta_{i}^{1})\omega_{i}\ell_{i}\Bigr{)},$
(8)

where the latter inequality follows from the fact that
$\delta_{i}^{2}-\delta_{i}^{1}\geq 0$ and $\lambda_{i,R}\leq\ell_{i}$ for all
$i\in\\{1,\ldots,k\\}$. Finally, the last line of (8) is equal to

$\sum_{i=1}^{k}\Bigl{(}(\delta_{i}^{2}-1)\Bigl{(}\lambda_{i}-\omega_{i}\ell_{i}\Bigr{)}+(\delta_{i}^{1}-1)\omega_{i}\ell_{i}\Bigr{)},$

which with (4) and (7) concludes the proof. ∎

We illustrate the previous result with two examples where $G$ is not
systematic.

######  Example 4.12 (First-Order Reed-Muller Code).

Consider the following non-systematic generator matrix
$G\in\mathbb{F}_{2}^{4\times 8}$ of the first order Reed-Muller code, namely

$G:=\begin{pmatrix}1&1&1&1&0&0&0&0\\\ 1&0&1&0&1&0&1&0\\\ 1&1&0&0&1&1&0&0\\\
1&1&1&1&1&1&1&1\end{pmatrix}.$

Consider the codes generated by $G_{i}$, for $i\in\\{1,2,3,4\\}$. We have that
$\delta_{1}^{1}=\delta_{2}^{1}=\delta_{3}^{1}=3$,
$\omega_{1}=\omega_{2}=\omega_{3}=4$,
$\delta_{1}^{2}=\delta_{2}^{2}=\delta_{2}^{2}=5$, $\delta_{4}^{1}=2$,
$\omega_{4}=1$ and $\delta_{4}^{2}=4$. Thus Thm 4.11 reads, with
$\ell_{i}=\min\\{\lambda_{i},1\\}$ for all $i$,

$\displaystyle
4\lambda_{1}+4\lambda_{2}+4\lambda_{3}-8\ell_{1}-8\ell_{2}-8\ell_{3}+3\lambda_{4}-2\ell_{4}\leq
8.$ (9)

The bound is not sharp in this case. Indeed, suppose that
$\lambda_{2}=\lambda_{3}=0$.

$\lambda_{1}$$\lambda_{4}$$0$$1$$2$$3$$4$$1$$2$$3$$4$$1$$2$$3$$4$$1$$2$$\frac{10}{3}$
Figure 2: Service rate region for the $G$-system in Example 4.12, with
$\lambda_{2}=\lambda_{3}=0$. Eq. (9) is represented by the green line.

######  Example 4.13.

Consider the finite field $\mathbb{F}_{8}=\mathbb{F}_{2}[\alpha]$, where
$\alpha^{3}+\alpha+1=0$. Let

$G:=\begin{pmatrix}1&\alpha&\alpha^{4}&\alpha&\alpha^{3}\\\
\alpha&\alpha^{3}&\alpha&\alpha^{6}&\alpha^{5}\\\
\alpha^{2}&\alpha&\alpha^{4}&\alpha^{2}&\alpha^{3}\end{pmatrix}\in\mathbb{F}_{8}^{3\times
5}.$

We have $d^{\perp}=2$. Moreover, the dual distances of the codes generated by
$G_{i}$, for $i\in\\{1,2,3\\}$, are all equal to $d^{\perp}$. Further, we have
$\delta_{1}^{1}=3$, $\omega_{1}=1$, $\delta_{1}^{2}=4$, $\delta_{2}^{1}=3$,
$\omega_{2}=2$, $\delta_{2}^{2}=4$, $\delta_{3}^{1}=4$, $\omega_{3}=7$, and
$\delta_{3}^{2}=5$. Thus Thm 4.11 reads, with
$\ell_{i}=\min\\{\lambda_{i},1\\}$ for all $i$,

$\displaystyle
3\lambda_{1}+3\lambda_{3}+4\lambda_{3}-\ell_{1}-2\ell_{2}-7\ell_{3}\leq 5.$

We conclude this section by showing that Theorem 4.11 implies the First Dual
Distance Bound of Theorem 4.6 when $G$ is systematic and $d^{\perp}\geq 3$.

######  Proposition 4.14.

Suppose that $G$ is systematic and that $d^{\perp}\geq 3$. Then for all
$i\in\\{1,\ldots,k\\}$ we have $\delta_{i}^{1}=2$, $\omega_{i}=1$, and
$\delta_{i}^{2}\geq d^{\perp}$.

###### Proof.

We only prove the result for $i=1$; the proof for the other indices is
identical. We denote by $\pi:\mathbb{F}_{q}^{n+1}\to\mathbb{F}_{q}^{n}$ the
projection onto the first $n$ coordinates. That $\delta_{1}^{1}=2$ easily
follows from the definitions, since the $1$st and the $(n+1)$th columns of
$G_{1}$ are equal.

We claim that $(1,0,\ldots,0,-1)\in\mathbb{F}_{q}^{n+1}$ is the only codeword
$x\in\mathscr{C}_{1}^{\perp}$ (up to multiples) with $n+1\in\sigma(x)$ and
Hamming weight 2. Let $x=(1,0,\ldots,0,-1)$ and suppose towards a
contradiction that there exists $y\in\mathscr{C}_{i}^{\perp}$ with
$y_{n+1}=1$, Hamming weight 2, and linearly independent from $x$. Then
$\pi(x+y)\in\mathscr{C}^{\perp}$ is non-zero and has weight at most 2,
contradicting $d^{\perp}\geq 3$. This shows that $\omega_{1}=1$.

It remains to show that $\delta_{1}^{2}\geq d^{\perp}$. Let
$x\in\mathscr{C}_{1}^{\perp}$ be the codeword defined above.

  * •

We start by showing that $\delta_{1}^{2}\geq 3$. Take
$y\in\mathscr{C}^{\perp}$ with $\textnormal{wt}(y)=d^{\perp}\geq 3$. Then
$(y,0)+x\in\mathscr{C}_{i}^{\perp}$ has weight at least $d^{\perp}\geq 3$. Not
all codewords of $\mathscr{C}_{1}^{\perp}$ with $n+1$ in their support have
weight 2. Therefore $\delta_{1}^{2}\geq 3$ by definition of $\delta_{1}^{2}$.

  * •

Let $y\in\mathscr{C}_{1}^{\perp}$ be a codeword with
$\textnormal{wt}(y)=\delta_{1}^{2}$ and $n+1\in\sigma(y)$. By the previous
item, $\textnormal{wt}(y)\geq 3$.

If $1\not\in\sigma(y)$, then $\pi(x+y)\in\mathscr{C}$ is a non-zero codeword
with the same weight as $y$. Therefore $\delta_{i}^{2}=\textnormal{wt}(y)\geq
d^{\perp}$. On the other hand, if $1\in\sigma(y)$ then
$z:=(y_{1}+y_{n+1},y_{2},\ldots,y_{n})\in\mathscr{C}^{\perp}$. Since
$\textnormal{wt}(y)\geq 3$ we have $z\neq 0$. Therefore
$d^{\perp}\leq\textnormal{wt}(z)\leq\textnormal{wt}(y)=\delta_{1}^{2}$. ∎

Observe that when $G$ is systematic and $d^{\perp}=2$, Theorem 4.11 can be
sharper than Theorem 4.6, since it takes into account possibly finer
information.

######  Example 4.15.

Let

$G:=\begin{pmatrix}1&0&0&3&5\\\ 0&1&0&0&1\\\
0&0&1&0&3\end{pmatrix}\in\mathbb{F}_{7}^{3\times 5}.$

The bound of Theorem 4.6 reads $\lambda_{1}+\lambda_{2}+\lambda_{3}\leq 5$,
while the one of Theorem 4.11 reads
$2\lambda_{1}+3\lambda_{2}+3\lambda_{3}-2\sum_{i=1}^{3}\min\\{\lambda_{i},1\\}\leq
5.$ It can be shown that the latter region is strictly contained in the
former.

The example illustrates that the service rate region of a $G$-system depends
on $G$. How invertible operations on $G$ change the region is an open problem.

##  5 Conclusions and Future Work

The service rate region is a new aspect of linear redundancy schemes, which
measures their ability to provide simultaneous data recovery. The problem was
studied in different frameworks. We initiates a study within the classical
coding theory. This approach enabled us to derive some new results and recover
some previously known bounds on the service rate region straightforwardly. A
liner redundancy system is defined by a matrix akin to a code generator
matrix. We believe that coding theory can be instrumental in identifying and
using the matrix’s structural properties to construct polytopes that contain
the service rate region by establishing a series of outer bounds that, when
combined, determine the region.

## References

  * [1] G. Yadgar, O. Kolosov, M. F. Aktas, and E. Soljanin, “Modeling the edge: Peer-to-peer reincarnated,” in _2nd USENIX Workshop on Hot Topics in Edge Computing, HotEdge 2019, Renton, WA, USA, July 9, 2019_ , I. Ahmad and S. Sundararaman, Eds. USENIX Association, 2019.
  * [2] M. Aktas, G. Joshi, S. Kadhe, F. Kazemi, and E. Soljanin, “Service rate region: A new aspect of coded distributed system design,” _IEEE Trans. Inform. The_ , Feb. 2022.
  * [3] F. Kazemi, S. Kurz, and E. Soljanin, “Efficient storage schemes for desired service rate regions,” in _2021 IEEE Information Theory Workshop (ITW)_ , Apr. 2021.
  * [4] ——, “A geometric view of the service rates of codes problem and its application to the service rate of the first order reed-muller code,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , June 2020\.
  * [5] F. Kazemi, E. Karimi, E. Soljanin, and A. Sprintson, “A combinatorial view of the service rates of codes problem, its equivalence to fractional matching and its connection with batch codes,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , June 2020.
  * [6] S. E. Anderson, A. Johnston, G. Joshi, G. L. Matthews, C. Mayer, and E. Soljanin, “Service capacity region of content access from erasure coded storage,” in _IEEE Information Theory Workshop (ITW)_ , Nov. 2018.
  * [7] M. Aktaş, S. E. Anderson, A. Johnston, G. Joshi, S. Kadhe, G. L. Matthews, C. Mayer, and E. Soljanin, “On the service capacity region of accessing erasure coded content,” in _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2017, pp. 17–24.
  * [8] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications,” in _Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004_ , L. Babai, Ed., 2004, pp. 262–271.
  * [9] A. Riet, V. Skachek, and E. K. Thomas, “Asynchronous batch and PIR codes from hypergraphs,” in _IEEE Inform. Theory Workshop, ITW 2018, Guangzhou, China, November 25-29, 2018_. IEEE, 2018, pp. 1–5.
  * [10] V. Skachek, _Batch and PIR Codes and Their Connections to Locally Repairable Codes_. Springer International Publishing, 2018.
  * [11] A. Fazeli, A. Vardy, and E. Yaakobi, “PIR with low storage overhead: Coding instead of replication,” _CoRR_ , vol. abs/1505.06241, 2015. [Online]. Available: http://arxiv.org/abs/1505.06241
  * [12] A. Fazeli, A. Vardy, and E. Yaakobi, “Codes for distributed pir with low storage overhead,” in _2015 IEEE Internat. Symp. on Inform. Theory (ISIT)_ , 2015, pp. 2852–2856.
  * [13] T. Ernvall, T. Westerbäck, and C. Hollanti, “Linear locally repairable codes with random matrices,” _CoRR_ , vol. abs/1408.0180, 2014. [Online]. Available: http://arxiv.org/abs/1408.0180
  * [14] T. Ernvall, T. Westerback, and C. Hollanti, “Constructions of optimal and almost optimal locally repairable codes,” in _Wireless Communications, Vehicular Technology, Information Theory and Aerospace Electronic Systems (VITAE), 2014 4th International Conference on_ , May 2014, pp. 1–5.
  * [15] P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin, “Explicit maximally recoverable codes with locality,” _IEEE Trans. Inform. Th._ , vol. 60, no. 9, pp. 5245–5256, 2014.
  * [16] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” _IEEE Transactions on Information Theory_ , vol. 60, no. 8, pp. 4661–4676, Aug 2014.