Object

Title: Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm ; Сложность алгоритма поиска ближайших соседей с кодами исправляющими ошибки

Abstract:

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.
; Известен алгоритм поиска ближайших соседей (алгоритм Элиаса). Алгоритм использует коды, исправляющие ошибки для построения схем хеш-кодирования. Эти схемы представляют данные в форме списков. Каждый список содержится в некоторой сфере, центром которого является некоторое кодовое слово. Алгоритм рассматривается для случаев совершенных кодов, поэтому указанные сферы и, следовательно, списки не пересекаются. Поскольку совершенные коды существуют для очень специфичного набора параметров, алгоритм рассматривается для некоторых обобщений совершенных кодов, когда одна и та же точка данных может содержаться в разных списках. Для указанных случаев получены формулы временной сложности алгоритма с использованием весовой структуры смежных классов кодов.

Date submitted:

18.02.2019

Date accepted:

15.04.2019

Identifier:

oai:noad.sci.am:136049

DOI:

10.51408/1963-0030

ISSN:

0131-4645

Other identifier:

UDC 519.712.6

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

51

URL:


Additional Information:

lasl@sci.am ; hed@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems ; Институт проблем информатики и автоматизации

Country:

Armenia

Indexing:

ASCI

Object collections:

Last modified:

Apr 1, 2021

In our library since:

Jul 30, 2020

Number of object content hits:

19

All available object's versions:

https://noad.sci.am/publication/149688

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information