Fundamental limits of identification : identification rate, search and memory complexity trade-off

F. Farhadzadeh, F.M.J. Willems, S. Voloshynovskiy

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


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.
Original languageEnglish
Title of host publication2013 IEEE International Symposium on Information Theory (ISIT)
Place of PublicationIstanbul, Turkey
PublisherInstitute of Electrical and Electronics Engineers
Publication statusPublished - 2013


Dive into the research topics of 'Fundamental limits of identification : identification rate, search and memory complexity trade-off'. Together they form a unique fingerprint.

Cite this