Fundamental Limits of Database Alignment

Daniel Cullina; Prateek Mittal; Negar Kiyavash

doi:10.1109/ISIT.2018.8437908

Fundamental Limits of Database Alignment

Daniel Cullina, Prateek Mittal, Negar Kiyavash

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

3 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	2018 IEEE International Symposium on Information Theory, ISIT 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	651-655
Number of pages	5
ISBN (Print)	9781538647806
DOIs	https://doi.org/10.1109/ISIT.2018.8437908
State	Published - Aug 15 2018
Event	2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States Duration: Jun 17 2018 → Jun 22 2018

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2018-June
ISSN (Print)	2157-8095

Other

Other	2018 IEEE International Symposium on Information Theory, ISIT 2018
Country	United States
City	Vail
Period	6/17/18 → 6/22/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2018.8437908

Fingerprint Dive into the research topics of 'Fundamental Limits of Database Alignment'. Together they form a unique fingerprint.

Cite this

@inproceedings{2279008dea444c2c94a13b0610777ec6,

title = "Fundamental Limits of Database Alignment",

abstract = "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.",

author = "Daniel Cullina and Prateek Mittal and Negar Kiyavash",

year = "2018",

month = aug,

day = "15",

doi = "10.1109/ISIT.2018.8437908",

language = "English (US)",

isbn = "9781538647806",

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

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "651--655",

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

address = "United States",

note = "2018 IEEE International Symposium on Information Theory, ISIT 2018 ; Conference date: 17-06-2018 Through 22-06-2018",

}

Cullina, D, Mittal, P & Kiyavash, N 2018, Fundamental Limits of Database Alignment. in 2018 IEEE International Symposium on Information Theory, ISIT 2018., 8437908, IEEE International Symposium on Information Theory - Proceedings, vol. 2018-June, Institute of Electrical and Electronics Engineers Inc., pp. 651-655, 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, United States, 6/17/18. https://doi.org/10.1109/ISIT.2018.8437908

Fundamental Limits of Database Alignment. / Cullina, Daniel; Mittal, Prateek; Kiyavash, Negar.

2018 IEEE International Symposium on Information Theory, ISIT 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 651-655 8437908 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June).

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

TY - GEN

T1 - Fundamental Limits of Database Alignment

AU - Cullina, Daniel

AU - Mittal, Prateek

AU - Kiyavash, Negar

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 -