DNA, with remarkable properties of high density, durability, and replicability, is one of the most appealing storage media. Emerging DNA storage technologies use composite DNA letters, where information is represented by probability vectors, leading to higher information density and lower synthesizing costs than regular DNA letters. However, it faces the problem of inevitable noise and information corruption. This paper explores the channel of composite DNA letters in DNA-based storage systems and introduces block codes for limited-magnitude probability errors on probability vectors. First, outer and inner bounds for limited-magnitude probability error correction codes are provided. Moreover, code constructions are proposed where the number of errors is bounded by t, the error magnitudes are bounded byl, and the probability resolution is fixed ask. These constructions focus on leveraging the properties of limited-magnitude probability errors in DNA-based storage systems, leading to improved performance in terms of complexity and redundancy. In addition, the asymptotic optimality for one of the proposed constructions is established. Finally, systematic codes based on one of the proposed constructions are presented, which enable efficient information extraction for practical implementation.

Having timely and fresh knowledge about the current status of information sources is critical in a variety of applications, where the status update arrives at the destination later than its generation time due to processing and communication delays. The freshness of the status update at the destination is captured by the notion of the age of information. In this study, we analyze a multiple sensing network with multiple sources, multiple servers, and a monitor (destination). Each source corresponds to an independent piece of information, and its age is individually measured. Given a particular source, the servers independently sense the source of information and send the status update to the monitor. We assume that updates arrive at the servers according to Poisson random processes. Each server sends its updates to the monitor through a direct link, which is modeled as a queue. The service time to transmit an update is considered to be an exponential random variable. We examine both homogeneous and heterogeneous service and arrival rates for the single-source case, and homogeneous arrival and service rates for the multiple-source case. We derive a closed-form expression for the average age of information under a last-come-first-serve (LCFS) queue for a single source and an arbitrary number of homogeneous servers. Using a recursive method, we derive the explicit average age of information for any number of sources and homogeneous servers. We also investigate heterogeneous servers and a single source, and present efficient algorithms for finding the average age of information. Optimal update scheduling strategies are also investigated in several scenarios, providing insights into enhancing the system performance in terms of update freshness.

This paper presents flexible storage codes, a class of error-correcting codes that can recover information from a flexible number of storage nodes. As a result, one can make better use of the available storage nodes in the presence of unpredictable node failures and reduce the data access latency. Assume a storage system encodes$k\ell $information symbols over a finite field$\mathbb {F}$into$n$nodes, each of size$\ell $symbols. The code is parameterized by a set of tuples$\{(R_{j},\ell _{j}): 1 \le j \le a\}$, satisfying$\ell _{1} < \ell _{2} < {\dots } < \ell _{a} = \ell $and$R_{1}>R_{2}> {\dots }>R_{a}$, such that the information symbols can be reconstructed from any$R_{j}$nodes, each node accessing$\ell _{j}$symbols, for any$1 \le j \le a$. In other words, the code allows a flexible number of nodes for decoding to accommodate the variance in the data access time of the nodes. Code constructions are presented for different storage scenarios, including LRC (locally recoverable) codes, PMDS (partial MDS) codes, and MSR (minimum storage regenerating) codes. We analyze the latency of accessing information and perform simulations on Amazon clusters to show the efficiency of the presented codes.

The problem of clock synchronization is studied in an arbitrary network ${\mathcal{G}} = ({\mathcal{V}},{\mathcal{E}})$ with $|{\mathcal{V}}|$ server nodes and $|{\mathcal{E}}|$ edges. Every pair of adjacent servers has a time discrepancy (edge information) that is only known approximately to one or both of the two adjacent servers. A master node aims to coordinate the otherwise independent clocks of the servers by eliminating the loop-wise offset surplus in the network. The goal is to minimize the communication cost between server nodes and the master node. Optimal schemes are found for the two cases where each time discrepancy is known by 1) both adjacent servers, and 2) only one of the adjacent servers. Notably, the scheme for the first case is robust to a straggler (slow or failed server). An algorithm that outperforms the natural (uncoded) baseline is proposed for the general setting that is a mix of the two cases. Classes of such mixed setting are identified where the algorithm represents the optimal solution.

