Traditionally, data compression deals with the problem of concisely representing a data source, e.g. a sequence of letters, for the purpose of eventual reproduction (either exact or approximate). In this work we are interested in the case where the goal is to answer similarity queries about the compressed sequence, i.e. to identify whether or not the original sequence is similar to a given query sequence. We study the fundamental tradeoff between the compression rate and the reliability of the queries performed on compressed data. For i.i.d. sequences, we characterize the minimal compression rate that allows query answers, that are reliable in the sense of having a vanishing false-positive probability, when false negatives are not allowed. The result is partially based on a previous work by , and the inherently typical subset lemma plays a key role in the converse proof. We then characterize the compression rate achievable by schemes that use lossy source codes as a building block, and show that such schemes are, in general, suboptimal. Finally, we tackle the problem of evaluating the minimal compression rate, by converting the problem to a sequence of convex programs that can be solved efficiently.
In the current paper we focus on discrete alphabets only, following @cite_22 . A parallel result, with complete characterization of the identification rate (and exponent) for the Gaussian case and quadratic distortion, appears in @cite_19 , @cite_5 . The identification exponent problem was originally studied in @cite_22 for the variable length case, where the resulting exponent depends on an auxiliary random variable with unbounded cardinality. A bound on the cardinality has been obtained recently in @cite_24 , where the exponent for fixed-length schemes is also found (and is different than that of the variable length schemes, unlike the identification rate -- see Prop. below). In the special case of exact match queries (i.e. identification with @math for Hamming distance), the exponent was studied in @cite_18 .
@cite_18 @cite_22 @cite_24 @cite_19 @cite_5
2039633672 2116661435 2089520644 1984810686
In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to PX × PY, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions PX and PY. In addition, the scheme achieving this exponent is universal, i.e. does not depend on PX, PY. A new coding problem is introduced for a correlated source (X sup n ,Y sup n ) sub n=1 sup spl infin . The observer of X sup n can transmit data depending on X sup n at a prescribed rate R. Based on these data the observer of Y sup n tries to identify whether for some distortion measure spl rho (like the Hamming distance) n sup -1 spl rho (X sup n ,Y sup n ) spl les d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X sup n and Y sup n are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X sup n and Y sup n are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory. The problem of performing similarity queries on compressed data is considered. We study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on compressed data. For a Gaussian source and quadratic similarity criterion, 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. 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 the identification rate is at most that of a Gaussian source with the same variance. Therefore, as with classical compression, the Gaussian source requires the largest compression rate. Moreover, a scheme is described that attains this maximal rate for any source distribution. 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 the compressed data. For a Gaussian source, we show that the 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.