extfieldsofstudy:
Computer Science
Mathematics

text:
Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems

Modern distributed storage systems apply redundancy coding techniques to stored data. One form of redundancy is based on regenerating codes, which can minimize the repair bandwidth, i.e., the amount of data transferred when repairing a failed storage node. Existing regenerating codes mainly require surviving storage nodes encode data during repair. In this paper, we study functional minimum storage regenerating (FMSR) codes, which enable uncoded repair without the encoding requirement in surviving nodes, while preserving the minimum repair bandwidth guarantees and also minimizing disk reads. Under double-fault tolerance settings, we formally prove the existence of FMSR codes, and provide a deterministic FMSR code construction that can significantly speed up the repair process. We further implement and evaluate our deterministic FMSR codes to show the benefits. Our work is built atop a practical cloud storage system that implements FMSR codes, and we provide theoretical validation to justify the practicality of FMSR codes.

I. INTRODUCTION
We have witnessed the wide deployment of storage systems in Internet-wide distributed settings, such as peer-to-peer storage (e.g., [14], [2], [5], [27]) and cloud storage (e.g., GFS [8] and Azure [4]), in which data is striped over multiple storage nodes in a networked environment. For data availability, a storage system must keep user data for a long period of time and allow users to access their data on demand. However, storage nodes are often deployed in commodity machines and prone to failures [8]. It is thus important for a storage system to ensure data availability in practical deployment.
One way to ensure data availability is to store redundant data over multiple storage nodes. Redundancy can be achieved via maximum distance separable (MDS) codes such as Reed-Solomon codes [18], whose idea is that even if any subset of nodes fail, the original data remains accessible from the remaining surviving nodes. In general, Reed-Solomon codes have significantly less redundancy overhead than simple replication of data under the same fault tolerance requirement.
When a storage node fails, it is necessary to recover the lost data of the failed node to preserve the required level of fault tolerance. Regenerating codes [7] have been proposed to minimize the repair bandwidth, which defines the amount of data traffic transferred in the repair process. Regenerating codes are built on network coding [1], such that to repair a failed node, existing surviving nodes encode their own stored data and send the encoded data to the new node, which then reconstructs the lost data. It is shown that regenerating codes use less repair bandwidth than Reed-Solomon codes, given the same storage overhead and fault tolerance requirements.
However, there are challenges of deploying regenerating codes in practice. First, most regenerating code constructions (e.g., [29], [6], [3], [23], [17], [21]) require storage nodes to encode stored data during repair. This may not be feasible for some storage devices that merely provide the basic I/O functionalities without any encoding capabilities. More importantly, even if storage nodes have encoding capabilities, they must first read all available data from disk and combine the data into encoded form before transmitting encoded data for repair. This leads to high disk reads, which may degrade the actual repair performance.
On the applied side, a cloud storage system NCCloud [10] proposes and implements functional minimum storage regenerating (FMSR) codes, which have several key properties: (i) FMSR codes preserve the fault tolerance of MDS codes and have the same redundancy overhead as MDS codes for a given fault tolerance; (ii) FMSR codes preserve the benefits of network coding as they minimize the repair bandwidth (e.g., the repair bandwidth saving compared to RAID-6 codes is up to 50% [10]); and (iii) FMSR codes use uncoded repair without requiring encoding of surviving nodes during repair, and this can minimize disk reads as the amount of data read from disk is the same as that being transferred. FMSR codes are designed as non-systematic codes as they do not keep the original uncoded data as their systematic counterparts, but instead store only linear combinations of original data called parity chunks. Each round of repair regenerates new parity chunks for the new node and ensures that the fault tolerance level is maintained. A trade-off of FMSR codes is that the whole encoded file must be decoded first if parts of a file are accessed. Nevertheless, FMSR codes are suited to long-term archival applications, since data backups are rarely read and it is common to restore the whole file rather than file parts.
While FMSR codes have been experimented on real-life cloud testbeds, there remain open issues regarding whether FMSR codes exist and how they are deterministically constructed. In particular, given that new parity chunks are regenerated in each round of repair, we need to ensure that such chunks preserve the fault tolerance of MDS codes after multiple rounds of repair. Thus, the key motivation of this work is to provide theoretical foundations for the practicality of FMSR codes.
In this paper, we conduct formal analysis on the existence of FMSR codes and provide a deterministic construction for FMSR codes, with an objective of theoretically validating the practicality of FMSR codes in distributed storage systems. We focus on the double-fault tolerance setting (i.e., at most two node failures can be tolerated) as in conventional RAID-6 codes [12]. Note that double-fault tolerance is by default used in practical cloud storage systems such as GFS [8] and Azure [4]. Our contributions are three-fold.
• We formally prove the existence of FMSR codes with uncoded repair, such that the fault tolerance of MDS codes is preserved after any number of rounds of repair. • We provide a deterministic FMSR code construction, such that the repair can deterministically specify (i) the chunks to be read from surviving nodes and (ii) the encoding coefficients used to regenerate new chunks. This significantly speeds up the repair time compared to the random FMSR code construction used in NCCloud [10]. • We build and evaluate our deterministic FMSR codes, and show that the chunk selection and regeneration during repair can be finished within less than one second. The rest of the paper proceeds as follows. Section II reviews related work. Section III characterizes the system model of FMSR codes and formulates the problems. Section IV formally proves the existence of FMSR codes. Section V provides a deterministic FMSR code construction. Section VI presents evaluation results. Section VII concludes the paper.

II. BACKGROUND AND RELATED WORK
Dimakis et al. [7] first propose regenerating codes based on network coding [1] for distributed storage systems. It is shown that when repairing a single failed storage node, regenerating codes use less repair bandwidth than conventional Reed-Solomon codes [18] by transmitting encoded data from the surviving nodes to a new node. Also, [7] gives an optimal tradeoff spectrum between storage cost and repair bandwidth and identifies two extreme points. One extreme point refers to the minimum storage regenerating (MSR) codes, in which each node stores the minimum amount of data as in Reed-Solomon codes. Another extreme point is the minimum bandwidth regenerating (MBR) codes, which allow each node to store more data than in conventional Reed-Solomon codes to minimize the repair bandwidth. In this work, we focus on the MSR codes, so that we can fairly compare with conventional Reed-Solomon codes under the same storage overhead.
As shown in [7], [28], [11], the MSR point is achievable under functional-repair, which means that the repaired data may not be the same as the lost data while still maintaining the same fault tolerance level. However, the corresponding coding schemes perform random linear coding in surviving nodes and do not provide explicit construction. Then there are extensive studies (e.g., [29], [6], [3], [23], [17], [21]) on the exactrepair MSR (EMSR) codes, in which the data reconstructed is identical to the lost data.
Most EMSR codes require storage nodes encode stored data during repair. Authors in [19], [20] propose regenerating codes that eliminate encoding of storage nodes during repair. We call it uncoded repair [19], or repair-by-transfer [20]. However, their constructions belong to MBR codes. EMSR code constructions based on uncoded repair have been proposed in [24], [26]. The EMSR code in [24] has the uncoded repair property for systematic nodes that store original data chunks but not for the parity nodes that store encoded chunks, while that in [26] has the uncoded repair property for both systematic and parity nodes. However, the code construction in [26] requires the total number of data chunks being stored increase exponentially with the number of systematic nodes. This increases the number of chunk accesses, and limits its application in practical storage systems.
Several studies (e.g., [25], [30], [13]) propose uncoded repair schemes that minimize disk reads for XOR-based erasure codes. Their solutions are built on existing code constructions. In general, they do not achieve the global minimum point.
A recent applied work [10] builds a network-coding-based cloud storage system called NCCloud. The authors build and evaluate functional MSR (FMSR) codes, which minimize the repair bandwidth using uncoded repair. Later in [22], the correctness of FMSR codes is analyzed for a special case of two systematic nodes. In this paper, we generalize the analysis, and also provide a deterministic code construction, for more systematic nodes.

A. Basics of FMSR Codes
We first describe the basics of FMSR codes, which are used by NCCloud [10] to store files over multiple independent storage nodes. Each node could be a disk device, a storage server, or a cloud storage provider. NCCloud motivates using FMSR codes to provide fault-tolerant, long-term archival storage using multiple clouds, so as to save the monetary cost in migrating data between cloud providers during repair. FMSR codes have three design properties, which we elaborate below.
Property 1: FMSR codes preserve the fault tolerance and storage efficiency of MDS codes. MDS codes are defined by two parameters n and k (k < n). An (n, k)-MDS code divides a file of size M into k pieces of size M/k each, and encodes them into n pieces such that any k out of n encoded pieces suffice to recover the original file. By storing the n encoded pieces over n nodes, a storage system can tolerate at most n − k node failures. An example of MDS codes is Reed-Solomon codes [18]. Figure 1 shows the FMSR codes for a special case n = 4 and k = 2. To store a file of size M units, an (n, k)-FMSR code splits the file evenly into k(n − k) native chunks, say F 1 , F 2 , . . . , F k(n−k) , and encodes them into n(n − k) parity chunks of size M k(n−k) each. Each l th parity chunk is formed by a linear combination of the k(n − k) native chunks, i.e., k(n−k) m=1 α l,m F m for some encoding coefficients α l,m . All encoding coefficients and arithmetic are operated over a finite field F q of size q. We store the n(n − k) parity chunks on n nodes, each keeping n − k parity chunks. Note that native chunks need not be stored. The original file can be restored by decoding k(n − k) parity chunks of any k nodes, where decoding can be done by inverting an encoding matrix [16]. Let P i,j be the j th parity chunk stored on node i, where i = 1, 2, . . . , n and j = 1, . . . , n − k. Property 2: FMSR codes minimize the repair bandwidth. If a node fails, we must reconstruct the lost data of the failed node to preserve fault tolerance. The conventional repair of Reed-Solomon codes reads k pieces from any k surviving nodes to restore the original file (by the design of MDS codes). Clearly, the amount of data read is the file size M . FMSR codes seek to read less than M units of data to reconstruct the lost data. We define repair bandwidth as the amount of data read from surviving nodes during repair. FMSR codes are designed to match the minimum storage point of regenerating codes when repairing a node failure [7], while having each node store M/k units of data as in Reed-Solomon codes. To repair a failed node in FMSR codes, each surviving node transfers data of size M k(n−k) units as in [7], or equivalently, a size of one parity chunk. In a special case of n = 4 and k = 2 (see Figure 1), the repair bandwidth is 0.75M , i.e., 25% less than that of conventional repair of Reed-Solomon codes. In general, the repair bandwidth of FMSR codes for k = n − 2 is M(n−1) 2(n−2) , and its saving compared to RAID-6 codes [12] (which are also double-fault tolerant) is up to 50% if n is large [10].
Property 3: FMSR codes use uncoded repair. During repair, each surviving node under FMSR codes transfers one parity chunk, without any encoding operations. This also minimizes the amount of data read from disk. Suppose we have a failed node l (e.g., l = 1 in Figure 1). Then we read one parity chunk denoted by P i,f (i) from each surviving node i, where 1 ≤ i ≤ n and i = l, and f (.) denotes some function that specifies which chunk to be read from a surviving node. Then we encode the n − 1 parity chunks into n − k linearly independent parity chunks P ′ l,1 , P ′ l,2 , . . . P ′ l,n−k , which will all be stored in a new node, which becomes the new node l (called the repaired node). Each new parity chunk is generated by: where γ i,j denotes some coefficient for encoding the collected parity chunks into new chunks. In Section V, we formally specify how we choose f (.) and γ i,j .

