TY - GEN
T1 - Fundamental Limits of Database Alignment
AU - Cullina, Daniel
AU - Mittal, Prateek
AU - Kiyavash, Negar
N1 - Funding Information:
This work was supported in part by NSF grants CCF 16-19216, CCF 16-17286, and CNS 15-53437.
Funding Information:
ACKNOWLEDGEMENT This work was supported in part by NSF grants CCF 16-19216, CCF 16-17286, and CNS 15-53437.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/15
Y1 - 2018/8/15
N2 - We consider the problem of aligning a pair of databases with correlated entries. We introduce a new measure of correlation in a joint distribution that we call cycle mutual information. This measure has operational significance: it determines whether exact recovery of the correspondence between database entries is possible for any algorithm. Additionally, there is an efficient algorithm for database alignment that achieves this information theoretic threshold.
AB - We consider the problem of aligning a pair of databases with correlated entries. We introduce a new measure of correlation in a joint distribution that we call cycle mutual information. This measure has operational significance: it determines whether exact recovery of the correspondence between database entries is possible for any algorithm. Additionally, there is an efficient algorithm for database alignment that achieves this information theoretic threshold.
UR - http://www.scopus.com/inward/record.url?scp=85052443314&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052443314&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2018.8437908
DO - 10.1109/ISIT.2018.8437908
M3 - Conference contribution
AN - SCOPUS:85052443314
SN - 9781538647806
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 651
EP - 655
BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -