Paper Info
Title
Fundamental limits of identification: Identification rate, search and memory complexity trade-off
Abstract
In this paper, we introduce a new generalized scheme to resolve the trade-off between the identification rate, search and memory complexities in large-scale identification systems. The main contribution of this paper consists in a special database organization based on assigning entries of a database to a set of predefined and possibly overlapping clusters, where the cluster representative points are generated based on statistics of both entries of the database and queries. The decoding procedure is accomplished in two stages: At the first stage, a list of clusters related to the query is estimated, then refinement checks are performed to all members of these clusters to produce a unique index at the second stage. The proposed scheme generalizes several practical searching in identification systems as well as makes it possible to approach a new achievable region of search- memory complexity trade-off.
Year
DOI
Venue
2013
10.1109/ISIT.2013.6620427
ISIT
Keywords
Field
DocType
decoding procedure,database management systems,pattern clustering,identification,statistical analysis,search-memory complexity trade-off,overlapping clusters,search problems,biometrics (access control),identification rate,database organization,refinement checks,decoding,large-scale identification systems,search complexity trade-off,cluster representative points,markov processes,indexes
Data mining,Cluster (physics),Biometrics access control,Pattern clustering,Computer science,Theoretical computer science,Decoding methods,Statistical analysis
Conference
ISSN
Citations 
PageRank 
2157-8095
4
0.44
References 
Authors
7
3
Name
Order
Citations
PageRank
Farzad Farhadzadeh16310.01
Frans M. J. Willems235595.64
Sviatoslav Voloshynovskiy377380.94