B. Formulation of Repair Problem in FMSR Codes
We formulate the repair problem in FMSR codes based on [10]. Note that [10] only gives a high-level description, without formal definitions and theoretical validations. Here, we provide a theoretical framework that formalizes the idea of [10].
FMSR codes satisfy the MDS property, as described below. Definition 1: MDS property. For any subset of k out of n nodes, if the k(n − k) parity chunks from the k nodes can be decoded to the k(n − k) native chunks of the original file, then the MDS property is satisfied.
Definition 2: Decodability. We say that a collection of k(n−k) parity chunks is decodable if the parity chunks can be decoded to the original file, which can be verified by checking if the associated k(n − k) vectors of encoding coefficients are linearly independent. Note that these k(n − k) chunks may be scattered among n nodes, and need not reside in k nodes.
Note that FMSR codes operate on parity chunks. For simplicity, when we use the term "chunk" in our discussion, we actually refer to a parity chunk.
Since FMSR codes regenerate different chunks in each repair, one design challenge of FMSR codes is to preserve the MDS property after multiple rounds of repairs. We illustrate with an example in Figure 1. Suppose that node 1 fails, and we construct new chunks P ′ 1,1 and P ′ 1,2 using P 2,1 , P 3,1 , and P 4,1 as in Figure 1. Next, suppose that node 2 fails. If we construct new chunks P ′ 2,1 and P ′ 2,2 using P ′ 1,1 , P 3,1 , and P 4,1 , then in the repaired nodes 1 and 2, the chunks {P ′ 1,1 , P ′ 1,2 , P ′ 2,1 , P ′ 2,2 } are the linear combinations of only three chunks P 2,1 , P 3,1 , and P 4,1 instead of four. So the chunks in the repaired nodes 1 and 2 are not decodable, and the MDS property is lost.
Thus, to preserve the MDS property over multiple rounds of repair, NCCloud uses a specific implementation of FMSR codes based on random chunk selection, which we call random FMSR codes. NCCloud seeks to completely avoid linear dependence in chunk regeneration and hence losing the MDS property. Specifically, NCCloud performs the r th (where r ≥ 1) round of repair as follows: (i) It randomly selects a chunk from each surviving node (i.e., f (.) returns a random value), and generates random encoding coefficients to encode the selected chunks into new chunks (i.e., γ i,j 's are randomly chosen). (ii) It then performs two-phase checking. In the first phase, it checks if the MDS property is satisfied with the new chunks generated (i.e., the chunks of any k out of n nodes remain decodable) after the current r th round of repair. In the second phase, it further checks if the MDS property is still satisfied after the (r + 1) th round of repair for any possible node failure, and this property is called the repair MDS property. (iii) If both phases are passed, then NCCloud writes the generated chunks to a new node; otherwise, it repeats (i) and (ii) with another set of random chunks and random encoding coefficients. We now formally define the repair MDS property. Definition 3: Repair-based collections (RBCs). An RBC of the r th round of repair is a collection of k(n − k) chunks that can be obtained after the r th round of repair by the following procedure. (Step 1) We select any n − 1 out of n nodes. (Step 2) We select k − 1 out of the n − 1 nodes found in Step 1 and collect n − k chunks from each selected node. (Step 3) We collect one chunk from each of the non-selected n − k nodes. Clearly, the number of collected chunks is We can easily verify that there are n n−1 Intuitively, an RBC refers to a collection of chunks of k nodes after the (r + 1) th round of repair for any possible node failure. For instance, after repairing node 1 in Figure 1, one example RBC is R = {P ′ 1,1 , P 3,1 , P 3,2 , P 4,1 }. This means that we assume: node 2 is the failed node in the next round of repair; the failed node 2 will be repaired by chunks P ′ 1,1 , P 3,1 (or P 3,2 ), and P 4,1 ; and we consider if the chunks of node 2 (after repair) and node 3 are decodable. Note that the chunks of node 2 and node 3 are linear combinations of this RBC R.
We assume that when a file is stored, it is first encoded using Reed-Solomon codes, such that any k(n − k) out of n(n − k) (parity) chunks are decodable. Note that these k(n−k) chunks may reside in more than k nodes (e.g., P 1,1 , P 2,1 , P 3,1 , P 4,1 in Figure 1). If no repair is carried out, then we ensure that every possible RBC is decodable.
However, after repairing a node failure, there exist some provably non-decodable RBCs. For example, in Figure 1, are linear combinations of P 2,1 , P 3,1 , P 4,1 . Note that these non-decodable RBCs all contain the chunks of the repaired node 1. Each of these RBCs is a linear combination of chunks P 2,1 , P 3,1 , P 4,1 (i.e., less than four chunks) in the repair. Accordingly, we define the following: Definition 4: Linear Dependent Collection (LDC). Suppose an RBC of the r th round of repair contains the n−k chunks of the repaired node that are collected in Step 2 (see Definition 3). If and only if every chunk of this RBC is a linear combination of a set of less than k(n−k) chunks of the r th round of repair, we call it an LDC of the r th round of repair.
Definition 5: Repair MDS (rMDS) property. If all RBCs, after excluding the LDCs, of the r th round of repair are decodable, then we say the rMDS property is satisfied. It means that if every RBC that is a linear combination of exactly k(n − k) chunks is always decodable, then we say that the rMDS property is satisfied.
Definition 6: (n,k)-FMSR codes. An original file is stored in n nodes in the form of n(n − k) chunks. If these n(n − k) chunks satisfy both the MDS and rMDS properties, then we say this file is FMSR-encoded.
Summary. Authors of NCCloud [10] show via simulations that by checking both the MDS and rMDS properties in each round of repair, FMSR codes can preserve the MDS property after hundreds of rounds of repair. Also, if we check only the MDS property but not the rMDS property, then after some rounds of repair we cannot regenerate the chunks that preserve the MDS property within a fixed number of iterations (this is called the bad repair [10]). On the other hand, there is no formal theoretical analysis showing the need of two-phase checking to preserve the MDS property after any number of rounds of repair. Also, random FSMR codes repeat two-phase checking until the valid chunks are regenerated. This could involve many iterations and significantly increase the repair time overhead (see Section VI). In the following sections, we formally provide the theoretical validation of existence of FMSR codes and the design of deterministic FMSR codes.

IV. EXISTENCE
We now prove the existence of FMSR codes. In this work, we focus on k = n−2, implying that FMSR codes are doublefault tolerant as conventional RAID-6 codes [12]. Double-fault tolerance has been assumed in practical cloud storage systems (e.g., GFS [8] and Azure [4]). Our goal is to show that FMSR codes always maintain double-fault tolerance (i.e., the MDS property is always satisfied with k = n − 2) after any number of rounds of uncoded repair, while the repair bandwidth is kept at the MSR point.
We first give three lemmas. Lemmas 1 and 2 provide a guideline of how to choose n − 1 chunks from n − 1 surviving nodes (one chunk from each node) to repair a failed node. Lemma 3 implies that if the finite field size is large enough, then we can always find a set of encoding coefficients to regenerate new chunks for a repaired node so as to maintain the MDS and rMDS properties after each round of repair. Finally, we prove Theorem 1 for the existence of FMSR codes.
Lemma 1: In repair, let F be the set of n − 1 chunks selected from n − 1 surviving nodes to regenerate the n − k chunks of the repaired node. Also, let Q be the set of chunks collected in Step 3 of RBC construction (see Definition 3). If an RBC (denoted by R) containing the n − k chunks of the repaired node is an LDC, then F and Q must have two or more common chunks.
Proof: Without loss of generality, let node 1 be the failed node. Let P be the set of chunks collected in Step 2 of Definition 3 excluding the n−k chunks of the repaired node 1. Thus, R = {P ′ 1,1 , . . . , P ′ 1,n−k } ∪ P ∪ Q. As P ′ 1,1 , . . . , P ′ 1,n−k are obtained by linearly combining the chunks in F , we infer that R contains linear combinations of chunks in F ∪ P ∪ Q.
Since F selects one chunk from each of n − 1 surviving nodes and P has all the chunks from k − 2 surviving nodes, F and P have k − 2 identical chunks, i.e., |F ∩ P| = k − 2.
Lemma 2: Suppose that the rMDS property is satisfied after every r th round of repair. Then for any n − 1 out of n nodes, we can always select one chunk from these n − 1 nodes (i.e., a total of n − 1 chunks) such that any RBC containing the selected n − 1 chunks is decodable.
Proof: Without loss of generality, suppose that we construct an RBC R by selecting the chunks from nodes 2, . . . , n (see Step 1 of Definition 3), and that G be the set of n − 1 chunks selected from nodes 2, . . . , n (one chunk from each nodes). We prove the existence of G such that if R contains G (i.e., G ⊂ R), then R is decodable.
If node 1 is the repaired node in the r th round of repair, then R is never an LDC (by Definition 4). Since the rMDS property is satisfied by our assumption, R is decodable (by Definition 5).
If node 1 is not the repaired node in the r th round of repair, then without loss of generality, let node 2 be the repaired node. By the FMSR design, the chunks of node 2 are linearly combined by one chunk in each of nodes 1, 3, . . . , n. We denote these chunks by F = {P 1,f (1) , P 3,f (3) , . . . , P n,f (n) }.
Since each node has n − k > 1 chunks, we can construct G = P 2,g(2) , . . . , P n,g(n) } such that g(i) = f (i) for i = 3, . . . , n (while g(2) can be randomly picked). If R contains G, then in Step 3 of RBC construction (see Definition 3), at least one chunk must be selected from G. However, G has no identical chunk with F . By Lemma 1, R is not an LDC. Since the rMDS property is satisfied, R is decodable.
Lemma 3: (Schwartz-Zippel Theorem) [15]. Consider a multivariate non-zero polynomial h(x 1 , . . . , x t ) of total degree ρ over a finite field F. Let S be a finite subset of F, and x 1 , . . . ,x t be the values randomly selected from S. Then the probability Pr[h(x 1 , . . . ,x t ) = 0] ≤ ρ |S| . Theorem 1: Consider a file encoded using FMSR codes with k = n − 2. In the r th (r ≥ 1) round of uncoded repair of some failed node j, the lost chunks are reconstructed by the random linear combination of n−1 chunks selected from n−1 surviving nodes (one chunk from each node). Then after the repair, the reconstructed file still satisfies both the MDS and rMDS properties with probability that can be driven arbitrarily to 1 by increasing the field size of F q .
Proof: We prove by induction on r. Initially, we use Reed-Solomon codes to encode a file into n(n−k) = 2n chunks that satisfy both the MDS and rMDS properties. Suppose that after the r th round of repair, both the MDS and rMDS properties are satisfied (this is our induction hypothesis).
Let U r = {P 1,1 , P 1,2 ; . . . ; P k+2,1 , P k+2,2 } be the current set of chunks after the r th round of repair. In the (r + 1) th round of repair, without loss of generality, let node 1 be the failed node to repair. Since U r satisfies the rMDS property, we have the following corollary by Lemma 2.
We use F to repair node 1. Suppose that the repaired node 1 has the new chunks {P ′ 1,1 , P ′ 1,2 }. Then: Next we prove that we can always tune γ i,j in F q in such a way that the set of chunks in the (r + 1) th round of repair U r+1 = {P ′ 1,1 , P ′ 1,2 ; . . . ; P k+2,1 , P k+2,2 } still satisfies both MDS and rMDS properties. The proof consists of two parts.
Part II: U r+1 satisfies the rMDS property. By Definition 5, we need to prove that all the RBCs of U r+1 except the LDCs are decodable. By Definition 3, we consider two cases of RBCs. Without loss of generality, we let node 1 be the repaired node.
Our goal is to show that if R 1 is not an LDC, then it is decodable. By Lemma 1, we know that if R 1 is an LDC, then there are at least two chunks selected in Step 3 that belong to F = {P 2,f (2) , . . . , P n,f (n) } (which are used to regenerate chunks for node 1), or equivalently, g(k) = f (k) and g(k + 1) = f (k +1). Therefore, to prove that R 1 except the LDCs is decodable, it is equivalent to prove that R 1 is decodable when (a) g(k) = f (k) and g(k + 1) = f (k + 1), (b) g(k) = f (k) and g(k + 1) = f (k + 1), or (c) g(k) = f (k) and g(k + 1) = f (k + 1).
The above collection is an RBC containing F . By our corollary, the collection is decodable. Therefore, R 1 is linear combination of a decodable collection. Then we can use the similar method in Part I to prove that there always exists an assignment of γ i,j in a sufficiently large field such that R 1 is decodable (by Lemma 3). The proof of (b) is similar to that of (a) and is thus omitted.
Lastly, let us consider (c). Now, X can be written as {P 2,1 , P 2,2 ; . . . ; P k−1,1 , P k−1,2 ; P k,1 , P k,2 ; P k+1,1 , P k+1,2 ; P k+2,f (k+2) }. Define X = X − {P k+2,f k+2 }. Note that the MDS property of X is satisfied by induction hypothesis. Thus, X is decodable, implying that P k+2,f (k+2) can be seen as a linear combination of X . Obviously, we can also say that X is formed by linear combinations of X . Therefore, R 1 is also formed by linear combinations of the decodable collection X . Based on the above argument, R 1 is decodable.
Denote the RBC by R 2 = {P 2,1 , P 2,2 ; . . . ; P k,1 , P k,2 ; P ′ 1,g(1) , P k+1,g(k+1) }. We need to show that if R 2 is not an LDC, it is decodable. Based on Lemma 1, there is no more than one identical chunk between F and the RBC's chunks collected in Step 3, so R 2 is never an LDC. We only need to prove that every possible R 2 is decodable.
Combining Case 1 and Case 2, we deduce that all RBCs excluding the LDCs are decodable. So U r+1 satisfies the rMDS property. Therefore, Theorem 1 concludes.

