Transcript Power Laws, Highly Optimized Tolerance and generalized source

Power Laws, Highly Optimized
Tolerance and generalized
source coding
John Doyle, J.M. Carlson
Presented by Sumitra Ganesh
Overview


Propose an optimization problem that is
a generalization of the Data
Compression (Source coding) problem
Problem is formulated and analyzed for
3 examples : Data compression (DC),
Website layout (WWW), Forest Fires
(FF)
The PLR optimization problem
J  { pi li | li  f ( ri ),  ri  R}
1 i  N
pi
Probability of event
li
Loss/size associated with event
ri
Resource allocated to suppress the size
f  ( ri )   log( ri ),   0
f  (ri )  c(ri    1) /  ,   0
Data Compression
 0
Each source symbol – codeword of
k
p

2
Bits. i
i
2
li
1
ri  pi
li   log( pi )  ki
J   pi log( pi )
li
Web Layout




 1
The sizes are the lengths of the files
The probabilities are determined by
user interest in the files
The cost is the average delay that a
user experiences in downloading files
Resource limit is on the total number of
files
WWW contd
Crucial : The resource-loss tradeoff is determined by
li  ri
1
The resource allocation (separation if document
into files) may change influence the hit probability
for a given file.
Split the one-dimensional file into N regions of
equal size and with uniform access probability

Forest Fires





 1
Two-dimensional problem
The losses are the burned areas
The probabilities are determined by the
probability of sparks
The cost is the average timber lost in
fires
Resource is the density of firebreaks
etc.
Heavy tailed CDFs
Comments



Generalized framework : not clear about
its applicability
The average statistics seem to obey
power laws even though the individual
websites were not optimally designed
(Why?)
The three examples are explained well