Автор: Полевой Д. В., Постников В. В., Усков А. В.
Источник:Труды ИСА РАН 2005. Т. 16, с.132-133, http://www.isa.ru/proceedings/images/documents/2005-16/130
Пусть P = {p1, p2,…, pn} — множество из n точек в метрическом пространстве M = (v, d(v,v)), где v — это d-мерное векторное пространство и d : v*v > R обозначает меру близости (удаленности). Пусть даны множество точек P из n точек в M и исходная точка поиска qev. Назовем ближайшим соседом для точки q такую точку p∈P, что для любой другой точки p’∈P выполняется d(q, p) < d(q, p’).
Задача поиска ближайшего соседа (nearest neighbor search) состоит в нахождении ближайшего соседа для произвольной исходной точки поиска q. Если при этом разрешены добавление точек к множеству P, или их удаление, то задача называется динамической. Если множество точек данных фиксировано и не изменяется, то это статическая задача. Далее рассматривается только статическая задача поиска ближайшего соседа.
Использование вспомогательных поисковых структур позволяет значительно убыстрить процесс поиска ближайшего соседа. Проблема имеет оптимальное решение в случае 1-мерного пространства с использованием B-деревьев и их вариантов [5]. Для пространств большей размерности
разработаны различные подходы [6], [15], [16], [17], [17]. Наиболее популярными вспомогательными структурами данных являются различные
индексные деревья [4], [11], [12], [14], [18]. Рассмотрим подробнее один из возможных подходов. HS алгоритм, предложенный Hjaltson и Samet [7], использует простую идею, корни которой восходят ко многим работам (таким как k-d-деревья [8], или BBD-деревья).
Пусть дана исходная точка поиска q, идея состоит в том, чтобыразбить все пространство на блоки, и искать в этих блоках в порядке возрастания расстояния до точки q. Блок — это область пространства, которая может разбиваться на более мелкие блоки, в зависимости от количества точек, попавших в данный блок. Более формально: пусть MINDIST(q,B) обозначает минимальное расстояние от точки q до любой точки блокаB. MINDIST(q, B) = 0 если точка лежит внутри блока B. Функцию MINDIST(q, B) мы считаем расстояние от точки q до блока B. Заметим, что по определению в блоке B нет может быть точек с расстоянием до точки q меньшим, чем MINDIST(q, B). Алгоритм ищет в иерархической структуре индексов, чтобы найти блок, который содержит точку q. Спускаясь вниз по дереву будем помещать блоки, встречающиеся на пути поиска, в очередь с приоритетом. В очереди блоки сортируются в соответствии с функцией MINDIST(q, B). Алгоритм посещает блоки в порядке уменьшения расстояния от дочки q. Если блок соответствует внутреннему узлу дерева поиска, тогда все соответствующие ему блоки помещаются в очередь. Если блок является терминальным — вычислим расстояние от q до каждой точки блока.
Расстояние до ближайшей точки хранится в переменной lmin. Алгоритм заканчивает свою работу, когда расстояние до очередного блока, извлеченного из очереди, станет больше, чем lmin. HS алгоритм является оптимальным в том смысле, что он посещает только те блоки, которые пересекаются с шаром радиуса dmin (расстояние до ближайшего соседа) и центром в исходной точке q. Однако, в худшем случае, алгоритм вынужден просмотреть все точки в каждом блоке.
1. Арлазаров В. В., Постников В. В., Шоломов Д. Л. Cognitive Forms — система массового ввода структурированных документов / Сборник трудов ИСА РАН «Управление информационными потоками». 2002.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
3. Guttman A. R-trees: a dynamic index structure for spatial searching // Proceedings of the ACM SIGMOD International Conference on Management of Data. 1984. V. 14. P. 47–57.
4. White D. A., Jain R. Similarity indexing with SS-tree // Proceedings of the 24th International Conference on Very Large Data Bases, VLDB. 1998. P. 194–205.
5. Comer D. Ubiquitous B-tree // ACM Computing Surveys, 11(2): 121–137, June 1979.
6. Dobkin D., Lipton R. J. Multidimensional searching problems // SIAM Journal of Computing, 5(2): 181–186, 1976. 7. Hjaltson G. R., Samet H. Ranking in spatial databases // Lecture Notes in Computer Science, 951: 83–95, 1995.
8. Friedman J. H., Bently J. L., Finkel R. A. An algorithm for finding best matches in logarithmic expected time // ACM Transaction on Mathematical Software. 1977. V. 3. P. 209–226.
9. Clarkson K. A randomized algorithm for closest-point queries // SIAM Journal of Computing, 17: 830–847, 1988.
10. Bennett K. P., Fayyad U., Geiger D. Density-based indexing for nearest neighbor queries. Technical Report MSR-TR-98-58, Microsoft Research, 1998.
11. Beckmann N., Kriegel H. P., Shneider R., Seeger B. The R*-tree: An efficient and robust access method for points and rectangles // Proceedings of the ACM SIGMOD International Conference on Management of Data. 1990. P. 322–331.
12. Katayama N., Satoh S. The RS-tree: An index structure for high-dimensional nearest neighbor queries // Proceedings of the ACM SIGMOD International Conference on Management of Data. 1997. V. 26, 2. P. 369–380.
13. Roussopolous N., Kelley S., Vincent F. Nearest neighbor queries // Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. 1995. P. 71–79.
14. Sarnak N., Tarjan R. E. Planar point location using persistent search trees // Commun. ACM, 26: 669–679, 1986.
15. Tsaparas P. Nearest Neigbor Search in Multidimensional Spaces. Depth Oral Report, June 10, 1999.
16. Agarwal P. K., Edelsbrunner H., Schwarzkopf O., Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. Proc. 6th ACM Symp. Comp. Geom., 1990. P. 189–201.
17. Yianilos P. N. Data structures and algorithms for nearest neighbor search in general metric space // Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ‘93). 1993. P. 311–321. 18. Berchtold S., Keim D. A., Kriegel H.-P. The X-tree: An index structure for highdimensional data // VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases. 1999. P. 28–39.