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