13 531
правка
Изменения
м
Нет описания правки
С одной стороны, реализация методов с исключительным расчётом на внешнюю память (жёсткий диск, SSD) в последнее время, в условиях дешёвой оперативной памяти, может ставиться под сомнение для задач, в которых весь индекс гарантированно всегда будет помещаться в оперативную память, а данные редко меняются. Например, обычное оптимально построенное K-D дерево займёт всего лишь примерно 130 Мб для 8 миллионов индексируемых векторов любой размерности, а средний персональный компьютер уже сейчас имеет на борту 2-4 Гб оперативной памяти, поэтому если 8 миллионов сгенерированных однажды векторов достаточно для решения задачи — можно использовать методы, работающие только с оперативной памятью.
Возможно, частично из-за отсутствия готовых решений авторы алгоритмов распознавания, которые можно было бы ускорять или масштабировать на большие объёмы данных, часто не рассматривают использование этих методов. В данном докладе приводится описание равзличных методов, предлагается использовать соответствующие методы индексации для быстрого поискаданных при распознавании, производится сравнение некоторых методов применительно к задаче анализа биологических данных (заканчивающееся в пользу K-D-B деревьев), приводится описание различных методов, и предлагается использовать свободную СУБД PostgreSQL как «субъект» реализации, по причине наличия в ней реализации GiST[1] — обобщённого дерева поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь глубоко во внутреннем устройстве самой СУБД.
# 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.