Social Locality in Data Storage - Data Storage for Social Networks: A Socially Aware Approach - page 18

which can be re-written as

0 1

X

N

X

N

X

M

X

N

X

M

X

N

X

M

@ 1 C A

read D

.1 p is /p js .1 p is / L r i e ij r i p js e ij p it x jt

i D 1 j D 1 s D 1 i D 1 s D 1 j D 1 t D 1

„ ƒ‚ …

„ ƒ‚ …

read
0

L

(2.5)

(derived using the equality P s D 1 p is

D

1 8 i

2

read
0

represents
the total read load in the case without replication (i.e., X D 0)and represents
the read load reduction offered by the replication scheme X . Letting s i

Œ1; N ). Note that L

denote the

=1andp is =0 8 s

¤

primary server of user i , i.e., p is i s i , we can simplify as

follows

N M N M

X X X X

D r i .1 p is / p js e ij p it x jt

i D 1 s D 1 j D 1 t D 1

X

N

X

M

X

N

D r i p js e ij x js i

i D 1 s ¤ s i j D 1

N N M

X X X

D r i x js i e ij p js

i D 1 j D 1

s ¤ s i

X

N

X

N

D r i x js i e ij .1 p js i /

i D 1 j D 1

X

N

X

N

X

N

X

N

D r i x js i e ij r i x js i e ij p js i

i D 1 j D 1 i D 1 j D 1

X

N

X

N

D

r i x js i e ij (because x js i and p js i cannot both be 1)

i D 1 j D 1

X

N

X

N

X

M

D r i p is x js e ij

i D 1 j D 1 s D 1

X

N

X

M

X

N

D x js r i p is e ij

j D 1 s D 1 i D 1

N M N

X X X

D x is r j p js e ji :

i D 1 s D 1 j D 1