Successive Refinement for High-Dimensional Identification Systems

The asymptotic tradeoff between the number of distinguishable objects and the necessary storage space (or equivalently, the search complexity) in an identification system was characterized previously. This paper extends that single-letter characterization to the multi-stage scenario whereby data is stored in increasing levels of accuracy, and depending on the number of entries, the identification is performed by utilizing part or all of the recorded bits in the database. It is also shown that a sufficient condition for a multi-stage system to achieve single-stage capacities at each stage is Markovity of the optimal test channels. Whether Markovity is also necessary remains elusive.