On universal coding of unordered data

Lav R. Varshney, Vivek K. Goyal

Research output: Chapter in Book/Report/Conference proceedingConference contribution


There are several applications in information transfer and storage where the order of source letters is irrelevant at the destination. For these source-destination pairs, multiset communication rather than the more difficult task of sequence communication may be performed. In this work, we study universal multiset communication. For classes of countable-alphabet sources that meet Kieffer's condition for sequence communication, we present a scheme that universally achieves a rate of n + o(n) bits per multiset letter for multiset communication. We also define redundancy measures that are normalized by the logarithm of the multiset size rather than per multiset letter and show that these redundancy measures cannot be driven to zero for the class of finite-alphabet memoryless multisets. This further implies that finite-alphabet memoryless multisets cannot be encoded universally with vanishing fractional redundancy.

Original languageEnglish (US)
Title of host publication2007 Information Theory and Applications Workshop, Conference Proceedings, ITA
Number of pages5
StatePublished - 2007
Externally publishedYes
Event2007 Information Theory and Applications Workshop, ITA - San Diego, CA, United States
Duration: Jan 29 2007Feb 2 2007

Publication series

Name2007 Information Theory and Applications Workshop, Conference Proceedings, ITA


Other2007 Information Theory and Applications Workshop, ITA
Country/TerritoryUnited States
CitySan Diego, CA

ASJC Scopus subject areas

  • Information Systems
  • Information Systems and Management


Dive into the research topics of 'On universal coding of unordered data'. Together they form a unique fingerprint.

Cite this