Изменения

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

* При сравнении обычно используются стандартные метрики - : Евклидова (корень из суммы квадратов разностей), максимум модуля разности, сумма модуля разностей модулей разности или линейная корреляция. Эти факты не дают использовать для оптимизации поиска обычные 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>. Индексные структуры,рассчитанные на внешнюю память, естественно, на небольших объёмах будутмедленнее именно потому, что используют внешнюю память, а не оперативную,но выигрывают при учёте перспективы увеличения объёмов данных, в которыхпредполагается производить поиск.

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

Сами Для исправления этой ситуации предлагается использовать описанные методы индексациимногомерных данных и свободную СУБД PostgreSQL как «субъект» реализации, по сутипричиненаличия в ней реализации GiST <ref name="gist95">Joe Hellerstein. GiST: A Generalized Search Tree for Database Systems. A talk given at Hebrew University in Jerusalem, разделяются на R-подобные деревьяTel Aviv University, хранящие в узлах гиперкубы (R - от Region/Rectangle)UC Berkeley, и BSP-подобные деревьяBrown University, разделяющие на каждом шаге пространство на 2 или большее число элементов гиперплоскостями (BSP - от Binary Space Partitioning)IBM Almaden Research Center. К первым из наиболее известных относятся собственно R-деревоAn extended version of the talk given at VLDB95.</ref> — обобщённого деревапоиска, R*-позволяющего легко реализовывать собственные методы индексации, R+-не разбираясьглубоко во внутреннем устройстве самой СУБД. Например, X-, M- и hB-деревья, ко вторым - в первую очередь процессе работы автором докладана GiST была достаточно быстро создана реализация K-D-B / bKD-деревья, TV-деревья и некоторые малоизвестные реализации, использующие гиперплоскости, построенными по линейным комбинациям осей. Общая проблема - в сложности перебалансировки при динамическом построении индекса, т.е. при последовательной вставке элементов, проблема R-деревьев - ещё и в пересечении гиперкубов в узлах дерева, особенно сильно увеличивающимся с увеличением размерности пространства. Некоторые из методов поддерживают индексацию только точечных данных, некоторые - точечных и пространственных.

Как ни странно, строгий расчёт на дисковое использование Также в последнее время, докладе производится сравнение некоторых методов применительно к задачеанализа биологических данных (заканчивающееся в условиях дешёвой оперативной памяти, можно и ставить под сомнение - например, обычное оптимально построенное K-D, не пользу K-D-B дерево займёт всего лишь примерно 100 Мб для 8 миллионов индексируемых векторов, в то время, как средний персональный компьютер сейчас имеет на борту 2-4 Гб оперативной памяти. С переходом на большие объёмы оперативной памяти и 64-битные архитектуры, конечно, возрастает и разрядность указателей и то же дерево вырастает до 167 Мб, но и это не много; скорость же доступа к оперативной памяти на порядки быстрее чтения с диска (даже с набирающих популярность SSDдеревьев). Это не значит, что "дисковый" подход вовсе отмирает - но при разработке будущих СУБД и индексов авторам имеет смысл обращать внимание на лучшую работу и с оперативной памятью, и с диском, так как для многих задач это может оказаться вполне достаточноприводитсяописание самих методов.