Information retrieval and the average number of input clues

Tero Laihonen

doi:10.3934/amc.2017013

Article Contents

2017, Volume 11, Issue 1: 203-223. Doi: 10.3934/amc.2017013

This issue Previous Article More constructions of near optimal codebooks associated with binary sequences Next Article On defining generalized rank weights

Information retrieval and the average number of input clues

Tero Laihonen

Department of Mathematics and Statistics, University of Turku, FI-20014 Turku, Finland

Received: August 2015

Revised: January 2016

Published: May 2017

Abstract / Introduction Full Text(HTML) Figure(7) Related Papers Cited by

Abstract

Information retrieval in an associative memory was introduced in a recent paper by Yaakobi and Bruck. The associative memory is represented by a graph where the vertices correspond to the stored information units and the edges to associations between them. The goal is to find a stored information unit in the memory using input clues. In this paper, we study the minimum average number of input clues needed to find the sought information unit in the infinite king grid. We provide a geometric approach to determine the minimum number of input clues. Using this approach we are able to find optimal results and bounds on the number of input clues. The model by Yaakobi and Bruck has also applications to sensor networks monitoring and Levenshtein's sequence reconstruction problem.

Keywords:

Mathematics Subject Classification: Primary: 68P20, 68R05; Secondary: 94B27, 05B30.

Citation:

Full Text(HTML)

Figure 1. The code consists of the black vertices

Download: Full-size image PowerPoint slide

Figure 2. (a) The example, (b) All the vertices form $B_1({\bf{u}})$. The gray nodes belong to $\mathcal{S}_1^1({\bf{u}})$ and the white ones to $L_1^1({\bf{u}})$

Download: Full-size image PowerPoint slide

Figure 3. Part of the infinite king grid and the patterns $H$, $H'$, $J$ and $J'$ for $t=1.$ The code $C$ consists of the black vertices.

Download: Full-size image PowerPoint slide

Figure 4. In these figures, the black nodes are codewords, white nodes are non-codewords and the gray ones are unknown: (a) The configuration (b) The rule R2

Download: Full-size image PowerPoint slide

Figure 5. Optimal codes giving an $\mathcal{SAM}_\mathcal{K}(1;N)$ (a) for $N=3$ (b) for $N=2$.

Download: Full-size image PowerPoint slide

Figure 6. In these figures, the black nodes are codewords, white nodes are non-codewords and the gray ones are unknown: (a) The first configuration (b) The second configuration

Download: Full-size image PowerPoint slide

Figure 7. In these figures, a node with 3 in it belongs to $Z_{\ge 3}$: (a) The rule R2 (b) The rule R3

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	D. Auger and I. Honkala, Watching systems in the king grid, Graphs Combin., 29 (2013), 333-347. doi: 10.1007/s00373-011-1124-0.
[2]	Y. Ben-Haim, S. Gravier, A. Lobstein and J. Moncel, Adaptive identification in tori in the king lattice, Electron. J. Combin. , 18 (2011), 116.
[3]	I. Charon, I. Honkala, O. Hudry and A. Lobstein, The minimum density of an identifying code in the king lattice, Discrete Math., 276 (2004), 95-109. doi: 10.1016/S0012-365X(03)00306-6.
[4]	G. Cohen, I. Honkala, A. Lobstein and G. Zémor, On codes identifying vertices in the twodimensional square lattice with diagonals, IEEE Trans. Comp., 50 (2001), 174-176. doi: 10.1109/12.908992.
[5]	N. Fazlollahi, D. Starobinski and A. Trachtenberg, Connected identifying codes, IEEE Trans. Inform. Theory, 58 (2012), 4814-4824. doi: 10.1109/TIT.2012.2191934.
[6]	F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, European J. Combin., 32 (2011), 628-638. doi: 10.1016/j.ejc.2011.01.002.
[7]	S. Gravier, M. Kovše, M. Mollard, J. Moncel and A. Parreau, New results on variants of covering codes in Sierpiński graphs, Des. Codes Cryptogr., 69 (2013), 181-188. doi: 10.1007/s10623-012-9642-1.
[8]	V. Junnila and T. Laihonen, Codes for information retrieval with small uncertainty, IEEE Trans. Inform. Theory, 60 (2014), 976-985. doi: 10.1109/TIT.2013.2290045.
[9]	V. Junnila and T. Laihonen, Information retrieval with unambiguous output, Inform. Comput., 242 (2015), 354-368. doi: 10.1016/j.ic.2015.04.002.
[10]	V. Junnila and T. Laihonen, Information retrieval with varying number of input clues, IEEE Trans. Inform. Theory, 62 (2016), 1-14. doi: 10.1109/TIT.2015.2508800.
[11]	M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44 (1998), 599-611. doi: 10.1109/18.661507.
[12]	S. Ray, D. Starobinski, A. Trachtenberg and R. Ungrangsi, Robust location detection with sensor networks, IEEE J. Sel. Areas Commun., 22 (2004), 1016-1025. doi: 10.1109/JSAC.2004.830895.
[13]	K. Thulasiraman, M. Su, Y. Xiao and X. Hu, Vertex identifying codes for fault isolation in communication networks, in Proc. Int. Conf. Discrete Math. Appl. (ICDM 2006), Bangalore, 2006.
[14]	E. Yaakobi and J. Bruck, On the uncertainty of information retrieval in associative memories, in Proceedings of 2012 IEEE International Symposium on Information Theory, 2012,106-110. doi: 10.1109/ISIT.2012.6283016.
[15]	E. Yaakobi, M. Schwartz, M. Langberg and J. Bruck, Sequence reconstruction for Grassmann graphs and permutations, in Proc. 2013 IEEE Int. Symp. Inf. Theory, 2013,874-878. doi: 10.1109/ISIT.2013.6620351.