Identification rate, search and memory complexity trade-off: fundamental limits

F. Farhadzadeh, F.M.J. Willems

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
154 Downloads (Pure)


In an information-theoretic framework, we introduce a two-stage decoding scheme capable of achieving identification capacity to address search and memory complexities in large-scale identification systems. This twostage decoding procedure is accomplished as follows. For a given query, at the first stage, a list of cluster indices is estimated. Then, at the second stage, refinement checks are performed for all members of the clusters to produce a single index. The first result this paper presents is the achievable rate quadruple region that specifies necessary conditions that the two-stage decoding scheme should satisfy to be able to achieve the identification capacity. The rest of paper is designated to investigate various achievable rate quadruples in which the proposed twostage identification setup can reduce the search complexity with respect to conventional identification setups.
Original languageEnglish
Pages (from-to) 6173 - 6188
JournalIEEE Transactions on Information Theory
Issue number11
Publication statusPublished - 21 Sep 2016


Dive into the research topics of 'Identification rate, search and memory complexity trade-off: fundamental limits'. Together they form a unique fingerprint.

Cite this