Storage and Identification Tradeoff for Multiple Databases
The tradeoff between the storage rate and the identification capacity for multiple databases
is investigated. Noisy observations of individual feature vectors are compressed and stored in
two separate databases for two distinct groups. The queries are assumed to be (possibly random)
functions of two feature vectors (called the ancestors), one from each group. The problem of
identification of the ancestors based on a noisy query vector and the database entries is studied
from the information theoretic perspective. The fundamental tradeoff between the compression
rates and the identification rate region is studied and an achievable rate region and an outer
bound are presented.