V. DETERMINISTIC FMSR CODES
In NCCloud [10], the repair operation under FMSR codes is accomplished based on two random processes: (i) using random chunk selection to read chunks from the surviving nodes and (ii) applying random linear combinations of the selected chunks to generate new chunks for the repaired node. Section IV has proved the correctness of the random-based repair operation by virtue of existence of FMSR codes. On the other hand, a drawback of the random approach is that it may need to try many iterations to generate the correct set of chunks that satisfies both the MDS and rMDS properties.
In this section, we propose a deterministic repair scheme under FMSR codes (k = n − 2), such that both the chunk selection and linear combination operations are deterministic. This enables us to significantly speed up the repair operation. In our deterministic scheme, we specify which particular chunk should be read from each surviving node in each round of repair. We also derive the sufficient conditions on which the encoding coefficients should satisfy. To design the deterministic scheme, we first introduce an evolved repair MDS property.
Definition 7: Evolved Repair MDS (erMDS) property. Let k = n−2. For any k+1 out of n nodes, if we can always select one specific chunk from each of the k + 1 nodes such that any RBC containing these selected k +1 chunks is decodable, then we say the code scheme has the erMDS property.
From Lemma 2, we can see that if the rMDS property is satisfied, then the erMDS property is also satisfied. Thus, any RBCs satisfying the rMDS property is a subset of the RBCs satisfying the erMDS property. We use the erMDS property to construct a deterministic FMSR code.
To construct deterministic FMSR codes for k = n − 2, we describe how we store a file and how we trigger the r th (r ≥ 1) round of repair for a node failure. The correctness of our deterministic FMSR codes is proved in Appendix.
The first round of repair. Suppose without loss of generality that node 1 fails and is then repaired by two steps.

VI. EVALUATION
In this section, we evaluate the repair performance of two implementations of FMSR codes: (i) random FMSR codes, which use random chunk selection in repair and is used in NCCloud [10] and (ii) deterministic FMSR codes, which use deterministic chunk selection proposed in Section V. We show that our proposed deterministic FMSR codes can significantly reduce the time required to regenerate parity chunks in repair.
We implement both versions of FMSR codes in C. We implement finite-field arithmetic operations over a Galois Field GF(2 8 ) based on the standard table lookup approach [9]. We conduct our evaluation on a server running on an Intel CPU at 2.4GHz. We consider different values of n (i.e., the number of nodes). For each n, we first apply Reed-Solomon codes to generate the encoding coefficients that will be used to encode a file into parity chunks before uploading. In each round of repair, we randomly pick a node to fail. We then repair the failed node using two-phase checking, based on either random or deterministic FMSR code implementations. The failed node that we choose is different from that of the previous round of repair, so as to ensure a different chunk selection in each round of repair. We conduct 50 rounds of repair in each evaluation run. We conduct a total of 30 runs over different seeds for each n.
The metric we are interested in is the checking time spent on determining if the chunks selected from surviving nodes can be used to regenerate the lost chunks. We do not measure the times of reading or writing chunks, as they are the same for both random and deterministic FMSR codes. Instead, we focus on measuring the processing time of two-phase checking in each round of repair. It is important to note that twophase checking only operates on encoding coefficients, and is independent of the size of the file being encoded. Note that we do not specifically optimize our encoding operations, but we believe our results provide fair comparison of both random and deterministic FMSR codes using our baseline implementations. Figure 2 first depicts the aggregate checking times for a total of 50 rounds of repair versus the number of nodes when using random and deterministic FMSR codes. The aggregate checking time of random FMSR codes is small when n is small (e.g., less than 1 second for n ≤ 6), but exponentially increases as n is large. On the other hand, the aggregate checking time of deterministic FMSR codes is significantly small (e.g., within 0.2 seconds for n ≤ 10).
Our investigation finds that the checking time of random FMSR codes increases dramatically as the value of n increases. For example, when n = 12 (not shown in our figures), we find that the repair operation of our random FMSR code implementation still cannot return a right set of regenerated chunks after running for two hours. In contrast, our deterministic FMSR codes can return a solution within 0.5 seconds.
To further examine the significant performance overhead of random FMSR codes, Figures 3 and 4 show the cumulative checking time and number of two-phase checkings performed for r rounds of repair, respectively, for n = 8, 9, 10. We note that random FMSR codes incur a fairly large but constant number of two-phase checkings in each round of repair. For example, for n = 10, each round of repair takes around 100 iterations of two-phase checkings (see Figure 4(a)). On the other hand, deterministic FMSR codes significantly reduce the number of iterations of two-phase checking (e.g., less than 2.5 on average for n = 10). In summary, our evaluation results show that deterministic FMSR codes significantly reduce the two-phase checking overhead of ensuring that the MDS property is preserved during repair.

VII. CONCLUSIONS
This paper formulates an uncoded repair problem based on functional minimum storage regenerating (FMSR) codes. We formally prove the existence of FMSR codes and provide a deterministic FMSR code construction. We also show via our evaluation that our deterministic FMSR codes significantly reduce the repair time overhead of random FMSR codes. Our theoretical results validate the correctness of existing practical FMSR code implementation [10]. We also demonstrate the feasibility of preserving the benefits of network coding in minimizing the repair bandwidth with uncoded repair.

