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?”; “What are their properties?”. In this talk we partially give the answers to these questions. We propose a programming model for the problem of determining an optimal network structure for decentralized nearest neighbor search. Also we propose tabu algorithm for constracting such networks and show results.