DNA, with remarkable properties of high density and stability, particularly for long-term data archiving, is one of the most appealing storage media. Emerging DNA storage technologies use composite DNA letters, where information is represented by a probability vector, leading to higher information density and lower synthesizing cost than single DNA letters. However, it faces the problem of inevitable noise and information corruption. This paper studies the channel of composite DNA letters in DNA storage and block codes for symmetric limited-magnitude errors on probability vectors. We provide outer and inner bounds for limited-magnitude probability error correction codes. Moreover, we propose code constructions where the number of errors is bounded by t, the error magnitudes are bounded by l, and the probability resolution is fixed as k. Our constructions exploit the properties of the limited-magnitude errors, and improve the performance in terms of complexity and redundancy.

The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. There are up to$N - R$stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication.

The distributed matrix multiplication problem with unknown number of stragglers is considered, where the goal is to allow a master to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across$N$servers. We assume there are at most$N-R$stragglers but the exact number is not known a priori. Motivated by reducing the latency, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing job for each server is separated into 2 layers, constructed based on Entangled Polynomial (EP) codes by Yu el al. The final results can be obtained when a larger number of servers complete the task from the first layer or a smaller number of servers complete the tasks from both 2 layers. The required finite field size of the proposed solution is less than$2N$. Moreover, the optimal partitioning of the input matrices is discussed. Our constructions can also be generalized to batch matrix multiplication.

We consider a status updating system where having timely knowledge about the information source at the destination (monitor) is of utmost importance. By utilizing the age of information (AoI) metric, the freshness of the status update over an erasure channel is investigated. Due to the erasure nature of the update transmission, an error-free feedback channel from the monitor to the source is beneficial for reducing AoI. Each status update contains K packets which can be sent through the channel one at a time. At each channel use, one status update is available from the information source. Depending on how many packets have been received successfully out of the K packets, we need to decide whether to continue sending the current update or terminate it and start sending the newly generated update. In this paper, we find the optimal failure tolerance when the erasure probability (ϵ) is in the regime ϵ→ 0 and also provide a lower and an upper bound for the average AoI for all erasure probabilities. Moreover, for all ϵ, we provide a lower bound for failure tolerance to minimize peak AoI.

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA- NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. Each record contains P symbols, and each symbol takes values uniformly and independently from an alphabet of size K. Considering the large number of records in modern datasets, it is assumed that L is much larger than the alphabet size K. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1 - 1/N, even when the scope of private search is further generalized to allow OR search, AND search, NOT search and sequence search. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages. The asymptotic behavior is also applicable to T-colluding servers or (N, T)-MDS coded servers.

We consider the problem of T-Private Information Retrieval with private side information (TPIR-PSI). In this problem, N replicated databases store K independent messages, and a user, equipped with a local cache that holds M messages as side information, wishes to retrieve one of the other K - M messages. The desired message index and the side information must remain jointly private even if any T of the N databases collude. We show that the capacity of TPIR-PSI is (1+ T/N + ⋯ +(T/N)K-M-1)-1. As a special case obtained by setting T = 1, this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all N databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is 1 - T/N if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least T/N -T bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.

Having timely and fresh knowledge about the current state of information sources is critical in a variety of applications. In particular, a status update may arrive at the destination much later than its generation time due to processing and communication delays. The freshness of the status update at the destination is captured by the notion of age of information. In this study, we first analyze a network with a single source, n servers, and the monitor (destination). The servers independently sense the source of information and send the status update to the monitor. We then extend our result to multiple independent sources of information in the presence of n servers. We assume that updates arrive at the servers according to Poisson random processes. Each server sends its update to the monitor through a direct link, which is modeled as a queue. The service time to transmit an update is considered to be an exponential random variable. We examine both homogeneous and heterogeneous service and arrival rates for the single-source case, and only homogeneous arrival and service rates for the multiple-source case. We derive a closed-form expression for the average age of information under a last-come-first-serve (LCFS) queue for a single source and arbitrary n homogeneous servers. For n = 2, 3, we derive the explicit average age of information for arbitrary sources and homogeneous servers, and for a single source and heterogeneous servers. For n = 2, we find the optimal arrival rates given fixed sum arrival rate and service rates.

