|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О сложности поиска ближайшего соседа в манхэттенской метрикедипломная работа (Магистр)
- Научный руководитель: Гасанов Э.Э.
- Автор: Арапова Олеся Алексеевна
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2009
- Аннотация: В работе Араповой О.А. рассматривается задача поиска ближайшего соседа, которая состоит в следующем. Дана база данных, состоящая из точек плоскости. Элементы базы данных в данной задаче принято называть полюсами. В качестве запроса на поиск поступает точка плоскости. Надо найти в базе данных полюс, ближайший к запросу. В случае, когда расстояние между точками задается евклидовой метрикой, задача хорошо изучена и имеет красивое решение, основывающееся на построении локусов. Под локусом данного полюса понимается множество точек плоскости, для которых данный полюс является ближайшим. Поиск ближайшего соседа по методу локусов состоит в определении, какому локусу принадлежит точка, и его временная сложность, как в худшем случае, так и в среднем по порядку равна логарифму от числа полюсов. В случае, когда расстояние между двумя точками определяется как сумма модулей разностей абсцисс и ординат точек, т.е. задается манхэттенской метрикой, задача ранее не изучалась. В работе показан, какой вид могут иметь локусы для случая манхэттенской метрики, и на этой основе разработан алгоритм разбиения плоскости на локусы. Хотя для манхэттенской метрики локусы имеют более сложную форму, чем для случая евклидовой метрики, но все стороны локусов параллельны одному из четырех направлений. Используя это свойство, удалось получить алгоритм поиска, который имеет константную среднюю временную сложность, сохраняя при этом логарифмическую сложность в худшем случае. Такого результата для эвклидовой метрики получить до сих пор не удается.
- Добавил в систему: Гасанов Эльяр Эльдарович