Изменения

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

* При сравнении обычно используются стандартные метрики — метрики: Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модуля разностей модулей разности или линейная корреляция. Эти факты не дают использовать для оптимизации поиска обычные 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<nowiki>+</nowiki>-дерево: R-дерево без перекрытий. Смысл в том, чтобы при вставке элементов следить за перекрытием областей и своевременно разбивать их на подобласти, возможно, включая разбиение дочерних элементов. Это решает главную проблему R-подобных деревьев — без использования специальных методов при вставке элементов в дерево узлы, находящиеся на одном уровне, могут начать перекрываться, и если искомая точка содержится в области перекрытия, это сразу требует больше чтений из внешней памяти, что сильно ухудшает производительность. В <ref name="p028_xtree">Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel. The X-tree: An Index Structure for High-Dimensional Data. In VLDB’1996, p.28-39.</ref> авторы показали, что степень перекрытия стремится к 90\% уже при увеличении размерности до 10.* X-дерево: уход от древовидной структуры R-дерева при большом проценте перекрытия. X-дерево — адаптивная структура, в которой кроме «древовидных» узлов также существуют «списочные», содержащие просто длинный список элементов, не разбитый на области.* M-дерево: попытка построения аналога R-дерева для шаровидных окрестностей элементов, и попытка его обобщения на случай любой метрики. От проблемы перекрытия страдает точно так же, и возможно, даже больше, чем обычное R-дерево.* hB-дерево: тоже похоже на R-дерево, но элементы каждой области не покрываются полностью её дочерними кубическими областями, а каждая область делится на дочерние гиперкубы и «всё остальное», за счёт чего достигается высокая эффективность использования дискового пространства, а заодно и уменьшается степень перекрытия.* K-D-B-, TV-, BIH-деревья сводятся к делению пространства на каждом шаге пополам. Различия — в способе выбора разбиения и в том, что BIH-деревья содержат по два деления в одном узле. В K-D-B дереве ось для разбиения обычно выбирается либо циклически, либо наиболее хорошо разделяющая массив на две части. == Оптимизация == Смысл оптимизации очевиден — он такой же, как и любого дерева поиска: свестичисло сравнений с O(n) до O(log n), или точнее, в случае использования внешнейпамяти, <m>O((k-1) log_k n</m>. Для пояснения: при использовании только оперативной памяти,наиболее оптимальным деревом поиска является сбалансированное двоичное дерево,так как количество сравнений элементов в нём будет равно <m>O(log_2 n)</m> — каждоесравнение отсекает половину всего множества элементов. Однако в реальности базы данных,как правило, имеют размер больший, чем оперативная память, и должны гарантированно сохранятьданные в целостном виде при внезапных отключениях питания, поэтому для их хранения,как правило, используется внешняя память — то есть, жёсткие диски или SSD. Скоростьже чтения с диска на порядки меньше скорости чтения из оперативной памяти, кроме того,диск, как правило, оперирует «блоками» некоторого фиксированного размера — обычноэто как минимум 512 байт — и поэтому при использовании двоичного дерева, хранимогово внешней памяти, узким местом становится уже чтение с диска, а не проведение сравнений.Это приводит к понятию «страницы» и логичной оптимизации дерева поиска — увеличениюузла дерева до размера страницы, и созданию не 2 его дочерних узлов, а k, и,соответственно, k подобластей. Рассмотренные индексные структуры позволяют осуществлять поиск по окрестности заданногоэлемента. В оригинале окрестность, как правило, является гиперкубом. Возникает вопрос:как с помощью поиска по такой окрестности оптимизировать обычные используемые метрики?Как ни странно, для всех метрик это возможно: * Самая простая метрика — максимум модуля разности — сама в точности задаёт гиперкуб, по которому нужно просто осуществить поиск.* Сумма модулей разности может быть оптимизирована с помощью поиска по гиперкубу в повёрнутой ортогональной системе координат.* Выборочный парный коэффициент линейной корреляции может быть оптимизирован с помощью поиска по гиперкубу в многомерной сферической системе координат, так как линейная выборочная корреляция двух многомерных векторов есть не что иное, как косинус угла между ними:*: <m>r(X,Y) = \frac{E((X-EX) \cdot (Y-EY))}{\sqrt{D(X) \cdot D(Y)}}</m>*: <m>r_n(X,Y) = \frac{\sum_{i=1}^{n} (x_i — \bar x)(y_i — \bar y)}{\sqrt{\sum_{i=1}^{n} (x_i — \bar x)²}\sqrt{\sum_{i=1}^{n} (y_i — \bar y)²}}</m>*: <m>cos \phi = \frac{(\vec{a}, \vec{b})}{|\vec{a}||\vec{b}|} = \frac{\sum_{i=1}^n a_i b_i}{\sqrt{\sum_{i=1}^{n} a_i²}\sqrt{\sum_{i=1}^{n} b_i²}}</m>* Сумма квадратов разностей может быть либо оптимизирована «неточно», если искомый гиперкуб описать вокруг искомой шаровидной окрестности, либо, для большей оптимизации возможно дополнительно реализовать поиск по шаровидной окрестности точки. Кроме этого, по любой из индексных структур с минимальными затратами реализуется возможностьпоиска ближайшего соседа — весь смысл в обходе дерева в порядке, соответствующем минимальновозможному расстоянию от области, сохранённой в узле дерева, до искомого элемента. Например, при поиске неточных повторов в генетических последовательностяхисходные строки сначала сводятся к числовым последовательностям, принимаяза значение в каждой точке количество заданных нуклеотидов в некоторой еёокрестности, а потом с определённым шагом выбираются вектора этих чисел,рассчитываются их спектральные образы по одному из распространённых базисов.Это и есть рассматриваемые многомерные вектора, размерностью не меньшехотя бы 16. Соответственно, для приближённого поиска нового фрагмента визвестной последовательности нужно произвести те же самые операциии исравнить спектральные образы, полученные из него, с сохранёнными в базеданных. Эта операция хорошо распараллеливается, а длясравнения можно использовать частичное вычисление метрик, например,если квадрат разности по первой координате больше порогового значения,вычислять последующие уже не нужно. Однако даже при такой оптимизациисравнений сложность алгоритма поиска одного вектора всё равно остаётся равнойO(n), соответственно, поиска частей одной последовательности в другой — O(m n),а поиска повторов в одной последовательности — O(n²).

Одновременно с этим существует теория баз данныхВ то же время, в рамках которой в той или иной степени разрабатываются различные методы индексации многомерных данныхесли ввести использование простейшего K-D-дерева, оценкасложности поиска вектора будет равна <m>O(log_2 n)</m>. Все эти методыИндексные структуры, разумеетсярассчитанные на внешнюю память, имеют базовые общие черты — все они являются методами построения деревьев поискаестественно, все они на каждом шаге разделяют общее пространство на какие-то области и почти всегда они рассчитываются на использование с внешней памятью. Есть и ещё одна общая черта — почти ни один из этих методов не реализован в распространённых СУБДнебольших объёмах будутмедленнее именно потому, что усложняет жизнь исследователям и разработчикам и заставлять создавать реализации снова и сноваиспользуют внешнюю память, а не оперативную,но выигрывают при учёте перспективы увеличения объёмов данных, в которыхпредполагается производить поиск.

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

При этом, все стандартные используемые метрики могут быть ускорены с помощью методов Для исправления этой ситуации предлагается использовать описанные методы индексации многомерных данных. Самая простая метрика — максимум модуля разности — вообще в точности задаёт гиперкуби свободную СУБД PostgreSQL как «субъект» реализации, по которому нужно просто осуществить поиск. Сумма модулей разности может быть оптимизирована с помощью поиска по гиперкубу причиненаличия в повёрнутой ортогональной системе координатней реализации GiST <ref name="gist95">Joe Hellerstein. Линейная корреляция может быть оптимизирована опять-таки с помощью поиска по гиперкубу в многомерной сферической системе координат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.</ref> — обобщённого деревапоиска ближайшего соседа — весь смысл в обходе дерева в порядке, соответствующем минимально возможному расстоянию от областипозволяющего легко реализовывать собственные методы индексации, не разбираясьглубоко во внутреннем устройстве самой СУБД. Например, сохранённой в узле процессе работы автором докладана GiST была достаточно быстро создана реализация K-D-B дерева, до искомого элемента.

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