Ամփոփում:

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

Հանձնման ամսաթիվը:

18.02.2019

Ընդունման ամսաթիվը:

15.04.2019

Նույնականացուցիչ:

oai:noad.sci.am:136049

DOI:

10.51408/1963-0030

ISSN:

0131-4645

Այլ նույնացուցիչ:

UDC 519.712.6

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Mathematical Problems of Computer Science

Հատոր:

51

URL:

լրացուցիչ տեղեկատվություն:

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

Կազմակերպության անվանում:

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

Երկիր:

Armenia

Ինդեքսավորում:

ASCI