ММРО - Об оптимизации поиска многомерных данных в распознавании
При обработке, анализе и распознавании различных информационных массивов часто встаёт необходимость поиска многомерных векторов (обычно численных) в больших базах данных. К этому, например, сводятся задачи поиска неточных повторов в ДНК-последовательностях (геноме) и белковых последовательностях, служащие на благо биологических исследований; различные задачи поиска изображений по содержимому — поиск контуров по известной базе, поиск похожих изображений, возможно, даже какие-то задачи сжатия (например, как идея — ускорение фрактального сжатия изображений с помощью индексации блоков); и многие другие.
При этом важно, что:
- Все измерения равнозначны
- Невозможно ввести порядок в пространстве искомых векторов
- При сравнении обычно используются стандартные метрики — Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модуля разностей или линейная корреляция.
Одновременно с этим существует теория баз данных, в рамках которой в той или иной степени разрабатываются различные методы индексации многомерных данных. Все эти методы, разумеется, имеют базовые общие черты — все они являются методами построения деревьев поиска, все они на каждом шаге разделяют общее пространство на какие-то области и почти всегда они рассчитываются на использование с внешней памятью. Есть и ещё одна общая черта — почти ни один из этих методов не реализован в распространённых СУБД, что сильно усложняет жизнь исследователям и разработчикам и заставлять создавать реализации снова и снова.
С одной стороны, реализация методов с исключительным расчётом на внешнюю память (жёсткий диск, SSD) в последнее время, в условиях дешёвой оперативной памяти, может ставиться под сомнение для задач, в которых весь индекс гарантированно всегда будет помещаться в оперативную память, а данные редко меняются. Например, обычное оптимально построенное K-D дерево займёт всего лишь примерно 130 Мб для 8 миллионов индексируемых векторов любой размерности, а средний персональный компьютер уже сейчас имеет на борту 2-4 Гб оперативной памяти, поэтому если 8 миллионов сгенерированных однажды векторов достаточно для решения задачи — можно использовать методы, работающие только с оперативной памятью.
Сами методы индексации, по сути, разделяются на R-подобные деревья, хранящие в узлах гиперкубы (R — от Region/Rectangle), и BSP-подобные деревья, разделяющие на каждом шаге пространство на 2 или большее число элементов гиперплоскостями (BSP — от Binary Space Partitioning). К первым из наиболее известных относятся собственно R-дерево, R*, R+, X, M и hB-деревья, ко вторым — в первую очередь K-D-B / bKD-деревья, TV-деревья, BIH/SKD-деревья (используемые в Ray Tracing) и некоторые малоизвестные реализации, использующие гиперплоскости, построенные по линейным комбинациям осей. Общая проблема — в сложности перебалансировки дерева при динамическом построении индекса, то есть при последовательной вставке элементов; проблема R-деревьев — ещё и в пересечении гиперкубов в узлах дерева, особенно сильно увеличивающимся с увеличением размерности пространства. Некоторые из методов поддерживают индексацию только точечных данных, некоторые — точечных и пространственных. Различные методы также поддерживают различные методы поиска — точный поиск, поиск по области, поиск ближайшего соседа.
При этом, все стандартные используемые метрики могут быть ускорены с помощью методов индексации многомерных данных. Самая простая метрика — максимум модуля разности — вообще в точности задаёт гиперкуб, по которому нужно просто осуществить поиск. Сумма модулей разности может быть оптимизирована с помощью поиска по гиперкубу в повёрнутой ортогональной системе координат. Линейная корреляция может быть оптимизирована опять-таки с помощью поиска по гиперкубу в многомерной сферической системе координат, так как линейная корреляция двух векторов в многомерном пространстве — по сути, всего лишь косинус угла между ними. Сумма квадратов разностей может быть либо оптимизирована «неточно», если гиперкуб описать вокруг искомой шаровидной окрестности; либо, для ещё большей оптимизации возможно реализовать поиск по шаровидной окрестности точки. Кроме этого, по любой из индексных структур с минимальными затратами реализуется возможность поиска ближайшего соседа — весь смысл в обходе дерева в порядке, соответствующем минимально возможному расстоянию от области, сохранённой в узле дерева, до искомого элемента.
Возможно, частично из-за отсутствия готовых решений авторы алгоритмов распознавания, которые можно было бы ускорять или масштабировать на большие объёмы данных, часто не рассматривают использование этих методов. В данном докладе предлагается использовать соответствующие методы индексации для быстрого поиска данных при распознавании, производится сравнение некоторых методов применительно к задаче анализа биологических данных (заканчивающееся в пользу K-D-B деревьев), приводится описание различных методов, и предлагается использовать свободную СУБД PostgreSQL как «субъект» реализации, по причине наличия в ней реализации GiST[1] — обобщённого дерева поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь глубоко во внутреннем устройстве самой СУБД.
- 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.
