O'Reilly logo

Computation and Storage in the Cloud by Jinjun Chen, Yun Yang, Dong Yuan

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Appendix B

Proofs of Theorems, Lemmas and Corollaries

Theorem 5.1

Given a linear DDG with data sets {d1, d2, , dn}, the length of Pmin<ds, de> of its CTT is the minimum cost rate for storing the data sets in the DDG, and the corresponding storage strategy is to store the data sets that Pmin<ds, de> traverses.

Proof of Theorem 5.1: First, there is a one-to-one mapping between the storage strategies of the DDG and the paths from ds to de in the CTT. Given any storage strategy of the DDG, we can find an order of these stored data sets, since the DDG is linear. Then, we can find the exact path in the CTT that has traversed all these stored data sets. Similarly, given any path from ds to de in the CTT, we can find the data sets it has traversed, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required