  The problem of performing similarity queries on compressed data is
considered. We focus on the quadratic similarity measure, and study the
fundamental tradeoff between compression rate, sequence length, and reliability
of queries performed on compressed data. For a Gaussian source, we show that
queries can be answered reliably if and only if the compression rate exceeds a
given threshold - the identification rate - which we explicitly characterize.
Moreover, when compression is performed at a rate greater than the
identification rate, responses to queries on the compressed data can be made
exponentially reliable. We give a complete characterization of this exponent,
which is analogous to the error and excess-distortion exponents in channel and
source coding, respectively.
  For a general source we prove that, as with classical compression, the
Gaussian source requires the largest compression rate among sources with a
given variance. Moreover, a robust scheme is described that attains this
maximal rate for any source distribution.
