Hierarchical Identification With Pre-Processing

We study a two-stage identification problem with pre-processing to enable efficient data retrieval and reconstruction. In the enrollment phase, users' data are stored into the database in two layers. In the identification phase an observer obtains an observation, which originates from an unknown user in the enrolled database through a memoryless channel. The observation is sent for processing in two stages. In the first stage, the observation is pre-processed, and the result is then used in combination with the stored first layer information in the database to output a list of compatible users to the second stage. Then the second step uses the information of users contained in the list from both layers and the original observation sequence to return the exact user identity and a corresponding reconstruction sequence. The rate-distortion regions are characterized for both discrete and Gaussian scenarios. Specifically, for a fixed list size and distortion level, the compression-identification trade-off in the Gaussian scenario results in three different operating cases characterized by three auxiliary functions. While the choice of the auxiliary random variable for the first layer information is essentially unchanged when the identification rate is varied, the second one is selected based on the dominant function within those three. Due to the presence of a mixture of discrete and continuous random variables, the proof for the Gaussian case is highly non-trivial, which makes a careful measure theoretic analysis necessary. In addition, we study a connection of the previous setting to a two observer identification and a related problem with a lower bound for the list size, where the latter is motivated from privacy concerns.