ММРО - Об оптимизации поиска многомерных данных в распознавании

Ссылки сюда (1) →

• Об оптимизации поиска многомерных данных в распознавании
• Филиппов В. В.
• Москва, ВМиК, кафедра ММП
• В докладе рассматриваются методы оптимизации поиска многомерных повторов применительно к задачам распознавания, например, поиска неточных повторов в генетических последовательностях.

Введение

При обработке, анализе и распознавании различных информационных массивов часто встаёт необходимость поиска многомерных векторов (обычно численных) в больших базах данных. К этому, например, сводятся задачи поиска неточных повторов в ДНК-последовательностях (геноме) и белковых последовательностях, служащие на благо биологических исследований; различные задачи поиска изображений по содержимому — поиск контуров по известной базе, поиск похожих изображений, возможно, даже какие-то задачи сжатия (например, как идея — ускорение фрактального сжатия изображений с помощью индексации блоков), а также и многие другие.

При этом важно, что:

• Все измерения равнозначны
• Невозможно ввести порядок в пространстве искомых векторов
• При сравнении обычно используются стандартные метрики: Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модулей разности или линейная корреляция.

Эти факты не дают использовать для оптимизации поиска обычные B-деревья, что приводит к необходимости поиска специальных методов.

Обзор методов

Одновременно с этим существует теория баз данных, в рамках которой в той или иной степени разрабатываются различные методы индексации многомерных данных. Все эти методы, разумеется, имеют базовые общие черты — все они являются методами построения деревьев поиска, все они на каждом шаге разделяют общее пространство на какие-то области и почти всегда они рассчитываются на использование с внешней памятью. Есть и ещё одна общая черта - почти ни один из этих методов не реализован в распространённых СУБД, что сильно усложняет жизнь исследователям и разработчикам и заставлять создавать реализации снова и снова.

