ММРО - Об оптимизации поиска многомерных данных в распознавании
При обработке, анализе и распознавании различных информационных массивов часто встаёт необходимость поиска многомерных векторов (обычно численных) в больших базах данных. К этому, например, сводятся задачи поиска неточных повторов в ДНК-последовательностях (геноме) и белковых последовательностях, служащие на благо биологических исследований; различные задачи поиска изображений по содержимому - поиск контуров по известной базе, поиск похожих изображений, возможно, даже какие-то задачи сжатия (например, как идея - ускорение фрактального сжатия изображений с помощью индексации блоков); и многие другие. При этом важным является, что:
- Все измерения равнозначны
- Невозможно ввести порядок в пространстве искомых векторов
- При сравнении обычно используются стандартные метрики - Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модуля разностей или линейная корреляция.
Одновременно с этим существует теория баз данных, в рамках которой в той или иной степени разрабатываются различные методы индексации многомерных данных. Все эти методы, разумеется, имеют базовые общие черты - все они являются методами построения деревьев поиска, все они на каждом шаге разделяют общее пространство на какие-то области и почти всегда они рассчитываются на дисковое хранение. Есть и ещё одна черта - почти ни один из этих методов не реализован в распространённых СУБД, что усложняет жизнь исследователям и разработчикам и заставлять создавать реализации снова и снова.
Возможно, частично поэтому авторы соответствующих алгоритмов распознавания часто не рассматривают возможность ускорения большого числа сравнений с помощью этих методов. В данном докладе предлагается использовать соответствующие методы индексации для быстрого поиска, производится сравнение некоторых методов применительно к задаче анализа биологических данных (заканчивающееся в пользу 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.
