Data deduplication refers to a collection of data processing strategies that aim to remove repeated data chunks stored by different users. Despite providing excellent storage savings, deduplication can lead to severe file fragmentation issues: data chunks of the same file may be stored at distal locations on the server, making reconstruction time-consuming. Here, we continue our analytical study of uncoded and coded deduplication methods with reduced fragmentation levels. We model files as self-avoiding (simple) paths in specialized graphs whose nodes correspond to data chunks. To measure the level of fragmentation, we introduce the jump metric which captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. We derive lower and upper bounds on the degree of jump fragmentation, and provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. We also present examples that show how repetition and coded redundancy in chunk stores can reduce jump fragmentation.

Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view. Storage robustness pertains to ensuring that deduplicated data can be used to reconstruct the original files without service disruptions and data loss. Fragmentation pertains to the problems of placing deduplicated data chunks of different user files in a proximity-preserving linear order, since neighboring chunks of the same file may be stored in sectors far apart on the server. This work proposes a new theoretical model for data fragmentation and introduces novel graph- and coding-theoretic approaches for reducing fragmentation via limited duplication (repetition coding) and coded deduplication (e.g., linear coding). In addition to alleviating issues with fragmentation, limited duplication and coded deduplication can also serve the dual purpose of increasing the robusteness of the system design. The contributions of our work are three-fold. First, we describe a new model for file structures of the form of self-avoiding (simple) paths in specialized graphs. Second, we introduce several new metrics for measuring the fragmentation level in deduplication systems on graph-structured files, including thestretch metricthat captures the worst-case “spread” of adjacent data chunks within a file when deduplicated and placed on the server; and, thejump metricthat captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. For the stretch metric, we establish a connection between the level of fragmentation and thebandwidthof the file-graph. In particular, we derive lower and upper bounds on the degree of fragmentation and describe instances of the problem where repetition and coding reduce fragmentation. The key ideas behind our approach are graph folding and information-theoretic arguments coupled with graph algorithms such as matching. For the jump metric, we provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. Third, we describe how controlled repetition and coded redundancy added after deduplication can ensure valuable trade-offs between the storage volume and the degree of fragmentation.

Motivated by testing for pathogenic diseases we consider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst with classical group testing [1] to the setting of semiquantitative group testing (SQGT) [2]. Specifically, we study the setting where the burst-length ℓ is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η1,…, ηs. Interestingly, we show that the minimum number of tests needed for burst identification is essentially only a function of the largest threshold ηs. In this context, our main result is an order-optimal test scheme that can recover any burst of length ℓ using roughly $\left\lfloor {\frac{\ell }{{2{\eta _s}}}} \right\rfloor + {\log _{s + 1}}(n)$ measurements. This suggests that a large saturation level ηsis more important than finely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.

Motivated by applications in polymer-based data storage we introduced the new problem of characterizing the code rate and designing constant-weight binary B2-sequences. Binary B2-sequences are collections of binary strings of length nwith the property that the real-valued sums of all distinct pairs of strings are distinct. In addition to this defining property, constant-weight binary B2-sequences also satisfy the constraint that each string has a fixed, relatively small weight ωthat scales linearly with n. The constant-weight constraint ensures low-cost synthesis and uniform processing of the data readout via tandem mass spectrometers. Our main results include upper bounds on the size of the codes formulated as entropy-optimization problems and constructive lower bounds based on Sidon sequences.

In this work, combinatorial quantitative group testing (QGT) with noisy measurements is studied. The goal of QGT is to detect defective items from a data set of size n with counting measurements, each of which counts the number of defects in a selected pool of items. While most literatures consider either probabilistic QGT with random noise or combinatorial QGT with noiseless measurements, our focus is on the combinatorial QGT with noisy measurements that might be adversarially perturbed by additive bounded noises. Since perfect detection is impossible, a partial detection criterion is adopted. With the adversarial noise being bounded by dn= Θ(nδ) and the detection criterion being to ensure no more than kn= Θ(nκ) errors can be made, our goal is to characterize the fundamental limit on the number of measurement, termed pooling complexity, as well as provide explicit construction of measurement plans with optimal pooling complexity and efficient decoding algorithms. We first show that the fundamental limit is $\frac{1}{{1 - 2\delta }}\frac{n}{{\log n}}$ to within a constant factor not depending on (n, κ, δ) for the non-adaptive setting when 0 < 2δ ≤ κ < 1, sharpening the previous result by Chen and Wang [1]. We also provide deterministic constructions of an adaptive method with $\frac{1}{{1 - 2\delta }}\frac{n}{{{{\log }_2}n}}$ pooling complexity up to a constant factor and O(n) decoding complexity.