Resistive memories are considered a promising memory technology enabling high storage densities. However, the readout reliability of resistive memories is impaired due to the inevitable existence of wire resistance, resulting in the sneak path problem. Motivated by this problem, we study polar coding over channels with different reliability levels, termed non-stationary polar codes, and we propose a technique improving the bit error rate (BER) performance. We then apply the framework of non-stationary polar codes to the crossbar array and evaluate its BER performance under two modeling approaches, namely binary symmetric channels and binary asymmetric channels. Finally, we propose a technique for biasing the proportion of high-resistance states in the crossbar array and show its advantage in reducing further the BER. Several simulations are carried out using a SPICE-like simulator, exhibiting significant reduction in BER.

DNA becomes an attractive storage medium in recent years for its ultra-high density, millennial-long endurance, and efficient replication. In this work we consider DNA storage that uses the affordable and portable nanopore sequencing as the reading mechanics. Unlike traditional data storage systems, errors occur asymmetrically among the four types of nucleotide bases of DNA. Quaternary codes can be employed for error correction, but suffer from high complexity. In this paper, we design binary LDPC codes with a turbo-like decoder for the DNA storage channel. Simulation results show that our binary LDPC codes have a similar bit-error rate but with a speed up by a factor of 4 compared to quaternary codes.

Minimizing the repair bandwidth, i.e., the amount of information from the helper nodes needed for recovering the content of one failed node in an erasure-coded distributed storage system, has been the focus of many works in the literature. We investigate another important performance metric, namely the I/O cost, which specifies the amount of information that needs to be read by the helper nodes during the repair process of one failed node. We analyze the I/O costs of a few known repair schemes for Reed-Solomon codes of various lengths, in contrast to the previous works in this direction, which only studied the I/O costs in repairing full-length Reed-Solomon codes.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.

Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field GF(qI) evaluated at a set of points, where I is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller I facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packetization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye, and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this paper, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures.

In a distributed storage system, recovering from multiple failures is a critical and frequent task that is crucial for maintaining the system's reliability and fault-tolerance. In this paper, we focus on the problem of repairing multiple failures in a centralized way, which can be desirable in many data storage configurations; furthermore, we show that a significant repair traffic reduction is possible. First, the fundamental trade-off between the repair bandwidth and the storage size for functional repair is established. Using a graph-theoretic formulation, the optimal tradeoff is identified as the solution to an integer optimization problem, for which a closed-form expression is derived. Expressions of the extreme points, namely the minimum storage multi-node repair (MSMR) and minimum bandwidth multinode repair (MBMR) points, are obtained. Second, we describe a general framework for converting single erasure minimum storage regenerating codes to MSMR codes. The repair strategy for e failures is similar to that for a single failure; however, certain extra requirements need to be satisfied by the repairing functions for a single failure. For illustration, the framework is applied to product-matrix codes and interference alignment codes. Furthermore, we prove that the functional MBMR point is not achievable for linear exact-repair codes. We also show that the exact-repair minimum bandwidth cooperative repair codes achieve an interior point, that lies near the MBMR point, when k ≡ 1 mod e, k being the minimum number of nodes needed to reconstruct the entire data. Finally, for k > 2e, e | k, and e | d, where d is the number of helper nodes during repair, we show that the functional repair trade-off is not achievable under exact repair, except for maybe a small portion near the MSMR point, which parallels the results for single-erasure repair by Shah et al.

The private search problem is introduced, where a dataset comprised of L i.i.d. records is replicated across N non-colluding servers, each record takes values uniformly from an alphabet of size K, and a user wishes to search for all records that match a privately chosen value, without revealing any information about the chosen value to any individual server. The capacity of private search is the maximum number of bits of desired information that can be retrieved per bit of download. The asymptotic (large K) capacity of private search is shown to be 1-1/N, even as the scope of private search is further generalized to allow approximate (OR) search over a number of realizations that grows with K. The results are based on the asymptotic behavior of a new converse bound for private information retrieval with arbitrarily dependent messages.

