Регистрация / Вход
Прислать материал

Optimal graph for decentralized search problem

Name
Irina
Surname
Utkina
Scientific organization
NRU HSE
Academic degree
Bachelor
Position
Student
Scientific discipline
Information technologies
Topic
Optimal graph for decentralized search problem
Abstract
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 neighbours. Several algorithms that construct such networks have been proposed in literature. We propose a programming model and tabu algorithm for constructing network.
Keywords
networks, tabu, heuristic, search
Summary

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.