February  2017, 11(1): 203-223. doi: 10.3934/amc.2017013

Information retrieval and the average number of input clues

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

Received  August 2015 Revised  January 2016 Published  February 2017

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.

Citation: Tero Laihonen. Information retrieval and the average number of input clues. Advances in Mathematics of Communications, 2017, 11 (1) : 203-223. doi: 10.3934/amc.2017013
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. Google Scholar

[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. Google Scholar

[3]

I. CharonI. HonkalaO. 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. Google Scholar

[4]

G. CohenI. HonkalaA. 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. Google Scholar

[5]

N. FazlollahiD. Starobinski and A. Trachtenberg, Connected identifying codes, IEEE Trans. Inform. Theory, 58 (2012), 4814-4824. doi: 10.1109/TIT.2012.2191934. Google Scholar

[6]

F. FoucaudE. GuerriniM. KovšeR. NaserasrA. 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. Google Scholar

[7]

S. GravierM. KovšeM. MollardJ. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

M. G. KarpovskyK. 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. Google Scholar

[12]

S. RayD. StarobinskiA. 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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

show all references

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. Google Scholar

[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. Google Scholar

[3]

I. CharonI. HonkalaO. 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. Google Scholar

[4]

G. CohenI. HonkalaA. 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. Google Scholar

[5]

N. FazlollahiD. Starobinski and A. Trachtenberg, Connected identifying codes, IEEE Trans. Inform. Theory, 58 (2012), 4814-4824. doi: 10.1109/TIT.2012.2191934. Google Scholar

[6]

F. FoucaudE. GuerriniM. KovšeR. NaserasrA. 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. Google Scholar

[7]

S. GravierM. KovšeM. MollardJ. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[11]

M. G. KarpovskyK. 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. Google Scholar

[12]

S. RayD. StarobinskiA. 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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

Figure 1.  The code consists of the black vertices
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}})$
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.
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
Figure 5.  Optimal codes giving an $\mathcal{SAM}_\mathcal{K}(1;N)$ (a) for $N=3$ (b) for $N=2$.
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
Figure 7.  In these figures, a node with 3 in it belongs to $Z_{\ge 3}$: (a) The rule R2 (b) The rule R3
[1]

Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid. Advances in Mathematics of Communications, 2014, 8 (1) : 35-52. doi: 10.3934/amc.2014.8.35

[2]

Mikko Pelto. On $(r,\leq 2)$-locating-dominating codes in the infinite king grid. Advances in Mathematics of Communications, 2012, 6 (1) : 27-38. doi: 10.3934/amc.2012.6.27

[3]

Jianhong Wu, Ruyuan Zhang. A simple delayed neural network with large capacity for associative memory. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 851-863. doi: 10.3934/dcdsb.2004.4.851

[4]

K. L. Mak, J. G. Peng, Z. B. Xu, K. F. C. Yiu. A novel neural network for associative memory via dynamical systems. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 573-590. doi: 10.3934/dcdsb.2006.6.573

[5]

Jinchao Xu. The single-grid multilevel method and its applications. Inverse Problems & Imaging, 2013, 7 (3) : 987-1005. doi: 10.3934/ipi.2013.7.987

[6]

Yanfei Wang, Qinghua Ma. A gradient method for regularizing retrieval of aerosol particle size distribution function. Journal of Industrial & Management Optimization, 2009, 5 (1) : 115-126. doi: 10.3934/jimo.2009.5.115

[7]

Colleen M. Swanson, Douglas R. Stinson. Extended combinatorial constructions for peer-to-peer user-private information retrieval. Advances in Mathematics of Communications, 2012, 6 (4) : 479-497. doi: 10.3934/amc.2012.6.479

[8]

Frédéric Sur, Michel Grédiac. Towards deconvolution to enhance the grid method for in-plane strain measurement. Inverse Problems & Imaging, 2014, 8 (1) : 259-291. doi: 10.3934/ipi.2014.8.259

[9]

Hao-Chun Lu. An efficient convexification method for solving generalized geometric problems. Journal of Industrial & Management Optimization, 2012, 8 (2) : 429-455. doi: 10.3934/jimo.2012.8.429

[10]

Cheng Wang. Convergence analysis of the numerical method for the primitive equations formulated in mean vorticity on a Cartesian grid. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1143-1172. doi: 10.3934/dcdsb.2004.4.1143

[11]

Jiaping Yu, Haibiao Zheng, Feng Shi, Ren Zhao. Two-grid finite element method for the stabilization of mixed Stokes-Darcy model. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 387-402. doi: 10.3934/dcdsb.2018109

[12]

Yigui Ou, Yuanwen Liu. A memory gradient method based on the nonmonotone technique. Journal of Industrial & Management Optimization, 2017, 13 (2) : 857-872. doi: 10.3934/jimo.2016050

[13]

R. M. Yulmetyev, E. V. Khusaenova, D. G. Yulmetyeva, P. Hänggi, S. Shimojo, K. Watanabe, J. Bhattacharya. Dynamic effects and information quantifiers of statistical memory of MEG's signals at photosensitive epilepsy. Mathematical Biosciences & Engineering, 2009, 6 (1) : 189-206. doi: 10.3934/mbe.2009.6.189

[14]

Joseph Bayara, André Conseibo, Artibano Micali, Moussa Ouattara. Derivations in power-associative algebras. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1359-1370. doi: 10.3934/dcdss.2011.4.1359

[15]

Luca Dieci, Cinzia Elia. Smooth to discontinuous systems: A geometric and numerical method for slow-fast dynamics. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2935-2950. doi: 10.3934/dcdsb.2018112

[16]

Melody Alsaker, Sarah Jane Hamilton, Andreas Hauptmann. A direct D-bar method for partial boundary data electrical impedance tomography with a priori information. Inverse Problems & Imaging, 2017, 11 (3) : 427-454. doi: 10.3934/ipi.2017020

[17]

Shuai Ren, Tao Zhang, Fangxia Shi. Characteristic analysis of carrier based on the filtering and a multi-wavelet method for the information hiding. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1291-1299. doi: 10.3934/dcdss.2015.8.1291

[18]

Wen Chen, Song Wang. A finite difference method for pricing European and American options under a geometric Lévy process. Journal of Industrial & Management Optimization, 2015, 11 (1) : 241-264. doi: 10.3934/jimo.2015.11.241

[19]

Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems & Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267

[20]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (8)
  • HTML views (3)
  • Cited by (0)

Other articles
by authors

[Back to Top]