A Model of Optimal Network Structure for Decentralized Nearest Neighbor Search

P. 197–203.

Ponomarenko A., Irina Utkina, Mikhail Batsyn

One of the approaches for the nearest neighbor search problem is to build a network which nodes correspond to the given set of indexed objects. In this case the search of the closest object can be thought as a search of a node in a network. A procedure in a network is called decentralized if it uses only local information about visited nodes and its neighbors. Networks, which structure allows efficient performing the nearest neighbor search by a decentralized search procedure started from any node, are of particular interest especially for pure distributed systems. Several algorithms that construct such networks have been proposed in literature. However, the following questions arise: “Are there network models in which decentralized search can be performed faster?”; “What are the optimal networks for the decentralized search?”; “What are their properties?”. In this paper we partially give answers to these questions. We propose a mathematical programming model for the problem of determining an optimal network structure for decentralized nearest neighbour search. We have found the exact solutions for a regular lattice of size 4x4 and heuristic solutions for sizes from 5x5 to 7x7. As a distance function we use L_1, L_2 and L_inf metrics. We hope that our results and the proposed model will initiate study of optimal network structures for decentralized nearest neighbour search.

Keywords: сеть, оптимизационная модель, network, поиск ближайшего соседа, Nearest Neighbour Search, Optimisation Model, Decentralised Search, децентрализованный поиск

In book

Computational Aspects and Applications in Large-Scale Networks. Springer Proceedings in Mathematics & Statistics

Valery A. Kalyagin, Panos M. Pardalos, Oleg Prokopyev, Irina Utkina Vol. 247. , Springer, 2018.