A Caltech Library Service

Functional Compression Through Graph Coloring

Doshi, Vishal and Shah, Devavrat and Médard, Muriel and Effros, Michelle (2010) Functional Compression Through Graph Coloring. IEEE Transactions on Information Theory, 56 (8). pp. 3901-3917. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Motivated by applications to sensor networks and privacy preserving databases, we consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary but fixed deterministic function of those sources can be computed given the compressed data from each source. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder; 2) under a special condition, lossless computation where both sources are separately encoded; and 3) lossy computation where one source is available at the decoder. For all of these instances, we present a layered architecture for distributed coding: first preprocess data at each source using colorings of certain characteristic graphs and then use standard distributed source coding (a la Slepian and Wolfs scheme) to compress them. For the first instance, our results extend the approach developed by Orlitsky and Roche (2001) in the sense that our scheme requires simpler structure of coloring rather than independent sets as in the previous case. As an intermediate step to obtain these results, we obtain an asymptotic characterization of conditional graph coloring for an OR product of graphs generalizing a result of Korner (1973), which should be of interest in its own right.

Item Type:Article
Related URLs:
Additional Information:© 2010 IEEE. Manuscript received July 15, 2008; revised February 13, 2010. Date of current version July 14, 2010. This work was done when V. Doshi was with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology. This work was supported in part by a Sandia Fellowship and a DARPA ITMANET grant. This work was presented in part at the 2006 Asilomar Conference on Signals, Systems, and Computers, Monterey, CA, the 2007 Data Compression Conference, Snowbird, UT, and the 2007 International Symposium on Information Theory, Nice, France. The authors would like to thank Dr. A. Heller for providing the Blue Force Tracking data used in our simulations. The authors would also like to thank anonymous reviewers for their detailed feedback which has improved the readability of this work.
Funding AgencyGrant Number
Sandia FellowshipUNSPECIFIED
Defense Advanced Research Projects Agency - Information Theory for Mobile Ad-Hoc Networks (DARPA ITMANET)UNSPECIFIED
Subject Keywords:Distributed computing, distributed source coding, functional compression
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11476662
Issue or Number:8
Record Number:CaltechAUTHORS:20101011-105632282
Persistent URL:
Official Citation:Doshi, V.; Shah, D.; Médard, M.; Effros, M.; , "Functional Compression Through Graph Coloring," Information Theory, IEEE Transactions on , vol.56, no.8, pp.3901-3917, Aug. 2010 doi: 10.1109/TIT.2010.2050835
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20369
Deposited By: Tony Diaz
Deposited On:23 Nov 2010 19:41
Last Modified:03 Oct 2019 02:09

Repository Staff Only: item control page