• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
  • HSE University
  • Publications of HSE
  • Articles
  • Структура со свойствами тесного мира для решения задачи поиска ближайшего соседа в метрическом пространстве

Article

Структура со свойствами тесного мира для решения задачи поиска ближайшего соседа в метрическом пространстве

Пономаренко А. А., Мальков Ю. А., Логвинов А. А., Крылов В. В.

A novel approach to solving the nearest neighbor search problem in metric space is considered. It is proposed as a data structure to use a graph with navigable small world properties and a gradient descent algorithm as a search algorithm. The problem of the existence of local minima is solved by a series of independent searches. Experimental data are presented to confirm logarithmic complexity of the search algorithm.