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

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.