Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm
DOI:
https://doi.org/10.51408/1963-0030Keywords:
NN search, Best match, Hash-coding schema, Perfect Codes, Uniformly Packed code, Quasi-perfect codesAbstract
The Nearest Neighbor search algorithm considered in this paper is well known (Elias algorithm). It uses error-correcting codes and constructs appropriate hash-coding schemas. These schemas preprocess the data in the form of lists. Each list is contained in some sphere, centered at a code-word. The algorithm is considered for the cases of perfect codes, so the spheres and, consequently, the lists do not intersect. As such codes exist for the limited set of parameters, the algorithm is considered for some other generalizations of perfect codes, and then the same data point may be contained in different lists. A formula of time complexity of the algorithm is obtained for these cases, using coset weight structures of the mentioned codes
References
D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, second edition, Eddison-Wesley, 1998.
R. Rivest, “On the optimality of Elias’s algorithm for performing best-match searches”, Information Processing, pp. 678–681, 1974.
L. H. Aslanyan and H. E. Danoyan, “On the optimality of the hash-coding type nearest neighbour search algorithm”, Selected works of 9th CSIT conference, pp. 1-6, 2013.
F. J. Mac-Williams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1986.
V. A. Zinoviev and V. K. Leont’ev, “The nonexistence of perfect codes over Galois fields”, Problems of Control and Information Theory, vol. 2, no. 2, pp. 123-132, 1973.
L. A. Bassalygo, G. V. Zaitsevand V. A. Zinoviev, “Uniformly packed codes”, Problemy Peredachi Informatsii, vol. 10, no. 1, pp. 9-14, 1974.
T. Baicheva, I. Bouyukliev and S. Dodunekov, “Binary and ternary linear quasiperfect codes with small dimensions”, IEEE Transactions of Information Theory, vol. 54, no. 9, pp. 4335-4339, 2008.
E. M. Gabidulin, A. A. Davydov and L. M. Tombak, “Linear codes with covering radius 2 and other new covering codes,” IEEE Transactionsof Information Theory, vol. 37, no. 1, pp. 219–224, 1991.
A. A. Davydov and A. Yu. Drozhzhina-Labinskaya, “Constructions, families, and tables of binary linear covering codes,” IEEE Transactions of Information Theory, vol. 40, no. 4, pp. 1270–1279, Jul. 1994.
T. Etzion and B. Mounits, “Quasi-perfect codes with small distance”, IEEE Trans. Inform. Theory, vol. 51, no. 11, pp. 3938-3946, 2005.
T. Etzion and G. Greenberg, “Constructions for perfect mixed codes and other covering codes,” IEEE Transactions of Information.Theory, vol. 39, no. 1, pp. 209– 214, 1993.
D. Gorenstein, W. Peterson and N. Zierler, “Two error-correcting bose-chaudhuri codes are quasi perfect”, Information and Control, no. 3, pp. 291-294, 1960.
T. Kasami, S. Lin and W. Peterson, “Some results on the weight distributions of BCH codes”, IEEE Trans. Information Theory, vol. 12, no. 2, pp. 274-277, 1966.
P. Charpin “Weight distributions of cosets of two-error-correcting BCH codes, extended or not”, IEEE Transactions of Information.Theory, vol. 40, no. 5, pp. 1425– 1442, 1991.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
