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