Trading-off performance and complexity in identification problem
Taras Holotyak, Slava Voloshynovskiy, Oleksiy Koval, Fokko Beekhof · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2011
In this paper, we consider an information-theoretic formulation of the content identification under search complexity constrain. The proposed framework is based on soft fingerprinting, i.e., joint consideration of sign and magnitude of fingerprint coefficients. The fingerprint magnitude is analyzed in the scope of communications with side information that results in channel decomposition, where all bits of fingerprints are classified to be communicated via several channels with distinctive characteristics. We demonstrate that under certain conditions the channels with low identification capacity can be neglected without considerable rate loss. This is a basis for the analysis of fast identification techniques trading-off theoretical performance in terms of achievable rate and search complexity.