ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ
ТЕХНИКА
УДК 519.7
А. Е. У с т ю ж а н и н
МЕТОД ПОСТРОЕНИЯ СИСТЕМЫ ПАМЯТИ
ДЛЯ ХРАНЕНИЯ И ПОИСКА МНОГОМЕРНЫХ
ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Рассмотрена возможность использования хаотических процессо-
ров как систем хранения и поиска информации, представленной в
виде пространственно-временных последовательностей. Основны-
ми проблемами построения систем памяти являются значитель-
ные объемы информации и нечеткость критериев сравнения двух
последовательностей. Рассмотрена функция расстояния для срав-
нения пространственно-временных последовательностей и способ
организации информации в виде хаотического процессора на осно-
ве структур пространственных индексов. На основе реальных дан-
ных, используемых в качестве стандартного набора при разработ-
ке алгоритмов и структур данных многомерной индексации, оцене-
на применимость и эффективность данного подхода.
Во многих задачах, связанных с хранением и анализом данных,
основным способом представления информации является кодирование
данныхв виде пространственно-временныхпоследовательностей. Раз-
витие такихтехнологий, как Global Positioning System (GPS), мобиль-
ныхсистем и датчиков пространственныхкоординат объектов дает
доступ к огромным объемам данныхи, как следствие, возрастает по-
требность в эффективныхалгоритмахиханализа и хранения. Напри-
мер, рассмотрим задачу, когда мобильный объект наблюдения оснащен
сенсором, регистрирующим положение объекта в пространстве с опре-
деленной временной частотой. Данные о траектории движения объек-
та сохраняются для дальнейшей обработки в базе пространственно-
временныхданных. Запросы к такой базе данныхмогут состоять в
поиске траекторий, похожихдруг на друга, в поиске возможныхпро-
должений по известному началу, поиску предысторий по известному
отрезку траекторий и т.д. На сегодняшний день универсальныхспо-
собов работы с такими данными нет, и каждый подход имеет свои
достоинства и недостатки.
В настоящей работе рассмотрена проблема построения хранилища
пространственно-временныхпоследовательностей (траекторий), кото-
рое позволяет находить траектории, содержащие подпоследователь-
ности, похожие на поисковый запрос. Именно возможность ответа
104 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2