Motivated by mobile edge computing and wireless data centers, we study a wireless distributed computing framework where the distributed nodes exchange information over a wireless interference network. Our framework follows the structure of MapReduce. This framework consists of Map, Shuffle, and Reduce phases, where Map and Reduce are computation phases and Shuffle is a data transmission phase. In our setting, we assume that the transmission is operated over a wireless interference network. We demonstrate that, by duplicating the computation work at a cluster of distributed nodes in the Map phase, one can reduce the amount of transmission load required for the Shuffle phase. In this work, we characterize the fundamental tradeoff between computation load and communication load, under the assumption of one-shot linear schemes. The proposed scheme is based on side information cancellation and zero-forcing, and we prove that it is optimal in terms of computation-communication tradeoff. The proposed scheme outperforms the naive TDMA scheme with single node transmission at a time, as well as the coded TDMA scheme that allows coding across data, in terms of the computation-communication tradeoff.

We study the problem of centralized exact repair of multiple failures in distributed storage. We describe constructions that achieve a new set of interior points under exact repair. The constructions build upon the layered code construction by Tian et al in [1], designed for exact repair of single failure. We firstly improve upon the layered construction for general system parameters. Then, we extend the improved construction to support adaptive repair for a flexible number of failures, and a flexible number of helpers. In particular, we prove the optimality of one point on the functional repair tradeoff of multiple failures for some parameters. Finally, considering minimum bandwidth cooperative repair (MBCR) codes as centralized repair codes, we determine explicitly the best achievable region obtained by space-sharing among all known points, including the MBCR point.

Motivation: Chromatin immunoprecipitation sequencing (ChIP-seq) experiments are inexpensive and time-efficient, and result in massive datasets that introduce significant storage and maintenance challenges. To address the resulting Big Data problems, we propose a lossless and lossy compression framework specifically designed for ChIP-seq Wig data, termed ChIPWig. ChIPWig enables random access, summary statistics lookups and it is based on the asymptotic theory of optimal point density design for nonuniform quantizers. Results: We tested the ChIPWig compressor on 10 ChIP-seq datasets generated by the ENCODE consortium. On average, lossless ChIPWig reduced the file sizes to merely 6% of the original, and offered 6-fold compression rate improvement compared to bigWig. The lossy feature further reduced file sizes 2-fold compared to the lossless mode, with little or no effects on peak calling and motif discovery using specialized NarrowPeaks methods. The compression and decompression speed rates are of the order of 0.2 sec/MB using general purpose computers. Availability and implementation: The source code and binaries are freely available for download at https://github.com/vidarmehr/ChIPWig-v2, implemented in C ++. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

In applications of distributed storage systems to distributed computing and implementation of key-value stores, the following property, usually referred to as consistency in distributed computing, is an important requirement: as the data stored changes, the latest version of the data must be accessible to a client that connects to the storage system. Motivated by technological trends where key-value stores are increasingly implemented in high-speed memory, an information theoretic formulation called multi-version coding is introduced in this paper in order to understand and minimize the memory overhead of consistent distributed storage. Multi-version coding is characterized by ν totally ordered versions of a message and a storage system with n servers. At each server, values corresponding to an arbitrary subset of the ν versions are received and encoded. For any subset of c servers in the storage system, the value corresponding to the latest common version or a later version, as per the total ordering, among the c servers is required to be decodable. An achievable multi-version code construction via linear coding and a converse result that shows that the construction is asymptotically tight when ν|(c - 1) are provided. An implication of the converse is that there is an inevitable price, in terms of storage cost, to ensure consistency in distributed storage systems.

