Identification over multiple databases

Deniz Gündüz; Ertem Tuncel; Andrea Goldsmith; H. Vincent Poor

doi:10.1109/ISIT.2009.5205930

Identification over multiple databases

Deniz Gündüz, Ertem Tuncel, Andrea Goldsmith, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

The tradeoff between storage and identification rates for multiple databases is investigated from an information theoretic perspective. In the assumed model, noisy observations of feature vectors of two distinct groups, called the ancestors, are compressed and stored in two separate databases. When queried with a noisy observation of a (possibly random) function of two randomly selected ancestors (one from each group), the system is required to correctly identify the ancestors with high probability. Single-letter inner and outer bounds are presented on the set of achievable rate points, which identify a tradeoff between the compression rates and the identification rate region: the lower the compression rates for storage, the larger the rate region achievable for identification.

Original language	English (US)
Title of host publication	2009 IEEE International Symposium on Information Theory, ISIT 2009
Pages	2311-2315
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2009.5205930
State	Published - 2009
Event	2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of Duration: Jun 28 2009 → Jul 3 2009

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8102

Other

Other	2009 IEEE International Symposium on Information Theory, ISIT 2009
Country/Territory	Korea, Republic of
City	Seoul
Period	6/28/09 → 7/3/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2009.5205930

Cite this

@inproceedings{470ad777fd6645f9ac735c322cebe333,

title = "Identification over multiple databases",

abstract = "The tradeoff between storage and identification rates for multiple databases is investigated from an information theoretic perspective. In the assumed model, noisy observations of feature vectors of two distinct groups, called the ancestors, are compressed and stored in two separate databases. When queried with a noisy observation of a (possibly random) function of two randomly selected ancestors (one from each group), the system is required to correctly identify the ancestors with high probability. Single-letter inner and outer bounds are presented on the set of achievable rate points, which identify a tradeoff between the compression rates and the identification rate region: the lower the compression rates for storage, the larger the rate region achievable for identification.",

author = "Deniz G{\"u}nd{\"u}z and Ertem Tuncel and Andrea Goldsmith and Poor, {H. Vincent}",

year = "2009",

doi = "10.1109/ISIT.2009.5205930",

language = "English (US)",

isbn = "9781424443130",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "2311--2315",

booktitle = "2009 IEEE International Symposium on Information Theory, ISIT 2009",

note = "2009 IEEE International Symposium on Information Theory, ISIT 2009 ; Conference date: 28-06-2009 Through 03-07-2009",

}

Gündüz, D, Tuncel, E, Goldsmith, A & Poor, HV 2009, Identification over multiple databases. in 2009 IEEE International Symposium on Information Theory, ISIT 2009., 5205930, IEEE International Symposium on Information Theory - Proceedings, pp. 2311-2315, 2009 IEEE International Symposium on Information Theory, ISIT 2009, Seoul, Korea, Republic of, 6/28/09. https://doi.org/10.1109/ISIT.2009.5205930

TY - GEN

T1 - Identification over multiple databases

AU - Gündüz, Deniz

AU - Tuncel, Ertem

AU - Goldsmith, Andrea

AU - Poor, H. Vincent

PY - 2009

Y1 - 2009

N2 - The tradeoff between storage and identification rates for multiple databases is investigated from an information theoretic perspective. In the assumed model, noisy observations of feature vectors of two distinct groups, called the ancestors, are compressed and stored in two separate databases. When queried with a noisy observation of a (possibly random) function of two randomly selected ancestors (one from each group), the system is required to correctly identify the ancestors with high probability. Single-letter inner and outer bounds are presented on the set of achievable rate points, which identify a tradeoff between the compression rates and the identification rate region: the lower the compression rates for storage, the larger the rate region achievable for identification.

AB - The tradeoff between storage and identification rates for multiple databases is investigated from an information theoretic perspective. In the assumed model, noisy observations of feature vectors of two distinct groups, called the ancestors, are compressed and stored in two separate databases. When queried with a noisy observation of a (possibly random) function of two randomly selected ancestors (one from each group), the system is required to correctly identify the ancestors with high probability. Single-letter inner and outer bounds are presented on the set of achievable rate points, which identify a tradeoff between the compression rates and the identification rate region: the lower the compression rates for storage, the larger the rate region achievable for identification.

UR - http://www.scopus.com/inward/record.url?scp=70449512476&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449512476&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2009.5205930

DO - 10.1109/ISIT.2009.5205930

M3 - Conference contribution

AN - SCOPUS:70449512476

SN - 9781424443130

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2311

EP - 2315

BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009

T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009

Y2 - 28 June 2009 through 3 July 2009

ER -

Identification over multiple databases

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this