Functional Compression Through Graph Coloring
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 give...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/67497 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826190371289300992 |
|---|---|
| author | Doshi, Vishal Shah, Devavrat Medard, Muriel Effros, Michelle |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Doshi, Vishal Shah, Devavrat Medard, Muriel Effros, Michelle |
| author_sort | Doshi, Vishal |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:39:16Z |
| format | Article |
| id | mit-1721.1/67497 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:39:16Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/674972022-09-23T13:35:33Z Functional Compression Through Graph Coloring Doshi, Vishal Shah, Devavrat Medard, Muriel Effros, Michelle Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Medard, Muriel Medard, Muriel Doshi, Vishal Shah, Devavrat 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. United States. Defense Advanced Research Projects Agency (DARPA ITMANET grant) Sandia National Laboratories (Fellowship) 2011-12-09T19:31:19Z 2011-12-09T19:31:19Z 2010-08 2010-02 Article http://purl.org/eprint/type/JournalArticle 0018-9448 http://hdl.handle.net/1721.1/67497 Doshi, V. et al. “Functional Compression Through Graph Coloring.” Information Theory, IEEE Transactions on 56.8 (2010): 3901-3917.© 2010 IEEE. https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/tit.2010.2050835 IEEE Transactions on Information Theory Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Doshi, Vishal Shah, Devavrat Medard, Muriel Effros, Michelle Functional Compression Through Graph Coloring |
| title | Functional Compression Through Graph Coloring |
| title_full | Functional Compression Through Graph Coloring |
| title_fullStr | Functional Compression Through Graph Coloring |
| title_full_unstemmed | Functional Compression Through Graph Coloring |
| title_short | Functional Compression Through Graph Coloring |
| title_sort | functional compression through graph coloring |
| url | http://hdl.handle.net/1721.1/67497 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT doshivishal functionalcompressionthroughgraphcoloring AT shahdevavrat functionalcompressionthroughgraphcoloring AT medardmuriel functionalcompressionthroughgraphcoloring AT effrosmichelle functionalcompressionthroughgraphcoloring |