13 531
правка
Изменения
м
→Обзор методов
повторов в ДНК-последовательностях (геноме) и белковых последовательностях,
служащие на благо биологических исследований; различные задачи поиска
изображений по содержимому - — поиск контуров по известной базе, поиск
похожих изображений, возможно, даже какие-то задачи сжатия (например,
как идея - — ускорение фрактального сжатия изображений с помощью индексации
блоков), а также и многие другие.
Одновременно с этим существует теория баз данных, в рамках которой в той
или иной степени разрабатываются различные методы индексации многомерных
данных. Все эти методы, разумеется, имеют базовые общие черты - — все они
являются методами построения деревьев поиска, все они на каждом шаге
разделяют общее пространство на какие-то области и почти всегда они
любой размерности, а средний персональный компьютер уже сейчас имеет на
борту 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<nowiki>+</nowiki>-дерево: R-дерево без перекрытий. Смысл в том, чтобы при вставке элементов следить за перекрытием областей и своевременно разбивать их на подобласти, возможно, включая разбиение дочерних элементов. Это решает главную проблему R-подобных деревьев - — без использования специальных методов при вставке элементов в дерево узлы, находящиеся на одном уровне, могут начать перекрываться, и если искомая точка содержится в области перекрытия, это сразу требует больше чтений из внешней памяти, что сильно ухудшает производительность. В <ref idname="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 подобластей.
Как ни странно, для всех метрик это возможно:
* Самая простая метрика - — максимум модуля разности - — сама в точности задаёт гиперкуб, по которому нужно просто осуществить поиск.
* Сумма модулей разности может быть оптимизирована с помощью поиска по гиперкубу в повёрнутой ортогональной системе координат.
* Выборочный парный коэффициент линейной корреляции может быть оптимизирован с помощью поиска по гиперкубу в многомерной сферической системе координат, так как линейная выборочная корреляция двух многомерных векторов есть не что иное, как косинус угла между ними:
Кроме этого, по любой из индексных структур с минимальными затратами реализуется возможность
поиска ближайшего соседа - — весь смысл в обходе дерева в порядке, соответствующем минимально
возможному расстоянию от области, сохранённой в узле дерева, до искомого элемента.
вычислять последующие уже не нужно. Однако даже при такой оптимизации
сравнений сложность алгоритма поиска одного вектора всё равно остаётся равной
O(n), соответственно, поиска частей одной последовательности в другой - — O(m n),а поиска повторов в одной последовательности - — O(n²).
В то же время, если ввести использование простейшего K-D-дерева, оценка
объёмах данных, пока оперативной памяти достаточно для хранения полного набора данных,
используемые авторами методы могут давать приемлемые результаты, но если задуматься
и рассмотреть более крупные наборы данных - — требуются методы оптимизации многомерных данных.
Для исправления этой ситуации предлагается использовать описанные методы индексации
многомерных данных и свободную СУБД PostgreSQL как «субъект» реализации, по причине
наличия в ней реализации GiST <ref idname="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> - — обобщённого дерева
поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь
глубоко во внутреннем устройстве самой СУБД. Например, в процессе работы автором доклада
