NDLI: Compression for Similarity Identification: Computing the Error Exponent

Content Provider	IEEE Xplore Digital Library
Author	Ingber, A. Weissman, T.
Copyright Year	2015
Description	Author affiliation: Stanford Univ., Stanford, CA, USA (Weissman, T.) \|\| Yahoo! Labs., Sunnyvale, CA, USA (Ingber, A.)
Abstract	We consider the problem of compressing discrete memory less data sequences for the purpose of similarity identification, first studied by Ahlswede et al. (1997). In this setting, a source sequence is compressed, where the goal is to be able to identify whether the original source sequence is similar to another given sequence (called the query sequence). There is no requirement that the source will be reproducible from the compressed version. In the case where no false negatives are allowed, a compression scheme is said to be reliable if the probability of error (false positive) vanishes as the sequence length grows. The minimal compression rate in this sense, which is the parallel of the classical rate distortion function, is called the identification rate. The rate at which the error probability vanishes is measured by its exponent, called the identification exponent (which is the analog of the classical excess distortion exponent). While an information-theoretic expression for the identification exponent was found in past work, it is uncomputable due to a dependency on an auxiliary random variable with unbounded cardinality. The main result of this paper is a cardinality bound on the auxiliary random variable in the identification exponent, thereby making the quantity computable (solving the problem that was left open by Ahlswede et al.). The new proof technique relies on the fact that the Lagrangian in the optimization problem (in the expression for the exponent) can be decomposed by coordinate (of the auxiliary random variable). Then a standard Caratheodory - style argument completes the proof.
Starting Page	413
Ending Page	422
File Size	250164
Page Count	10
File Format	PDF
ISBN	9781479984305
ISSN	10680314
DOI	10.1109/DCC.2015.75
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-04-07
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Random variables Optimization Standards Databases Error probability Distortion measurement Probability distribution
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compression Schemes for Similarity Queries

Compression for similarity identification: Fundamental limits

Optimal quantizer performance and the Wasserstein distortion

Coding for computing

Robust coding schemes for distributed sensor networks with unreliable sensors

Algorithms for Computing Joint Compression and Private Watermarking Rate Regions

Probability of error metrics for best-basis selection

Identification via compressed data

Identification via compressed data

Compression for Similarity Identification: Computing the Error Exponent

Similar Documents

Compression Schemes for Similarity Queries

Compression for similarity identification: Fundamental limits

Optimal quantizer performance and the Wasserstein distortion

Coding for computing

Robust coding schemes for distributed sensor networks with unreliable sensors

Algorithms for Computing Joint Compression and Private Watermarking Rate Regions

Probability of error metrics for best-basis selection

Identification via compressed data

Identification via compressed data

Compression for Similarity Identification: Computing the Error Exponent