APPENDIX
We now prove the correctness of the deterministic FMSR codes in Section V. Initiaially, the file is stored with Reed-Solomon codes, such that any 2k out of 2(k + 2) (parity) chunks are decodable to the original file. Therefore, the set of chunks being stored before any repair satisfies the MDS and erMDS properties. Now, we show that the MDS and erMDS properties are always satisfied after each round of repair, based on our chunk selection and coefficient construction.
The first round of repair. Let U 1 = {P ′ 1,1 , P ′ 1,2 ; P 2,1 , P 2,2 ; . . . ; P n,1 , P n,2 } be the set of all chunks after the first round of repair (for failed node 1). Next we prove that U 1 still satisfies both the MDS and erMDS properties.
(U 1 satisfies the erMDS property) Since the file is initially stored with Reed-Solomon Codes, the erMDS property is satisfied before the repair. Hence there already exist k + 1 chunks, say P 2,1 , . . . , P k+2,1 , such that any RBC containing them is decodable. Thus, we only need to check whether for the repaired node 1 and any k of nodes 2, . . . , k + 2, there always exist k + 1 chunks such that by collecting one chunk from each such node, any RBC containing them is decodable. Without loss of generality, we just consider the case for the repaired node 1 and nodes 2, . . . , k + 1 for simplicity.
Here, we select the k + 1 chunks in the way that they are distinct from those selected for the first round of repair. In this case, we collect F 1 = {P ′ 1,2 , P 2,2 , . . . , P k+1,2 } (note: either P ′ 1,1 or P ′ 1,2 is fine). Next we show that the constructed γ i,j can make any RBC containing F 1 decodable. Since the repaired node 1 may offer one or two chunks to an RBC, we consider two cases.
The r th repair (r > 1) Take r = 2 for instance. Suppose without loss of generality that node k + 2 fails. Then we select {P ′ 1,2 , P 2,2 , . . . , P k+1,2 } which are distinct from those in the first round of repair. We can observe that in fact this set is F 1 in the first round of repair. As mentioned above, any RBC containing F 1 is decodable. So F 1 can be used for the second round of repair. Then we can generate the coefficients that satisfy the similar inequalities as (4), (5), and (6). The proof of correctness is similar as r = 1 and thus omitted.


Models vs. Inductive Inference for Dealing With Probabilistic Knowledge

Two different approaches to dealing with probabilistic knowledge are examined -models and inductive inference. Examples of the first are: influence diagrams [1], Bayesian networks [2], log-linear models [3, 4]. Examples of the second are: games-against nature [5, 6] varieties of maximum-entropy methods [7, 8, 9], and the author's min-score induction [10]. In the modeling approach, the basic issue is manageability, with respect to data elicitation and computation. Thus, it is assumed that the pertinent set of users in some sense knows the relevant probabilities, and the problem is to format that knowledge in a way that is convenient to input and store and that allows computation of the answers to current questions in an expeditious fashion. The basic issue for the inductive approach appears at first sight to be very different. In this approach it is presumed that the relevant probabilities are only partially known, and the problem is to extend that incomplete information in a reasonable way to answer current questions. Clearly, this approach requires that some form of induction be invoked. Of course, manageability is an important additional concern. Despite their seeming differences, the two approaches have a fair amount in common, especially with respect to the structural framework they employ. Roughly speaking, this framework involves identifying clusters of variables which strongly interact, establishing marginal probability distributions on the clusters, and extending the subdistributions to a more complete distribution, usually via a product formalism. The product extension is justified on the modeling approach in terms of assumed conditional independence; in the inductive approach the product form arises from an inductive rule.

Ex amp 1 es of the second are: .games-against nature [5, 6J, varieties of maximum ent�opy methods [7, 8, 9J, and the author's min-sco�e induction In the mode ling approach, the basic issue is manage abi lity, with �espect to data elicitation and computatic • n.
Thus., it is assumed that the per·tinent set of u s er·s in sc• me sense Knows the �e levant p�obabi l ities, and the p�ob lem is to forma.t that Know ledge in a wa>' that is convenient to input and sto�e and that allows computation of the answe�s to current questions in an expeditious fashion.
The basic issue fo� the inductive approach appears at fi�st sight tc• be ver·y differ·er.t.
In this approach it is p�esumed that the �e levant p�obabi l ities a�e on ly partia lly Kr.owr., ar.d the pr·ob lem is to exter.d that incomp lete inf c • r· mation in a �easonab le way to answe� cu��ent questions.
Clear ly, this approach �equi�es that some form of induction be invoKed. Of course, rnanageabi l ity is an impo�tant addi tiona l cc• ncer·n.
Despite their seeming dif fe�ences, the two approaches have a fai� amount in common, especia ll>' t.vi th r·espect tc• the structura l f�ameworK they emp loy. Rough ly speaKing, this f�ameworK invo lves identifying cluste�s of variab les which strong ly inte�act, establishing margina l probabi lity distri butions on the clusters, and extending the subdistributions to a more comp lete distribution, usua lly via a produc t forma l ism.
The product extension is justified on the mode ling approach in terms of assumed conditiona l independence; in the inductive app�oach the p�oduct form a�ises from an inductive ru le .  The correspqnding probabll ity distributions on members of C PC = P<Y1) , •• , ,P<Y1,.) is called a pr·obabi 1 i ty system Cor· system for short.) In this notation, Y may be either abso lute or· conditional.
A system PC is called consistent if there is a proba bility distribution P<X> that fulfills (1) or (1'") fc·r· all cc• mponents Y ir1 PC. Ir1 gener·al, if PC i:. con:.isterrt, ther·e will be a set K< PC> of distributions compatible with PC.
In the model approach, it is assumed that a system PC represents the clustering of descriptors with respect to dependence; i.e., within a component\' , the descr·iptors have  A web is a structure which fulfills the recursion: 1.
Any absolute compone-nt is a web.

2.
If Y is a terminal component, and C-CY} is a web, the-n C is a \AJE>b.
From the definition, a we-b contains at least one abso- A web is somewhat more general than influence diagrams or Bayesian networks.
These can be characterized as condi tional webs where for any conditional component Y = <ZIW>, Z cons.ists of a singfe descriptor.
Conditional webs are signicant for modeling probabil is tic Knowledge as a result of two basic properties: a.
The product P •<x> = n P<Y> is a joint probabi 1 i ty c distribution on X. b.
Proofs for these assertions are readily constructed by induction on the number of components in a web.
What these two properties. entai 1, in effect, is that if you can represent your knowledge concerning a distribution P<X) by the sub-distributions PC for a web C plus assuming conditional independence for descriptors not in common components, then the product P <X> "automat i ca. 11 y" expresses. that know! edge.
From the model! ing point of view, then, a web is a rela tively manageable representation of probabilistic Knowledge.
All that need be input are the subdistributions PC. The product is quite convenient for computations; e.g., the mani pulations feasible for influence diagrams are directly ex tendable to webs.

Inductiorr and maximum-entr·opy
Tur·rr i ng to the inductive apprc• ach, in an ear·l i er· publ i cation I demonstrated that for a subspecies of web, namely a forest, the product.extension is the maximum entropy exten sion of PC.
(11] A forest is a web in which all terminal components Y = <Z: W) fulfill the additional restr·iction that W is contained in some componer .. Knowledge will be at least as informative as a conclusion t�-•ithout that Knowledge. [10] Thus, if all you Knot"'' is a set of subdistributions PC, and PC is a forest, then the product extension is a supportable estimate of the total distribution.
One of the motivations for studying webs was the expec tation that the product extension would also turn out to b e the maximum entropy extension for a general web. The expec tation was based on a purported result of P. M. Lewis fre quent 1 y cited in the 1 i tera ture tc• the effect that for· a structure with a product extension, the product is the maximum entropy extension. [12] Unfortunately, the Lewis "result" happens to be incorrect.  Table I; where "1" means occurrance and "0" means non-occurrance in the 1 ist of cases. Table I x, x.,.., P<X3 IX 1 .Xl.) The product distribution p•(X) is along with another distribution P 0 (X).
of PC--which can easily be verified by clearly a higher entropy distribution. Table I I x, x'l. X 3 P •oo The numerical differ-ence in entropy is small, but the difference between .25 and 1/6 for· P<1 ,1 ,1), e.g., may not seem tr·ivial.
The elementary structure C of the example is actually a substructure of any web that is not a forest. Hence a similar counter-example can be constructed for any such web. The example is also a counter to the Lewis "result".
The upshot of this inquiry, then, is that a forest is the most general structure for which the product extension is always the maximum entropy extension.

