Minimum Number of Input Clues in Robust Information Retrieval

• Autorzy: Junnila V. , Laihonen T.

Identyfikatory

DOI

10.3233/FI-2016-1359

• Języki publikacji: EN

Abstrakty

EN

Information retrieval in associative memories was considered recently by Yaakobi and Bruck. In their model, a stored information unit is retrieved using input clues. In this paper, we study the problem where at most s (s ≥ 0) of the received input clues can be false and we still want to determine the sought information unit uniquely. We use a coding theoretical approach to estimate the maximum number of stored information units with respect to a given s. Moreover, optimal results for the problem are given, for example, in the infinite king grid. We also discuss the problem in the class of line graphs where a characterization and a connection to k-factors is given.

Słowa kluczowe

EN

information retrieval; associative memory; Johnson bound; k-factor; robustness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 243--256
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Junnila V.

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

autor

Laihonen T.

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

Bibliografia

• [1] Yaakobi E, Bruck J. On the Uncertainty of Information Retrieval in Associative Memories. In: Proceedings of 2012 IEEE International Symposium on Information Theory; 2012. p. 106–110.
• [2] Yaakobi E, Schwartz M, Langberg M, Bruck J. Sequence Reconstruction for Grassmann Graphs and Permutations. In: Proceedings of 2013 IEEE International Symposium on Information Theory; 2013. p. 874–878.
• [3] Junnila V, Laihonen T. Codes for information retrieval with small uncertainty. IEEE Trans Inform Theory. 2014;60(2):976–985. Available from: http://dx.doi.org/10.1109/TIT.2013.2290045. doi:10.1109/TIT.2013.2290045.
• [4] Junnila V, Laihonen T. Information retrieval with unambiguous output. Inform and Comput. 2015;242:354–368. Available from: http://dx.doi.org/10.1016/j.ic.2015.04.002. doi:10.1016/j.ic.2015.04.002.
• [5] Junnila V, Laihonen T. Information Retrieval with Varying Number of Input Clues. IEEE Trans Inform Theory. 2016;62(2):625–638. doi:10.1109/TIT.2015.2508800.
• [6] Honkala I, Laihonen T. On a new class of identifying codes in graphs. Inform Process Lett. 2007;102(2-3):92–98. doi:http://dx.doi.org/10.1016/j.ipl.2006.11.007.
• [7] Levenshtein VI. Efficient reconstruction of sequences. IEEE Trans Inform Theory. 2001;47(1):2–22. Available from: http://dx.doi.org/10.1109/18.904499. doi:10.1109/18.904499.
• [8] Fazlollahi N, Starobinski D, Trachtenberg A. Connected identifying codes. IEEE Trans Inform Theory. 2012;58(7):4814–4824. Available from: http://dx.doi.org/10.1109/TIT.2012.2191934. doi:10.1109/TIT.2012.2191934.
• [9] Ray S, Starobinski D, Trachtenberg A, Ungrangsi R. Robust location detection with sensor networks. IEEE Journal on Selected Areas in Communications. 2004 August;22(6):1016–1025. doi:10.1109/JSAC.2004.830895.
• [10] Charon I, Honkala I, Hudry O, Lobstein A. The minimum density of an identifying code in the king lattice. Discrete Math. 2004;276(1-3):95–109. 6th International Conference on Graph Theory. Available from: http://dx.doi.org/10.1016/S0012-365X(03)00306-6. doi:10.1016/S0012-365X(03)00306-6.
• [11] Lobstein A. Watching Systems, Identifying, Locating-Dominating and Discrminating Codes in Graphs, a bibliography;. Published electronically at http://perso.enst.fr/~lobstein/debutBIBidetlocdom.pdf.
• [12] MacWilliams FJ, Sloane NJA. The theory of error-correcting codes. vol. 16 of North-Holland Mathematical Library. Amsterdam: North-Holland Publishing Co.; 1977.
• [13] Brouwer AE, Cohen AM, Neumaier A. Distance-regular graphs. vol. 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Berlin: Springer-Verlag; 1989.
• [14] Brouwer AE, van Lint JH. Strongly regular graphs and partial geometries. In: Enumeration and design (Waterloo, Ont., 1982). Toronto, ON: Academic Press; 1984. p. 85–122.
• [15] Plummer MD. Graph factors and factorization: 1985–2003: a survey. Discrete Math. 2007;307(7-8): 791–821. Available from: http://dx.doi.org/10.1016/j.disc.2005.11.059. doi:10.1016/j.disc.2005.11.059.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).