Оценка эффективности использования метрических деревьев в приближённом поиске на основе обобщённого гиперплоскостного разбиения множества объектов - Статья
Деревья GH, GNAT и mm-GNAT как метрические структуры данных, использующие обобщённое гиперплоскостное разбиение. Выполнение поиска ближайшего соседа. Реализация программы для сравнения деревьев GH, GNAT и mm-GNAT. Эффективность поисковых запросов.
Аннотация к работе
Рассмотрены три метрические структуры данных, использующие обобщенное гиперплоскостное разбиение, - деревья GH, GNAT и mm-GNAT. Затем все остальные объекты разбиваются на два подмножества: объекты, расположенные внутри сферы с центром в опорном объекте и радиусом , и объекты, расположенные за пределами этой сферы. Обобщенным такое разбиение называется потому, что если объекты являются точками в n-мерном евклидовом пространстве, то разбиение осуществляется гиперплоскостью размерностью . Объект принадлежит кластеру , если для всех , т. е. кластеры формируются таким образом, что каждая точка в них расположена ближе к опорной точке данного кластера, нежели к остальным опорным точкам. Достоинство GNAT по сравнению с GH-деревом и деревьями, основанными на сферическом разбиении, заключается в меньшем количестве вычислений расстояний и, как следствие, возросшей производительности поиска.
Список литературы
1. Brin, S. Near Neighbor Search in Large Metric Spaces / S. Brin // VLDB "95 Proceedings of the 21th International Conference on Very Large Data Bases. - 1995. - P. 574-584.
2. Chavez, E. Searching in metric spaces / E. Chavez, G. Navarro, R. Baeza-Yates, J. L. Marroquin // ACM Computing Surveys (CSUR) Volume 33 Issue 3, September 2001. - 2001. - P. 273-321.
3. Onishi, K. mm-GNAT: Index Structure for Arbitrary Lp Norm / K. Onishi, M. Kobayakawa, M. Hoshi // IPSJ Transactions on Database 3(3). - 2010. - P. 88-98.
4. Uhlmann, J.K. Satisfying general proximity/similarity queries with metric trees / J.K. Uhlmann // Information Processing Letters 40 (1991). - 1991. - P. 175-179.
5. Yi, B.-K. Fast Time Sequence Indexing for Arbitrary Lp Norms / B.-K. Yi, C. Faloutsos // VLDB "00 Proceedings of the 26th International Conference on Very Large Data Bases. - 2000. - P. 385-394.