Discussion
At first glance, the fact that the product extension of a web is not in general maximum entropy may appear benign.
From the standpoint of the model approach, the basic properties of a web--the product is a probability and an extension of PC--maKe webs a highly convenient representation of probabilistic Knowledge.
All that is lost is a desirable, but by no means essential, fallbacK.
In the case of a forest, for example, if the assumption of conditional independence for separated descriptors is shaky, then it can still be contended that the product is a reasonable estimate of the joint distribution, given PC. It would be a valuable safety feature if the same could be claimed for a web.
Fr·om the standpoint of the inductive approach, it is perhaps unfortunate that the product extension of a web is not maxi mum entropy.
However, the maxi mum entropy ex ten�. ion can be sought by other means.
[l!J What is lost is the convenience of the pr·oduc t form.
For· the comp 1 ex systems of many descriptors common in expert systems, maximum entropy formal isms are 1 ikely to be cumbersome.
On a somewhat deeper level, however, the result is thought-provoKing.
One route that can be taKen is to "prune" the structure to a forest.
Lemmer [15 J has adopted this suggestion, fol A basic e 1 emen t missing fr·om this program is a measure of the information that is lost by the pruning process.
Concomm i tan t 1 y, there is no systematic procedur·e fc• r· deter· mining the most informative forest contained in the knowledge available to the analyst. Given a general probability system PC, if PC is consistent, the amount of information in PC can be defined as max Entropy( P) . At present, there is no PE.K<PC) way to determine this quar.tity directly from PC--or·, fc• r· that matter, determining whether PC is consistent.
These issues appear to be one area of potentially fruitful research.


s2fieldsofstudy:
Computer Science
Mathematics

text:
A Convex Approach for Image Hallucination

In this paper we propose a global convex approach for image hallucination. Altering the idea of classical multi image super resolution (SU) systems to single image SU, we incorporate aligned images to hallucinate the output. Our work is based on the paper of Tappen et al. where they use a non-convex model for image hallucination. In comparison we formulate a convex primal optimization problem and derive a fast converging primal-dual algorithm with a global optimal solution. We use a database with face images to incorporate high-frequency details to the high-resolution output. We show that we can achieve state-of-the-art results by using a convex approach.

Introduction
Single image Super Resolution (SU) systems yield to estimate a high-resolution (HR) image from low-resolution (LR) input. This is clearly an ill-posed problem due to the fact that important high frequency information is lost in a downsampling process.
A common constraint to nearly all SU systems is the reconstruction constraint, which says that the HR result down-sampled should be the same as the LR input. However, this constraint is weak and the space of possible solutions is large. A generic smoothness prior, like the Total Variation (TV), can improve this constraint but no lost information is infered. More advanced systems model edge statistics which can produce HR images with sharp edges while leaving other regions smooth [12]. This approach has its advantages in creating sharp edges with minimal jaggy or squary artifacts. But their performance will decrease as the resolution of the input decreases because the perceptual important edges will vanish. Additionally such systems cannot introduce novel high frequency details which were lost in the down-sampling process.
Backer and Kanade have shown in [1] that systems which only rely on the reconstruction constraint (and possible altered with a smoothness prior) cannot create high frequency image content. They propose the technique of image hallucination where HR image details and there LR correspondences are learned on a patch basis to synthesise HR images. Such systems like [9] can introduce new details which are not present in the low resolution image. However, the patchselection process remains a key problem in such systems and the mathematical models make it difficult to control artefacts in the output. A state-of-the-art enhancement of such a system is the work of Sun et al. [13] which incorporates their so called textual context bridging the gap between image hallucination and texture synthesis.
While these systems perform well on general images, domain based SU system where the content of the image is known have shown improvements of the results again. An example of such an approach is the work of Liu et al. face Figure 1: System-Overview: We use SiftFlow [10] to find similar appearing images based on the alignment energy. These Canididates are warped to match the input. The LR input and the aligned candidates are incorporated to form the estimate.
hallucination [8]. Their system inferes regularities of face-appearances to hallucinate details that a general image model can't create. However, the system of [8] is limited to frontal face images and can't handle large pose and viewpoint changes.
Our work is based on the paper of Tappen el al. [14]. This approach uses aligned face images prior to the hallucination process and therefore incorporates the ideas of the classic multi-image SU-systems. Tappen et al. uses Patch Match [2] to quickly search for similar face images in a large database. The best matches are called candidates. These candidates are densely aligned using the SIFTflow algorithm [10]. Their system incorporates a edge focusing image prior, a global likelihood function (the reconstruction constraint) and an examplebased non-convex hallucination model within a Baysian framework. Tappen et al. pointed out that if their system can't find good candidates, the performance decreases fast and the results get blurry. These limitations could be compensated by falling back to an edge-based system. Our system tries to improve this behaviour by using a hallucination model more robust to outliers.
We proposes a similar work flow, but in comparison all our models are convex and we omit PatchMatch. We search the database with SiftFlow utilizing the SiftFlow energy and warp the search results with the same algorithm. We omit PatchMatch because we think it is more important to have good aligned candidates rather than similar appearing images. Our convex optimization problem joins an total variation based image prior, the reconstruction constraint and a hallucination model robust to outliers. Starting with the primal minimization problem we derive a generic saddle-point problem and solve it with a fast converging primal-dual algorithm proposed by Chambolle et al. [5]. Figure 1 shows our system overview.
This paper is organized as followed. After presenting a convex approach for image hallucination in section 2 we derive a generic saddle-point problem and solve it with a so called primal-dual algorithm in section 3. In section 4 we describe the experiments made and we conclude in section 5.

A Convex Approach for Image Hallucination
As pointed out in the introduction, our work alters the model of Tappen et al. [14] to a convex approach. Solving a convex minimization problem has nice advantages. Convexity guarantees an existing, unique solution [4] and fast convergence can be achieved. However, choosing the image models and energy minimization terms are crucial for a perceptual good solution. The minimization problem of (1) combines 3 different image models and constraints where u is our HR estimate, f the LR input and g C are the aligned candidate images.
The first term is a general smoothness prior equipped with the TV-norm. This model preserves sharp edges while staying smooth in other regions. The TV is defined as T V (u) = Ω |∇u|dx, where ∇ = ∂ ∂x , ∂ ∂y is the gradient operator and the · is the L1-norm.
The second term of (1) models the reconstruction constraint. The constraint ensures that the down-sampled HR image yield to the LR input. In other words, the HR estimate down-sampled should be the same as the input. The matrices DB composes of a Gaussian blurring or anti-alias filter B and a downsampling matrix D. The reconstruction constraint implies a linear model where the observed image f is a linear combination of the undistorted image u added by noise f = Au+n. If we model the noise as Gaussian, we end up by equipping this term with a quadratic norm minimizing the noise. The factor λ controls how strong the constraint is imposed.
The third term of (1) represents a non-parametric image model here referred as the hallucination term. Having found similar candidate images from a database and aligned them to our input, high-frequency details can be introduced from these candidates. The term minimizes the difference between the HR result u and the candidate images g C after applying a high-pass filter H. We apply the high-pass filter H to infer only high-frequency information from the candidates. Thats because the low-frequency details are still present in the LR input and can be omitted. Equipping this function with the L1-norm makes it robust to outliers which is the case if no good candidates where found or if the alignment fails.
Note that there exists a strong relation between the blurring matrix B, the high-pass filter H and the scaling factor. In fact the high-pass filter kernel equals a all-pass kernel δ subtracted by the blurring kernel. So we incorporate just frequencies we lost in the down-sampling process. Moreover the blurring kernel depends on the scaling factor [15]. We choose the standard derivation for the blurring kernel as σ = 1 4 ξ 2 − 1, where ξ is the scaling factor.

Deriving the Primal-Dual Algorithm
In this section we will derive the first order primal-dual form of (1). We will solve this generic saddle-point problem with a variational approach, the primal-dual algorithm of Chambolle et al. [5].
The goal is to transform the primal minimization problem (1) into a convexconcave saddle-point problem of the type: with a continuous linear operator K, and G(x) and F (x) being convex functions.
In a first step one has to apply the Legendre-Fenchel transformation also refered as the conjugate of a function [4]. We derive the conjugate of the total variation (TV) ∇u 2,1 and of the hallucination term γ i H(u − g i ) 1 introducing the dual variables p and r i respectively. Additionally the primal variables w i is introduced as a lagrange-multipliere of the hallucination term leading to: with the structure of K, x and y as: The term δ p ∞≤1 (p) denotes the indicator function and p ∞ the maximum norm. Note that we don't apply the Legendre-Fenchel transformation to the reconstruction constraint λ DBu − f 2 2 . Instead we solve this sub-problem using the conjugate-gradient method (CG) [3] in an subroutine. Because the reconstruction constraint imply a linear model and thus consists of a linear system of equations, it is reasonable to use a fast-converging solver specialized on such systems. We refer to 3.2 for further details.

Algorithm
We use the first order primal-dual algorithm proposed in [5], there referred as "Algorithm 1". The idea is to perform a gradient ascent/decent step on the unconstraint objective function and sequentially reproject the variables according to the constraints. The gradient step-size σ and τ are crucial for convergence and have to satisfy τ λL 2 < 1 with L = K the operator norm of K. Within an iteration we perform a gradient decent in the primal variable x and a gradient ascent in the dual variable y followed by the reprojection utilizing the proxoperators. Additionally we perform a linear extrapolation of the dual variable based on the current and the previous iterates with θ = 1. This can be seen as an approximate extragradient step and offers fast convergence.

The prox-operators
Proximity Operators are a powerful generalization of projection operators. Their importance is attached by splitting the subject to be minimized into simpler functions that can be handled individually [6]. The proximity operator then assures to "resolve" the sub-gradient ∂G of any function G even if G is nonsmooth. We assume that F and G are simple so that one can compute their proximity operator in a closed-form. The operator is defined as: In order to apply the algorithm we have to compute the prox-operator for (I + σ∂F * ) −1 and (I + τ ∂G) −1 . In (3) we see that and The first term in F * (y) is the indicator function of a convex set and the proxor resolvent operator reduces to a pointwise Euclidean projection onto L 2 balls. The function −Hg i , r i poses an inner product and the prox operator of reduces to an affine function.
For w i 1 the resolvent operator poses a soft-threshold shrinkage function. The prox-operator of the reconstruction constraint poses again a linear problem: Note that the CG-method expects a symmetric positive definite matrix A new which is clearly the case. We apply the CG with a so called "hot-start" where the previous iterate of u is used for initialization. The hot-start initialization achieves faster convergence of the CG-method.

Experiments
In our experiments we use the PubFig83 database presented in [11]. The database consists of over 14,000 images of public figures, cropped to include just the faces and resized to the identical resolution of 100 × 100 pixels.
All results are produced in the same manner. First we down-sample the input by a factor of 4 using bicubic interpolation, followed by a bicubic upsampling by the same factor. We use the resampled image as an input to the SiftFlow [10] and search for candidates with the least SiftFlow energy. Figure 1  demonstrates this process. We just search in the set of pictures from the same individual as the input. We imply that the person of the input has already been identified by a face-recognition system and pictures of this person are available. Having found the best 6 candidate images, we aligned them to our input using again Siftflow. With this aligned candidates we run the primal-dual algorithm. Note that the input image f of the algorithm is still the bicubic down-sampled 25 × 25 image, while the candidates g i and the result u * are 100 × 100. On the output we calculate the Signal-to-Noise ratio (PSNR) and the SSIM index. Figure 2 shows some results of our algorithm.
In our experiments we discovered that a strong reconstruction constraint is needed and therefore the λ-value was set to λ = 5 · 10 4 , which has proven a high PSNR. The hallucination parameter γ was set to γ = 20 so that smoothing by the TV-regulatization is still applied. To treat the color images in optimization, we did a so called channel-by-channel optimization. A more comprehensive color treatment was proposed in [7] called vectorial total variation. This advanced TV-regulatization should be included in future work.
We ran our algorithm on all 14,000 images and got a mean PSNR of 24,13dB. This result outperforms the work of Tappen et al. which got a mean PSNR of 24.05dB. Table 1 shows a comparison with different algorithms and the achieved PSNR and SSIM index. The table was partly taken from Tappen et al. and we refer to [14] for further information. In figure 3 we show a comparison between the results of Tappen et al. and our approach. The percetual differences on these results are quite low which is not extraordinary because all these examples achieve a high PSNR and SSIM compared to the average.

Conclusion
We presented a convex and global approach for image hallucination. This implies a fast converging algorithm with a unique solution. By incorporating high-frequency information from similar images we get perceptually good solutions. Especially if the alignment of the candidates image works well, the results can be nearly perfect. A crucial part in our system poses the SiftFlow algorithm, first because we use it as a searching tool, and second and more important we use it for the alignment of the images. If SiftFlow is able to align the images, the results are superior to those where the alignment fails. Tracking failed alignments and replacing such candidates should achieve improvements in future work. We think that it is not so important to take images from the same person rather than having good alignments. For future work we propose to build a bag of visual words taken from face images and to apply the same algorithm so that no face-recognition system is needed. Due to the fine modeling of the down-sampling, blurring and highpass filter and the robust hallucination model our convex approach achieves good performance and state-of-the-art results.


Towards Coherent Multi-Document Summarization

This paper presents G-FLOW, a novel system for coherent extractive multi-document summarization (MDS). 1 Where previous work on MDS considered sentence selection and ordering separately, G-FLOW introduces a joint model for selection and ordering that balances coherence and salience. G-FLOW’s core representation is a graph that approximates the discourse relations across sentences based on indicators including discourse cues, deverbal nouns, co-reference, and more. This graph enables G-FLOW to estimate the coherence of a candidate summary. We evaluate G-FLOW on Mechanical Turk, and find that it generates dramatically better summaries than an extractive summarizer based on a pipeline of state-of-the-art sentence selection and reordering components, underscoring the value of our joint model.

Introduction
The goal of multi-document summarization (MDS) is to produce high quality summaries of collections of related documents. Most previous work in extractive MDS has studied the problems of sentence selection (e.g., Haghighi and Vanderwende, 2009)) and sentence ordering (e.g., (Lapata, 2003;Barzilay and Lapata, 2008)) separately, but we believe that a joint model is necessary to produce coherent summaries. The intuition is simple: if the sentences in a summary are first selected-without regard to coherence-then a satisfactory ordering of the selected sentences may not exist. An extractive summary is a subset of the sentences in the input documents, ordered in some way. 2 Of course, most possible summaries are incoherent. Now, consider a directed graph where the nodes are sentences in the collection, and each edge represents a pairwise ordering constraint necessary for a coherent summary (see Figure 1 for a sample graph). By definition, any coherent summary must obey the constraints in this graph.
Previous work has constructed similar graphs automatically for single document summarization and manually for MDS (see Section 2). Our system, G-FLOW extends this research in two important ways. First, it tackles automatic graph construction for MDS, which requires novel methods for identifying inter-document edges (Section 3). It uses this State-of-the-art MDS system G-FLOW • The attack took place Tuesday near Cailaco in East Timor, a former Portuguese colony, according to a statement issued by the pro-independence Christian Democratic Union of East Timor.
• The United Nations does not recognize Indonesian claims to East Timor.
• In a decision welcomed as a landmark by Portugal, European Union leaders Saturday backed calls for a referendum to decide the fate of East Timor, the former Portuguese colony occupied by Indonesia since 1975.
• Indonesia invaded East Timor in 1975 and annexed it the following year.
• Bhichai Rattakul, deputy prime minister and president of the Bangkok Asian Games Organizing Committee, asked the Foreign Ministry to urge the Saudi government to reconsider withdrawing its 105-strong team.
• The games will be a success.
• Thailand won host rights for the quadrennial games in 1995, but setbacks in preparations led officials of the Olympic Council of Asia late last year to threaten to move the games to another country.
• Thailand showed its nearly complete facilities for the Asian Games to a tough jury Thursday -the heads of the organizing committees from the 43 nations competing in the December event. Table 1: Pairs of sentences produced by a pipeline of a state-of-the-art sentence extractor (Lin and Bilmes, 2011) and sentence orderer (Li et al., 2011a), and by G-FLOW. graph to estimate coherence of a candidate summary. Second, G-FLOW introduces a novel methodology for joint sentence selection and ordering (Section 4). It casts MDS as a constraint optimization problem where salience and coherence are soft constraints, and redundancy and summary length are hard constraints. Because this optimization problem is NPhard, G-FLOW uses local search to approximate it.
We report on a Mechanical Turk evaluation that directly compares G-FLOW to state-of-the-art MDS systems. Using DUC'04 as our test set, we compare G-FLOW against a combination of an extractive summarization system with state-of-the-art ROUGE scores (Lin and Bilmes, 2011) followed by a stateof-the-art sentence reordering scheme (Li et al., 2011a). We also compare G-FLOW to a combination of an extractive system with state-of-the-art coherence scores (Nobata and Sekine, 2004) followed by the reordering system. In both cases participants substantially preferred G-FLOW. Participants chose G-FLOW 54% of the time when compared to Lin, and chose Lin's system 22% of the time. When compared to Nobata, participants chose G-FLOW 60% of the time, and chose Nobata only 20% of the time. The remainder of the cases were judged equivalent.
A further analysis shows that G-FLOW's summaries are judged superior along several dimensions suggested in the DUC'04 evaluation (including coherence, repetitive text, and referents). A comparison against manually written, gold standard summaries, reveals that while the gold standard summaries are preferred in direct comparisons, G-FLOW has nearly equivalent scores on almost all dimensions suggested in the DUC'04 evaluation.
The paper makes the following contributions: • We present G-FLOW, a novel MDS system that jointly solves the sentence selection and ordering problems to produce coherent summaries. • G-FLOW automatically constructs a domainindependent graph of ordering constraints over sentences in a document collection, based on syntactic cues and redundancy across documents. This graph is the backbone for estimating the coherence of a summary.
• We perform human evaluation on blind test sets and find that G-FLOW dramatically outperforms state-of-the-art MDS systems.

