ММРО - Об оптимизации поиска многомерных данных в распознавании
При обработке, анализе и распознавании различных информационных массивов часто встаёт необходимость поиска многомерных векторов (обычно численных) в больших базах данных. К этому, например, сводятся задачи поиска неточных повторов в ДНК-последовательностях (геноме) и белковых последовательностях, служащие на благо биологических исследований; различные задачи поиска изображений по содержимому — поиск контуров по известной базе, поиск похожих изображений, возможно, даже какие-то задачи сжатия (например, как идея — ускорение фрактального сжатия изображений с помощью индексации блоков); и многие другие. При этом важным является, что:
- Все измерения равнозначны
- Невозможно ввести порядок в пространстве искомых векторов
- При сравнении обычно используются стандартные метрики — Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модуля разностей или линейная корреляция.
Одновременно с этим существует теория баз данных, в рамках которой в той или иной степени разрабатываются различные методы индексации многомерных данных. Все эти методы, разумеется, имеют базовые общие черты — все они являются методами построения деревьев поиска, все они на каждом шаге разделяют общее пространство на какие-то области и почти всегда они рассчитываются на дисковое хранение. Есть и ещё одна черта — почти ни один из этих методов не реализован в распространённых СУБД, что усложняет жизнь исследователям и разработчикам и заставлять создавать реализации снова и снова.
Возможно, частично поэтому авторы соответствующих алгоритмов распознавания часто не рассматривают возможность ускорения большого числа сравнений с помощью этих методов. В данном докладе предлагается использовать соответствующие методы индексации для быстрого поиска, производится сравнение некоторых методов применительно к задаче анализа биологических данных (заканчивающееся в пользу K-D-B деревьев), и предлагается использовать свободную СУБД PostgreSQL как «субъект» реализации, по причине наличия в ней реализации GiST[1] — обобщённого дерева поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь глубоко во внутреннем устройстве СУБД.
Сами методы индексации, по сути, разделяются на R-подобные деревья, хранящие в узлах гиперкубы (R — от Region/Rectangle), и BSP-подобные деревья, разделяющие на каждом шаге пространство на 2 или большее число элементов гиперплоскостями (BSP — от Binary Space Partitioning). К первым из наиболее известных относятся собственно R-дерево, R*, R+, X, M и hB-деревья, ко вторым — в первую очередь K-D-B / bKD-деревья, TV-деревья и некоторые малоизвестные реализации, использующие гиперплоскости, построенными по линейным комбинациям осей. Общая проблема — в сложности перебалансировки при динамическом построении индекса, то есть при последовательной вставке элементов, проблема R-деревьев — ещё и в пересечении гиперкубов в узлах дерева, особенно сильно увеличивающимся с увеличением размерности пространства. Некоторые из методов поддерживают индексацию только точечных данных, некоторые — точечных и пространственных.
Как ни странно, строгий расчёт на дисковое использование в последнее время, в условиях дешёвой оперативной памяти, можно и ставить под сомнение — например, обычное оптимально построенное K-D, не K-D-B дерево займёт всего лишь примерно 100 Мб для 8 миллионов индексируемых векторов, в то время, как средний персональный компьютер сейчас имеет на борту 2-4 Гб оперативной памяти. С переходом на большие объёмы оперативной памяти и 64-битные архитектуры, конечно, возрастает и разрядность указателей и то же дерево вырастает до 167 Мб, но и это не много; скорость же доступа к оперативной памяти на порядки быстрее чтения с диска (даже с набирающих популярность SSD). Это не значит, что «дисковый» подход вовсе отмирает — но при разработке будущих СУБД и индексов авторам имеет смысл обращать внимание на лучшую работу и с оперативной памятью, и с диском, так как для многих задач это может оказаться вполне достаточно.
- GiST: A Generalized Search Tree for Database Systems, a talk given at Hebrew University in Jerusalem, Tel Aviv University, UC Berkeley, Brown University, IBM Almaden Research Center. An extended version of the talk given at VLDB95.