Low-density parity-check (LDPC) codes are known for superior performance over a wide range of codes for communication and memory systems. In many practical scenarios, adaptive ECC system is preferred that can adapt to various codes with varying channel conditions since the behavior of errors changes with time and space. This paper presents two architectural designs for efficient encoding of LDPC codes to support different code rates and lengths, which can be used for several applications. The proposed designs allow switching among different codes without any hardware modification. The first proposed design achieves extremely high throughput by removing the memory from the encoder, while still being able to adapt to a few predefined codes. The other architecture can adapt to any arbitrary code by using the memory for configuration, and yet, it achieves up to 12.9x throughput and 17.5x area improvement as compared to fully-reconfigurable encoders proposed in literature.

In distributed storage, erasure codes are widely used to provide data reliability, where every codeword symbol corresponds to one storage node. The network traffic cost during the repair of node failures, called repair bandwidth, is an important metric in code design. In particular, minimum storage regenerating (MSR) codes are maximum distance separable (MDS) codes that have optimal repair bandwidth. In this paper, we generalize the problem to minimum storage multi-node regenerating (MSMR) codes, which are MDS codes with optimal repair bandwidth for e node failures. We describe a general framework for converting MSR codes to MSMR codes. The repair strategy for e failures is similar to that for single failure, however certain extra requirements need to be satisfied by the repairing functions for single failure. Then we apply this framework to product-matrix codes and interference alignment codes.

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols.

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e <; r. Hence, a natural question is how much information do we need to access in order to rebuild e storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of e erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of 1/r for the rebuilding of any systematic node when e = 1; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any r erasures can be corrected by accessing some of the remaining information, and any e = 1 erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of e/r for systematic nodes of MDS codes, for any 1 ≤ e r; 2) we construct systematic codes that achieve optimal rebuilding ratio of 1/r, for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.

The focus of this paper is to understand storage costs of emulating an atomic shared memory over an asynchronous, distributed message passing system. Previous literature has developed several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this paper, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory emulation algorithms. Our storage cost lower bounds are universally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data.

CONTRIBUTIONS: We developed a new lossless compression method for WIG data, named smallWig, offering the best known compression rates for RNA-seq data and featuring random access functionalities that enable visualization, summary statistics analysis and fast queries from the compressed files. Our approach results in order of magnitude improvements compared with bigWig and ensures compression rates only a fraction of those produced by cWig. The key features of the smallWig algorithm are statistical data analysis and a combination of source coding methods that ensure high flexibility and make the algorithm suitable for different applications. Furthermore, for general-purpose file compression, the compression rate of smallWig approaches the empirical entropy of the tested WIG data. For compression with random query features, smallWig uses a simple block-based compression scheme that introduces only a minor overhead in the compression rate. For archival or storage space-sensitive applications, the method relies on context mixing techniques that lead to further improvements of the compression rate. Implementations of smallWig can be executed in parallel on different sets of chromosomes using multiple processors, thereby enabling desirable scaling for future transcriptome Big Data platforms. MOTIVATION: The development of next-generation sequencing technologies has led to a dramatic decrease in the cost of DNA/RNA sequencing and expression profiling. RNA-seq has emerged as an important and inexpensive technology that provides information about whole transcriptomes of various species and organisms, as well as different organs and cellular communities. The vast volume of data generated by RNA-seq experiments has significantly increased data storage costs and communication bandwidth requirements. Current compression tools for RNA-seq data such as bigWig and cWig either use general-purpose compressors (gzip) or suboptimal compression schemes that leave significant room for improvement. To substantiate this claim, we performed a statistical analysis of expression data in different transform domains and developed accompanying entropy coding methods that bridge the gap between theoretical and practical WIG file compression rates. RESULTS: We tested different variants of the smallWig compression algorithm on a number of integer-and real- (floating point) valued RNA-seq WIG files generated by the ENCODE project. The results reveal that, on average, smallWig offers 18-fold compression rate improvements, up to 2.5-fold compression time improvements, and 1.5-fold decompression time improvements when compared with bigWig. On the tested files, the memory usage of the algorithm never exceeded 90 KB. When more elaborate context mixing compressors were used within smallWig, the obtained compression rates were as much as 23 times better than those of bigWig. For smallWig used in the random query mode, which also supports retrieval of the summary statistics, an overhead in the compression rate of roughly 3-17% was introduced depending on the chosen system parameters. An increase in encoding and decoding time of 30% and 55% represents an additional performance loss caused by enabling random data access. We also implemented smallWig using multi-processor programming. This parallelization feature decreases the encoding delay 2-3.4 times compared with that of a single-processor implementation, with the number of processors used ranging from 2 to 8; in the same parameter regime, the decoding delay decreased 2-5.2 times. AVAILABILITY AND IMPLEMENTATION: The smallWig software can be downloaded from: http://stanford.edu/~zhiyingw/smallWig/smallwig.html, http://publish.illinois.edu/milenkovic/, http://web.stanford.edu/~tsachy/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In distributed storage, a file is stored in a set of nodes and protected by erasure-correcting codes. Regenerating code is a type of code with two properties: first, it can reconstruct the entire file in the presence of any r node erasures for some specified integer r; second, it can efficiently repair an erased node from any subset of remaining nodes with a given size. In the repair process, the amount of information transmitted from each node normalized by the storage size per node is termed repair bandwidth (fraction). When the storage size per node is minimized, the repair bandwidth is lower bounded by 1/r, where r is the number of parity nodes. A code attaining this lower bound is said to have optimal repair. We consider codes with minimum storage size per node and optimal repair, called minimum storage regenerating (MSR) codes. In particular, if an MSR code has r parities and any r erasures occur, then by transmitting all the information from the remaining nodes, the original file can be reconstructed. On the other hand, if only one erasure occurs, only a fraction of 1/r of the information in each remaining node needs to be transmitted. If we view each node as a vector or a column over some field, then the code forms a 2-D array. Given the length of the column l and the number of parities r, we explicitly construct the high-rate MSR codes. The number of systematic nodes of our construction is (r + 1) logrl, which is longer than previously known results. Besides, we construct the MSR codes with other desirable properties: first, the codes with low complexity when the information is updated, and second, the codes with low access or storage node I/O cost during repair.

