Indexing algorithm based on storing additional distances in metric space for multi-vantage-point tree

Аннотация

Введение: парадигма поиска по сходству применяется в различных вычислительных задачах, таких как классификация, интеллектуальный анализ данных, распознавание образов и др. В настоящее время среди алгоритмов поиска значительное место занимает технология древовидных метрических методов доступа. Классическая проблема сокращения времени поиска по сходству в метрическом пространстве является актуальной для современных систем при обработке больших сложных данных. Ввиду многоаспектности проблемы эффективности поисковых алгоритмов локальные исследования в этом направлении востребованы и продолжают приносить полезные результаты. Цель: снизить вычислительную сложность алгоритмов древовидного поиска в задачах, использующих метрическую близость. Результаты: разработан алгоритм поиска для структуры данных в виде дерева множества опорных точек, основанный на приоритетной очереди обработки узлов; математически формализованы проблемы дополнительных вычислений и способы их решения. Для повышения быстродействия поиска по сходству предложены процедуры формирования приоритетной очереди обработки узлов и уменьшения количества пересечений узлов одного уровня. Повышение эффективности происходит на основе изменения древовидной структуры данных и использования минимальных расстояний между опорными точками и поддеревьями узла. Уменьшение числа вычислений достигается за счет более точного определения расстояния до узлов от искомого объекта и факта пересечения области поиска с узлом дерева. Практическая значимость: полученным алгоритмам поиска требуется меньше времени для обработки информации за счет несущественного повышения требований к памяти. Снижение времени обработки информации расширяет границы применения древовидных метрических методов индексации в задачах поиска в больших массивах данных.