S-PUT - Data Storage for Social Networks: A Socially Aware Approach - page 31

Fig. 3.1 Initial partition solutions as a result of METIS. ( a ) 100 individuals ( b ) 500 individuals

Figure 3.1 shows the partition solutions resulted from METIS as described in
Sect. 3.2.2 . When using these solutions for the initial population in the EA process
of SPUT, the results obtained in after 100 generations are plotted in Fig. 3.2 ,which
shows a significant improvement. For the case with 100 individuals Fig. 3.2 a, we
obtain twelves non-dominated solutions, all no worse than METIS. Ten out of these
solutions are substantially better than METIS solutions in terms of both the toal
read load (L

write ). Similarly for the case with 500
individuals Fig. 3.2 b, we obtain eight non-dominated solutions, five of which are
substantially better than METIS in both measures.
These results shows that METIS cannot provide good solutions to our partition-
ing problem and substantiates the effective use of EA in order to reach a set of
solutions of significantly better quality. In terms of run time, it took about 6 h to
finish the S-PUT program for the case of 500 individuals.

read ) and write load balancing (G

3.4 Notes

S-PUT is a socially aware partition scheme aimed at minimizing the total read load
and balancing the write load. S-PUT can be modified easily to work with systems
that require low read load and balanced storage load instead of balanced write