DocumentCode :
1042367
Title :
The connection between information theory and object search in networks
Author :
Huang, Hong
Author_Institution :
Klipsch Sch. of Electr. & Comput. Eng., New Mexico State Univ., Las Cruces, NM
Volume :
12
Issue :
12
fYear :
2008
fDate :
12/1/2008 12:00:00 AM
Firstpage :
906
Lastpage :
908
Abstract :
This paper aims to establish a connection between information theory and object search in networks. We make two contributions:1) Using information theoretical arguments, we 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. 2) Using the analogy between search sequences and data compression and coding, we 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.
Keywords :
data compression; encoding; search problems; table lookup; Shannon code; coding; data compression; information theoretical arguments; lookup table; nonuniform lookup distributions; object search; search sequences; Costs; Data compression; Entropy; Information theory; Peer to peer computing; Random variables; Routing; Scalability; Search methods; Table lookup; Information theory, coding, search methods;
fLanguage :
English
Journal_Title :
Communications Letters, IEEE
Publisher :
ieee
ISSN :
1089-7798
Type :
jour
DOI :
10.1109/LCOMM.2008.081166
Filename :
4720247
Link To Document :
بازگشت