The Connection Between Information Theory and Object Search in Networks

This paper aims to establish a connection between information theory and object search in networks. The authors make two contributions: using information theoretical arguments, they establish fundamental lower bounds on lookup table sizes and search step numbers. These bounds generalize those derived previously and can deal with non-uniform lookup distributions and object popularities. Using the analogy between search sequences and data compression and coding, they propose a distributed implementation of Shannon code that can reduce the expected length of search sequences to an arbitrarily small value at the cost of at most doubling the table sizes.