In this paper, we study a construction of binary switch codes. A switch code is a code such that a multi-set request of information symbols can be simultaneously recovered from disjoint sets of codeword symbols. Our construction is optimal in the sense that it has the smallest codeword length given its average encoding degree, which is logarithmic in the code dimension. Moreover, the number of queries needed to recover any information symbol in the request is at most 2. As a result, our construction is the first family of switch codes with low encoding and decoding complexity.

We investigate an information theoretic problem motivated by storing multiple versions of a data object in distributed storage systems. Specifically, in a storage system with n server nodes, where there are ν independent message versions, each server receives message values corresponding to some arbitrary subset of the versions. The versions are assumed to be totally ordered. Each server is unaware of the set of versions at the other servers, and aims to encode the values corresponding to the versions it has. We investigate codes where, from any set of c nodes (c < n), the value corresponding to the highest common version, as per the version ordering, available at this set of c nodes is decodable. We aim to design codes that minimize the storage cost. We present two main results in this paper. First, we show that the storage cost is lower bounded by 1− (1− 1 c ) , measured in terms of the bits of the values. Second, for the cases of ν = 2 and ν = 3, we provide new code constructions that respectively achieve storage costs of 2c−1 c and 3c−2 c , measured in terms of the bits of the values. Our code constructions are simple in that we do not code across versions. We argue that when the number of versions ν is much larger than c, then replication is close to optimal.

Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. A node is said to have capacitylover some field F, if it can store that amount of symbols of the field. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to anyn-knode failures. An optimal bandwidth (respectively, optimal access) MDS code communicates (respectively, accesses) the minimum amount of data during the repair process of a single failed node. It was shown that this amount equals a fraction of 1/(n - k) of data stored in each node. In previous optimal bandwidth constructions,lscaled polynomially with k in codes when the asymptotic rate is less than 1. Moreover, in constructions with a constant number of parities, i.e., when the rate approaches 1,lis scaled exponentially withk. In this paper, we focus on the case of linear codes with linear repair operations and constant number of paritiesn-k=r, and ask the following question: given the capacity of a node l what is the largest number of information disks k in an optimal bandwidth (respectively, access) (k+r, k, l) MDS code? We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes. The first is a family of codes with optimal update property, and the second is a family with optimal access property. Moreover, the bounds show that in some cases optimal-bandwidth codes have largerkthan optimal-access codes, and therefore these two measures are not equivalent.