С одной стороны, реализация методов с исключительным расчётом на внешнюю память (жёсткий диск, 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-деревьев — ещё и в пересечении гиперкубов в узлах дерева, особенно сильно увеличивающимся с увеличением размерности пространства. Некоторые из методов поддерживают индексацию только точечных данных, некоторые — точечных и пространственных. Различные методы также поддерживают различные методы поиска - точный поиск, поиск по области, поиск ближайшего соседа.

• R-дерево: в узлах дерева поиска хранятся n-мерные гиперкубы и ссылки на дочерние узлы. Гиперкубы, хранящиеся в дочерних узлах, всегда принадлежат гиперкубу родительского. При переполнении страницы происходит её разделение на две части и, соответственно, два гиперкуба.
• R*-дерево: то же, что и R-дерево, но также с поддержкой индексации точечных данных, а не только гиперкубов.
• R+-дерево: R-дерево без перекрытий. Смысл в том, чтобы при вставке элементов следить за перекрытием областей и своевременно разбивать их на подобласти, возможно, включая разбиение дочерних элементов. Это решает главную проблему R-подобных деревьев — без использования специальных методов при вставке элементов в дерево узлы, находящиеся на одном уровне, могут начать перекрываться, и если искомая точка содержится в области перекрытия, это сразу требует больше чтений из внешней памяти, что сильно ухудшает производительность. В авторы показали, что степень перекрытия стремится к 90\% уже при увеличении размерности до 10.
• X-дерево: уход от древовидной структуры R-дерева при большом проценте перекрытия. X-дерево — адаптивная структура, в которой кроме «древовидных» узлов также существуют «списочные», содержащие просто длинный список элементов, не разбитый на области.
• M-дерево: попытка построения аналога R-дерева для шаровидных окрестностей элементов, и попытка его обобщения на случай любой метрики. От проблемы перекрытия страдает точно так же, и возможно, даже больше, чем обычное R-дерево.
• hB-дерево: тоже похоже на R-дерево, но элементы каждой области не покрываются полностью её дочерними кубическими областями, а каждая область делится на дочерние гиперкубы и «всё остальное», за счёт чего достигается высокая эффективность использования дискового пространства, а заодно и уменьшается степень перекрытия.
• K-D-B-, TV-, BIH-деревья сводятся к делению пространства на каждом шаге пополам. Различия — в способе выбора разбиения и в том, что BIH-деревья содержат по два деления в одном узле. В K-D-B дереве ось для разбиения обычно выбирается либо циклически, либо наиболее хорошо разделяющая массив на две части.

Оптимизация

Смысл оптимизации очевиден — он такой же, как и любого дерева поиска: свести число сравнений с O(n) до O(log n), или точнее, в случае использования внешней памяти, . Для пояснения: при использовании только оперативной памяти, наиболее оптимальным деревом поиска является сбалансированное двоичное дерево, так как количество сравнений элементов в нём будет равно — каждое сравнение отсекает половину всего множества элементов. Однако в реальности базы данных, как правило, имеют размер больший, чем оперативная память, и должны гарантированно сохранять данные в целостном виде при внезапных отключениях питания, поэтому для их хранения, как правило, используется внешняя память — то есть, жёсткие диски или SSD. Скорость же чтения с диска на порядки меньше скорости чтения из оперативной памяти, кроме того, диск, как правило, оперирует «блоками» некоторого фиксированного размера — обычно это как минимум 512 байт — и поэтому при использовании двоичного дерева, хранимого во внешней памяти, узким местом становится уже чтение с диска, а не проведение сравнений. Это приводит к понятию «страницы» и логичной оптимизации дерева поиска — увеличению узла дерева до размера страницы, и созданию не 2 его дочерних узлов, а k, и, соответственно, k подобластей.

Рассмотренные индексные структуры позволяют осуществлять поиск по окрестности заданного элемента. В оригинале окрестность, как правило, является гиперкубом. Возникает вопрос: как с помощью поиска по такой окрестности оптимизировать обычные используемые метрики? Как ни странно, для всех метрик это возможно:

• Самая простая метрика — максимум модуля разности — сама в точности задаёт гиперкуб, по которому нужно просто осуществить поиск.
• Сумма модулей разности может быть оптимизирована с помощью поиска по гиперкубу в повёрнутой ортогональной системе координат.
• Выборочный парный коэффициент линейной корреляции может быть оптимизирован с помощью поиска по гиперкубу в многомерной сферической системе координат, так как линейная выборочная корреляция двух многомерных векторов есть не что иное, как косинус угла между ними:

• Сумма квадратов разностей может быть либо оптимизирована «неточно», если искомый гиперкуб описать вокруг искомой шаровидной окрестности, либо, для большей оптимизации возможно дополнительно реализовать поиск по шаровидной окрестности точки.

Кроме этого, по любой из индексных структур с минимальными затратами реализуется возможность поиска ближайшего соседа — весь смысл в обходе дерева в порядке, соответствующем минимально возможному расстоянию от области, сохранённой в узле дерева, до искомого элемента.

Например, при поиске неточных повторов в генетических последовательностях исходные строки сначала сводятся к числовым последовательностям, принимая за значение в каждой точке количество заданных нуклеотидов в некоторой её окрестности, а потом с определённым шагом выбираются вектора этих чисел, рассчитываются их спектральные образы по одному из распространённых базисов. Это и есть рассматриваемые многомерные вектора, размерностью не меньше хотя бы 16. Соответственно, для приближённого поиска нового фрагмента в известной последовательности нужно произвести те же самые операциии и сравнить спектральные образы, полученные из него, с сохранёнными в базе данных.

Эта операция хорошо распараллеливается, а для сравнения можно использовать частичное вычисление метрик, например, если квадрат разности по первой координате больше порогового значения, вычислять последующие уже не нужно. Однако даже при такой оптимизации сравнений сложность алгоритма поиска одного вектора всё равно остаётся равной O(n), соответственно, поиска частей одной последовательности в другой — O(m n), а поиска повторов в одной последовательности — O(n²).

В то же время, если ввести использование простейшего K-D-дерева, оценка сложности поиска вектора будет равна . Индексные структуры, рассчитанные на внешнюю память, естественно, на небольших объёмах будут медленнее именно потому, что используют внешнюю память, а не оперативную, но выигрывают при учёте перспективы увеличения объёмов данных, в которых предполагается производить поиск.

Выводы

Возможно, частично из-за отсутствия готовых решений авторы алгоритмов распознавания, которые можно было бы ускорять или масштабировать на большие объёмы данных, авторы систем распознавания часто не рассматривают использование этих методов. Например, на небольших объёмах данных, пока оперативной памяти достаточно для хранения полного набора данных, используемые авторами методы могут давать приемлемые результаты, но если задуматься и рассмотреть более крупные наборы данных — требуются методы оптимизации многомерных данных.

Для исправления этой ситуации предлагается использовать описанные методы индексации многомерных данных и свободную СУБД PostgreSQL как «субъект» реализации, по причине наличия в ней реализации GiST — обобщённого дерева поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь глубоко во внутреннем устройстве самой СУБД. Например, в процессе работы автором доклада на GiST была достаточно быстро создана реализация K-D-B дерева.

Также в докладе производится сравнение некоторых методов применительно к задаче анализа биологических данных (заканчивающееся в пользу K-D-B деревьев) и приводится описание самих методов.