Optimal Graph for Decentralized Search Problem

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 the network is called decentralized if it uses only local information about visited nodes and its neighbors. Networks, which structure allows efficiently 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?”;. In this work we partially give the answers to these questions. We propose a programming model for the problem of determining an optimal net-work structure for decentralized nearest neighbor search. We show results for different graph size and propose several algorithms for constructing such networks.