Title :
Efficient two stage decoding scheme to achieve content identification capacity
Author :
Farhadzadeh, Farzad ; Ke Sun ; Fredowsi, Sohrab
Author_Institution :
Comput. Sci. Dept., Univ. of Geneva, Geneva, Switzerland
Abstract :
We introduce a scheme to address the trade-off between the identification rate, search and memory complexities in large-scale identification systems. We use a special database organization by assigning database entries to a set of possibly overlapping clusters. The clusters are generated based on statistics of both database entries and queries. The decoding procedure is accomplished in two stages. First, a list of clusters related to the query is detected. Then, refinement checks are performed on members of the detected clusters to produce a unique index. We investigate the minimum achievable search complexity for binary symmetric sources.
Keywords :
computational complexity; data compression; decoding; pattern clustering; query processing; binary symmetric sources; content identification capacity; database entry statistics; database organization; identification rate; memory complexity; overlapping cluster set; query statistics; refinement check; search complexity; two stage decoding scheme; unique index; Complexity theory; Decoding; Indexes; Markov processes; Minimization; Vectors; Content identification; clustering; identification capacity;
Conference_Titel :
Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on
Conference_Location :
Florence
DOI :
10.1109/ICASSP.2014.6854315