Related Work
Most existing research in multi-document summarization (MDS) focuses on sentence selection for increasing coverage and does not consider coherence of the summary (Section 2.1). Although coherence has been used in ordering of summary sentences (Section 2.2), this work is limited by the quality of summary sentences given as input. In contrast, G-FLOW incorporates coherence in both selection and ordering of summary sentences. G-FLOW can be seen as an instance of discoursedriven summarization (Section 2.3). There is prior work in this area, but primarily for summarization of single documents. There is some preliminary work on the use of manually-created discourse models in MDS. Our approach is fully automated.

Subset Selection in MDS
Most extractive summarization research aims to increase the coverage of concepts and entities while reducing redundancy. Approaches include the use of maximum marginal relevance (Carbonell and Goldstein, 1998), centroid-based summarization (Saggion and Gaizauskas, 2004;, cov-ering weighted scores of concepts (Takamura and Okumura, 2009;Qazvinian et al., 2010), formulation as minimum dominating set problem (Shen and Li, 2010), and use of submodularity in sentence selection (Lin and Bilmes, 2011). Graph centrality has also been used to estimate the salience of a sentence (Erkan and Radev, 2004). Approaches to content analysis include generative topic models (Haghighi and Vanderwende, 2009;Celikyilmaz and Hakkani-Tur, 2010;Li et al., 2011b), and discriminative models (Aker et al., 2010).
These approaches do not consider coherence as one of the desiderata in sentence selection. Moreover, they do not attempt to organize the selected sentences into an intelligible summary. They are often evaluted by ROUGE (Lin, 2004), which is coherence-insensitive. In practice, these approaches often result in incoherent summaries.

Sentence Reordering
A parallel thread of research has investigated taking a set of summary sentences as input and reordering them to make the summary fluent. Various algorithms use some combination of topic-relatedness, chronology, precedence, succession, and entity coherence for reordering sentences (Barzilay et al., 2001;Okazaki et al., 2004;Barzilay and Lapata, 2008;Bollegala et al., 2010). Recent work has also used event-based models (Zhang et al., 2010) and context analysis (Li et al., 2011a).
The hypothesis in this research is that a pipelined combination of subset selection and reordering will produce high-quality summaries. Unfortunately, this is not true in practice, because sentences are selected primarily for coverage without regard to coherence. This methodology often leads to an inadvertent selection of a set of disconnected sentences, which cannot be put together in a coherent summary, irrespective of how the succeeding algorithm reorders them. In our evaluation, reordering had limited impact on the quality of the summaries.

Coherence Models and Summarization
Research on discourse analysis of documents provides a basis for modeling coherence in a document. Several theories have been developed for modeling discourse, e.g., Centering Theory, Rhetorical Structure Theory (RST), Penn Discourse Tree-Bank (Grosz and Sidner, 1986;Mann and Thompson, 1988;Wolf and Gibson, 2005;Prasad et al., 2008).
Numerous discourse-guided summarization algorithms have been developed (Marcu, 1997;Mani, 2001;Taboada and Mann, 2006;Barzilay and Elhadad, 1997;. However, these approaches have been applied to single document summarization and not to MDS. Discourse models have seen some application to summary generation in MDS, for example, using a detailed semantic representation of the source texts (McKeown and Radev, 1995;Radev and McKeown, 1998). A multi-document extension of RST is Cross-document Structure Theory (CST), which has been applied to MDS (Zhang et al., 2002;Jorge and Pardo, 2010). However, these systems require a stronger input, such as a manual CST-annotation of the set of documents. Our work can be seen as an instance of summarization based on lightweight CST. However, a key difference is that our proposed algorithm is completely automated and does not require any additional human annotation. Additionally, while incorporating coherence into selection, this work does not attempt to order the sentences coherently, while our approach performs joint selection and ordering.
Discourse models have also been used for evaluating summary quality (Barzilay and Lapata, 2008;Louis and Nenkova, 2009;Pitler et al., 2010). Finally, there is work on generating coherent summaries in specific domains, such as scientific articles (Saggion and Lapalme, 2002;Abu-Jbara and Radev, 2011) using domain-specific cues like citations. In contrast, our work generates summaries without any domain-specific knowledge. Other research has focused on identifying coherent threads of documents rather than sentences (Shahaf and Guestrin, 2010).

Discourse Graph
As described in Section 1, our goal is to identify pairwise ordering constraints over a set of input sentences. These constraints specify a multi-document discourse graph, which is used by G-FLOW to evaluate the coherence of a candidate summary.
In this graph G, each vertex is a sentence and an edge from s i to s j indicates that s j can be placed right after s i in a coherent summary. In other words, the two share a discourse relationship. In the fol-lowing three sentences (from possibly different documents) there should be an edge from s 1 to s 2 , but not between s 3 and the other sentences: s 1 Militants attacked a market in Jerusalem. s 2 Arafat condemned the bombing. s 3 The Wye River Accord was signed in Oct.
Discourse theories have proposed a variety of relationships between sentences such as background and interpretation. RST has 17 such relations (Mann and Thompson, 1988) and PDTB has 16 (Prasad et al., 2008). While we seek to identify pairs of sentences that have a relationship, we do not attempt to label the edges with the exact relation.
We use textual cues from the discourse literature in combination with the redundancy inherent in related documents to generate edges. Because this methodology is noisy, the graph used by G-FLOW is an approximation, which we refer to as an approximate discourse graph (ADG). We first describe the construction of this graph, and then discuss the use of the graph for summary generation (Section 4).

Deverbal Noun Reference
Often, the main description of an event is mentioned in a verbal phrase and subsequent references use deverbal nouns (nominalization of verbs) (e.g., 'attacked' and 'the attack'). In this example, the noun is derivationally related to the verb, but that is not always the case. For example, 'bombing' in s 2 above refers to 'attacked' in s 1 .
We identify verb-noun pairs with this relationship as follows. First, we locate a set of candidate pairs from WordNet: for each verb v, we determine potential noun references n using a path length of up to two in WordNet (moving from verb to noun is possible via WordNet's 'derivationally related' links).
This set captures verb-noun pairs such as ('to attack', 'bombing'), but also includes generic pairs such as ('to act', 'attack'). To filter such errors we score the candidate references. Our goal is to emphasize common pairs and to deemphasize pairs with common verbs or verbs that map to many nouns. To this end, we score pairs by (c/p) * (c/q), where c is the number of times the pair (v, n) appears in adjacent sentences, p is the number of times the verb appears, and q is the number of times that v appears with a different noun. We generate these statistics over a background corpus of 60,000 arti-cles from the New York Times and Reuters, and filter out candidate pairs scoring below a threshold identified over a small training set.
We construct edges in the ADG between pairs of sentences containing these verb to noun mappings. To our knowledge, we are the first to use deverbal nouns for summarization.

Event/Entity Continuation
Our second indicator is related to lexical chains (Barzilay and Lapata, 2008). We add an edge in the ADG from a sentence s i to s j if they contain the same event or entity and the timestamp of s i is less than or equal to the timestamp of s j (timestamps generated with (Chang and Manning, 2012)).

Discourse Markers
We use 36 explicit discourse markers (e.g., 'but', 'however', 'moreover') to identify edges between two adjacent sentences of a document (Marcu and Echihabi, 2002). This indicator lets us learn an edge from s 4 to s 5 below: s 4 Arafat condemned the bombing. s 5 However, Netanyahu suspended peace talks.

Inferred Edges
We exploit the redundancy of information in MDS documents to infer edges to related sentences. An edge (s, s ) can be inferred if there is an existing edge (s, s ) and s and s express similar information. As an example, the edge (s 6 , s 7 ) can be inferred based on edge (s 4 , s 5 ): s 6 Arafat condemned the attack. s 7 Netanyahu has suspended the talks.
To infer edges we need an algorithm to identify sentences expressing similar information. To identify these pairs, we extract Open Information Extraction (Banko et al., 2007) relational tuples for each sentence, and we mark any pair of sentences with an equivalent relational tuple as redundant (see Section 4.3). The inferred edges allow us to propagate within-document discourse information to sentences from other documents.

Co-referent Mentions
A sentence s j will not be clearly understood in isolation and may need another sentence s i in its context, if s j has a general reference (e.g., 'the presi-dent') pointing to a specific entity or event in s i (e.g., 'President Bill Clinton'). We construct edges based on coreference mentions, as predicted by Stanford's coreference system (Lee et al., 2011). We are able to identify syntactic edge (s 8 , s 9 ): s 8 Pres. Clinton expressed sympathy for Israel. s 9 He said the attack should not derail the deal.

Edge Weights
We weight each edge in the ADG by adding the number of distinct indicators used to construct that edge -if sentences s and s have an edge because of a discourse marker and a deverbal reference, the edge weight w G (s, s ) will be two. We also include negative edges in the ADG. w G (s, s ) is negative if s contains a deverbal noun reference, a discourse marker, or a co-reference mention that is not fulfilled by s. For example, if s contains a discourse marker, and s is neither the sentence directly preceding s and there is no inferred discourse link between s and s , then we will add a negative edge w G (s, s ).

Preliminary Graph Evaluation
We evaluated the quality of the ADG used by G-FLOW, which is important not only for its use in MDS, but also because the ADG may be used for other applications like topic tracking and decomposing an event into sub-events. One author randomly chose 750 edges and labeled an edge correct if the pair of sentences did have a discourse relationship between them and incorrect otherwise. 62% of the edges accurately reflected a discourse relationship. Our ADG has on average 31 edges per sentence for a dataset in which each document cluster has on average 253 sentences. This evaluation includes only the positive edges.

Summary Generation
We denote a candidate summary X to be a sequence of sentences x 1 , x 2 , . . . , x |X| . G-FLOW's summarization algorithm searches through the space of ordered summaries and scores each candidate summary along the dimensions of coherence (Section 4.1), salience (Section 4.2) and redundancy (Section 4.3). G-FLOW returns the summary that maximizes a joint objective function (Section 4.4).

Coherence
G-FLOW estimates coherence of a candidate summary via the ADG. We define coherence as the sum of edge weights between successive summary sentences. For disconnected sentence pairs, the edge weight is zero.
w G+ represents positive edges and w G− represents negative edge weights. λ is a tradeoff coefficient for positive and negative weights, which is tuned using the methodology described in Section 4.4.

Salience
Salience is the inherent value of each sentence to the documents. We compute salience of a summary (Sal(X)) as the sum of the saliences of individual sentences ( i Sal(x i )).
To estimate salience of a sentence, G-FLOW uses a linear regression classifier trained on ROUGE scores over the DUC'03 dataset. The classifier uses surface features designed to identify sentences that cover important concepts. The complete list of features and learned weights is in Table 2. The classifier finds a sentence more salient if it mentions nouns or verbs that are present in more sentences across the documents. The highest ranked features are the last three -number of other sentences that mention a noun or a verb in the given sentence. We use the same procedure as in deverbal nouns for detecting verb mentions that appear as nouns in other sentences (Section 3.1).

Redundancy
We also wish to avoid redundancy. G-FLOW first processes each sentence with a state-of-the-art Open Information extractor OLLIE (Mausam et al., 2012), which converts a sentence into its component relational tuples of the form (arg1, relational phrase, arg2). 3 For example, it finds (Militants, bombed, a marketplace) as a tuple from sentence s 12 .
Two sentences will express redundant information if they both contain the same or synonymous component fact(s). Unfortunately, detecting synonymy even at relational tuple level is very hard. G-FLOW approximates this synonymy by considering two relational tuples synonymous if the relation phrases contain verbs that are synonyms of each other, have at least one synonymous argument, and are timestamped within a day of each other. Because the input documents cover related events, these relatively weak rules provide good performance. The same algorithm is used for inferring edges for the ADG (Section 3.4). This algorithm can detect that the following sentences express redundant information: s 12 Militants bombed a marketplace in Jerusalem. s 13 He alerted Arafat after assailants attacked the busy streets of Mahane Yehuda.

Objective Function
The objective function needs to balance coherence, salience and redundancy and also honor the given budget, i.e., maximum summary length B. G-FLOW treats redundancy and budget as hard constraints and coherence and salience as soft. Coherence is necessarily soft as the graph is approximate. While previous MDS systems specifically maximized coverage, in preliminary experiments on a development set, we found that adding a coverage term did not improve G-FLOW's performance. We optimize: Here len refers to the sentence length. We add |X| term (the number of sentences in the summary) to avoid picking many short sentences, which may increase coherence and salience scores at the cost of overall summary quality.
The parameters α, β and λ (see Section 4.1) are tuned automatically using a grid search over a development set as follows. We manually generate extractive summaries for each document cluster in our development set (DUC'03) and choose the parameter setting that minimizes |F (X G-FLOW ) − F (X * )| summed over all document clusters. F is the objective function, X G-FLOW is the summary produced by G-FLOW and X * is the manual summary.
This constraint optimization problem is NP hard, which can be shown by using a reduction of the longest path problem. For this reason, G-FLOW uses local search to reach an approximation of the optimum. G-FLOW employs stochastic hill climbing with random restarts as the base search algorithm. At each step, the search either adds a sentence, removes a sentence, replaces a sentence by another, or reorders a pair of sentences. The initial summary for random restarts is constructed as follows. We first pick the highest salience sentence with no incoming negative edges as the first sentence. The following sentences are probabilistically added one at a time based on the summary score up to that sentence. The initial summary is complete when there are no possible sentences left to fit within the budget. Intuitively, this heuristic chooses a good starting point by selecting a first sentence that does not rely on context and subsequent sentences that build a high scoring summary. As with all local search algorithms, this algorithm is highly scalable and can easily apply to large collections of related documents, but does not guarantee global optima.

Experiments
Because summaries are intended for human consumption we focused on human evaluations. We hired workers on Amazon Mechanical Turk (AMT) to evaluate the summaries. Our evaluation addresses the following questions: (1) how do G-FLOW summaries compare against the state-of-the-art in MDS (Section 5.2)?
(2) what is G-FLOW's performance along important summarization dimensions such as coherence and redundancy (Section 5.3)? (3) how does G-FLOW perform on coverage as measured by ROUGE (Section 5.3.1)? (4) how much do the components of G-FLOW's objective function contribute to performance (Section 5.4)? (5) how do G-FLOW's summaries compare to human summaries?

Data and Systems
We evaluated the systems on the Task 2 DUC'04 multi-document summarization dataset. This dataset consists of 50 clusters of related documents, each of which contains 10 documents. Each cluster of doc-uments also includes four gold standard summaries used for evaluation. As in the DUC'04 competition, we allowed 665 bytes for each summary including spaces and punctuation. We used DUC'03 as our development set, which contains 30 document clusters, again with approximately 10 documents each.
We compared G-FLOW against four systems. The first is a recent MDS extractive summarizer, which we choose for its state-of-the-art ROUGE scores (Lin and Bilmes, 2011). 4 The second is a pipeline of Lin's system followed by a reimplementation of a state-of-the-art sentence reordering system (Li et al., 2011a). We refer to these systems as LIN and LIN-LI, respectively. This second baseline allows us to quantify the advantage of using coherence as a factor in both sentence extraction and ordering.
We also compare against the system that had the highest coherence ratings at DUC'04 (Nobata and Sekine, 2004), which we refer to as NOBATA. As this system did not preform sentence ordering on its output, we also compare against a pipeline of Nobata's system and the sentence reordering system. We refer to this system as NOBATA-LI.
Lastly, to evaluate how well the system performs against human generated summaries, we compare against the gold standard summaries provided by DUC.

Overall Summary Quality
Following (Haghighi and Vanderwende, 2009) and (Celikyilmaz and Hakkani-Tur, 2010), to compare overall summary quality, we asked AMT workers to compare two candidate system summaries. The workers first read a gold standard summary, followed by the two system summaries, and were then asked to choose the better summary from the pair. The system summaries were shown in a random order to remove any bias.
To ensure that workers provided high quality data we added two quality checks. First, we restricted to workers who have an overall approval rating of over 95% on AMT. Second, we asked the workers to briefly describe the main events of the summary. We manually filtered out work where this description was incorrect.
Six workers compared each pair of summaries. We recorded the scores for each cluster, and report three numbers: the percentages of clusters where a system is more often preferred over the other and the percentage where the two systems are tied. G-FLOW is preferred almost three times as often as LIN: G-FLOW Indifferent LIN 56% 24% 20% Next, we compared G-FLOW and LIN-LI. Sentence reordering improves performance, but G-FLOW is still overwhelmingly preferred: G-FLOW Indifferent LIN-LI 54% 24% 22% These results suggest that incorporating coherence in sentence extraction adds significant value to a summarization system. In these experiments, LIN and LIN-LI are preferred in some cases. We analyzed those summaries more carefully, and found that occasionally, G-FLOW will sacrifice a small amount of coverage for coherence, resulting in lower performance in those cases (see Section 5.3.1).
We also compared LIN and LIN-LI, and found that reordering does not improve performance by much.
LIN-LI Indifferent LIN 32% 38% 30% While the scores presented above represent comparisons between G-FLOW and a summarization system with state-of-the-art ROUGE scores, we also compared against a summarization system with state-of-the-art coherence scores -the system with the highest coherence scores from DUC'04, (Nobata and Sekine, 2004). We found that G-FLOW was again preferred: G-FLOW Indifferent NOBATA 68% 10% 22% Adding in sentence ordering again improved the scores for the comparison system somewhat: G-FLOW Indifferent NOBATA-LI 60% 20% 20% While these scores show a significant improvement over previous sytems, they do not convey how well G-FLOW compares to the gold standard -manually generated summaries. As a final experiment, we compared G-FLOW and a second, manually generated summary: While we were pleased that in 32% of the cases, Turkers either preferred G-FLOW or were indifferent, there is clearly a lot of room for improvement despite the gains reported over previous sytems.

Comparison along Summary Dimensions
A high quality summary needs to be good along several dimensions. We asked AMT workers to rate summaries using the quality questions enumerated in DUC'04 evaluation scheme. 5 These questions concern: (1) coherence, (2) useless, confusing, or repetitive text, (3) redundancy, (4) nouns, pronouns, and personal names that are not well-specified (5) entities rementioned in an overly explicit way, (6) ungrammatical sentences, and (7) formatting errors. We evaluated G-FLOW LIN-LI and NOBATA-LI against the gold standard summaries, using the same AMT scheme as in the previous section. To assess automated performance with respect to the standards set by human summaries, we also evaluated a (different) gold standard summary for each document cluster, using the same Mechanical Turk scheme as in the previous section. The 50 summaries produced by each system were evaluated by four workers. The results are shown in Figure 2.
G-FLOW was rated significantly better than LIN-LI in all categories except 'Redundancy' and significant better than NOBATA-LI on 'Coherence' and 'Referents'. The ratings for 'Coherence', 'Referents', and 'OverlyExplicit' are not surprising given G-FLOW's focus on coherence. The results for 'UselessText' may also be due to G-FLOW's focus on coherence which ideally prevents it from getting off topic. Lastly, G-FLOW may perform better on 'Grammatical' and 'Formatting' because it tends to choose longer sentences than other systems, which are less likely to be sentence segmentation errors. There may also be some bleeding from one dimension to the other -if a worker likes one summary she may score it highly for many dimensions.
Finally, somewhat surprisingly, we find G-FLOW's performance to be nearly that of human summaries. G-FLOW is rated statistically significantly lower than the gold summaries on only 'Re-  dundancy'. Given the results from the previous section, G-FLOW is likely performing worse on categories not conveyed in these scores, such as Coverage, which we examine next.

Coverage Evaluation using ROUGE
Most recent research has focused on the ROUGE evaluation, and thus implicitly on coverage of information in a summary. To estimate the coverage of G-FLOW, we compared the systems on ROUGE (Lin, 2004). We calculated ROUGE-1 scores for G-FLOW, LIN, and NOBATA. 6 As sentence ordering does not matter for ROUGE, we do not include LIN-LI or NOBATA-LI in this evaluation. Because our algorithm does not explicitly maximize coverage while LIN does, we expected G-FLOW to perform slightly worse than LIN.
The ROUGE-1 scores for G-FLOW, LIN, NO-BATA and other recent MDS systems are listed in Table 3. We also include the ROUGE-1 scores for the gold summaries (compared to the other gold summaries). G-FLOW has slightly lower scores than LIN and the gold standard summaries, but much higher scores than NOBATA. G-FLOW only scores significantly lower than LIN and the gold standard summaries.
We can conclude that good summaries have both the characteristics listed in the quality dimensions, and good coverage. The gold standard summaries outperform G-FLOW on both ROUGE scores and the quality dimension scores, and therefore, outperform G-FLOW on overall comparison. However, G-FLOW is preferred to LIN-LI in addition to NOBATA-LI indicating that its quality scores outweigh its ROUGE scores in that comparison. An improvement to G-FLOW may focus on increasing  Figure 2: Ratings for the systems. 0 is the lowest possible score and 4 is the highest possible score. G-FLOW is rated significantly higher than LIN-LI on all categories, except for 'Redundancy', and significantly higher than NOBATA-LI on 'Coherence' and 'Referents'. G-FLOW is only significantly lower than the gold standard on 'Redundancy'.
coverage while retaining strengths such as coherence.

Ablation Experiments
In this ablation study, we evaluated the contribution of the main components of G-FLOW -coherence and salience. The details of the experiments are the same as in the experiment described in Section 5.2. We first measured the importance of coherence in summary generation. This system G-FLOW-SAL is identical to the full system except that it does not include the coherence term in the objective function (see Section 4.4). The results show that coherence is very important to G-FLOW's performance: G-FLOW Indifferent G-FLOW-SAL 54% 26% 20% Similarly, we evaluated the contribution of salience. This system G-FLOW-COH does not include the salience term in the objective function: G-FLOW Indifferent G-FLOW-COH 60% 20% 20% Without salience, the system produces readable, but highly irrelevant summaries.

Agreement of Expert & AMT Workers
Because summary evaluation is a relatively complex task, we compared AMT workers' annotations with expert annotations from DUC'04. We randomly selected ten summaries from each of the seven DUC'04 annotators, and asked four Turk workers to annotate them on the DUC'04 quality questions. For each DUC'04 annotator, we selected all pairs of summaries where one summary was judged more than one point better than the other summary. We compared whether the workers (voting as in Section 5.2) likewise judged that summary better than the second summary. We found that the annotations agreed in 75% of cases. When we looked only at pairs more than two points different, the agreement was 80%. Thus, given the subjective nature of the task, we feel reasonably confident that the AMT annotations are informative, and that the dramatic preference of G-FLOW over the baseline systems is due to a substantial improvement in its summaries.

Conclusion
In this paper, we present G-FLOW, a multidocument summarization system aimed at generating coherent summaries. While previous MDS systems have focused primarily on salience and coverage but not coherence, G-FLOW generates an ordered summary by jointly optimizing coherence and salience. G-FLOW estimates coherence by using an approximate discourse graph, where each node is a sentence from the input documents and each edge represents a discourse relationship between two sentences. Manual evaluations demonstrate that G-FLOW generates substantially better summaries than a pipeline of state-of-the-art sentence selection and reordering components. ROUGE scores, which measure summary coverage, show that G-FLOW sacrifices a small amount of coverage for overall readability and coherence. Comparisons to gold standard summaries show that G-FLOW must improve in coverage to equal the quality of manually written summaries. We believe this research has applications to other areas of summarization such as update summarization and query based summarization, and we are interested in investigating these topics in future work.