A network switch routes data packets between its multiple input and output ports. Packets from input ports are stored upon arrival in a switch fabric comprising multiple memory banks. This can result in memory contention when distinct output ports request packets from the same memory bank, resulting in a degraded switching bandwidth. To solve this problem, we propose to add redundant memory banks for storing the incoming packets. The problem we address is how to minimize the number of redundant memory banks given some guaranteed contention resolution capability. We present constructions of new switch memory architectures based on different coding techniques. The codes allow decreasing the redundancy by 1/2 or 2/3, depending on the request specifications, compared to non-coding solutions.

Maximum distance separable (MDS) array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct, then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between${{1} \over {2}}$and${{3} \over {4}}$; however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a two-erasure correcting code, the rebuilding ratio is${{1} \over {2}}$. In general, we construct a new family of$r$-erasure correcting MDS array codes that has optimal rebuilding ratio of${{1} \over {r}}$in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the cases$r=2$and$r=3$, they use a finite field of size 3 and 4, respectively) and an optimal update property.

Maximum distance separable (MDS) codes are widely used in storage systems to protect against disks (nodes) failures. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to any n - k node failures. An optimal bandwidth (resp. optimal access) MDS code communicates (resp. accesses) the minimum amount of data during the recovery process of a single failed node. It was shown that this amount equals a fraction of 1/(n - k) of data stored in each node. In previous optimal bandwidth constructions, l scaled polynomially with k in codes with asymptotic rate <; 1. Moreover, in constructions with constant number of parities, i.e. rate approaches 1, l scaled exponentially w.r.t. k. In this paper we focus on the practical case of n - k = 2, and ask the following question: Given the capacity of a node l what is the largest (w.r.t. k) optimal bandwidth (resp. access) (k + 2, k, l) MDS code. We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes.

MDS codes are erasure-correcting codes that can correct the maximum number of erasures given the number of redundancy or parity symbols. If an MDS code has r parities and no more than r erasures occur, then by transmitting all the remaining data in the code one can recover the original information. However, it was shown that in order to recover a single symbol erasure, only a fraction of 1/r of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we ask the following question: given the length of the column l, can we construct high-rate MDS array codes with optimal repair bandwidth of 1/r, whose code length is as long as possible? In this paper, we give code constructions such that the code length is (r + l)logrl.

Phase-change memory (PCM) is an emerging nonvolatile memory technology that promises very high performance. It currently uses discrete cell levels to represent data, controlled by a single amorphous/crystalline domain in a cell. To improve data density, more levels per cell are needed. There exist a number of challenges, including cell programming noise, drifting of cell levels, and the high power requirement for cell programming. In this paper, we present a new cell structure called patterned cell, and explore its data representation schemes. Multiple domains per cell are used, and their connectivity is used to store data. We analyze its storage capacity, and study its error-correction capability and the construction of error-control codes.

MDS array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting (and more practical) case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of r-erasure correcting MDS array codes that has optimal rebuilding ratio of 1/r in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the case r = 2 they use a finite field of size 3) and an optimal update property.

Rank modulation was recently proposed as an information representation for multilevel flash memories, using permutations or ranks of n flash cells. The current decoding process finds the cell with the i-th highest charge level at iteration i, for i = 1, 2, ..., n-1. Motivated by the need to reduce the number of such iterations, we consider k-partial permutations, where only the highest k cell levels are considered for information representation. We propose a generalization of Gray codes for k-partial permutations such that information is updated efficiently.

Rank modulation has been introduced as a new information representation scheme for flash memories. Given the charge levels of a group of flash cells, sorting is used to induce a permutation, which in turn represents data. Motivated by the lower sorting complexity of smaller cell groups, we consider bounded rank modulation, where a sequence of permutations of given sizes are used to represent data. We study the capacity of bounded rank modulation under the condition that permutations can overlap for higher capacity.