автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Прогнозирование социально-экономических показателей и алгоритмы сжатия баз данных в экономических системах

На правах рукописи

СМИРНОВ МАКСИМ АНАТОЛЬ

ПРОГ НОЗИРОВАНИЕ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПОКАЗАТЕЛЕЙ И АЛГОРИТМЫ СЖАТИЯ БАЗ ДАННЫХ В ЭКОНОМИЧЕСКИХ СИСТЕМАХ

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2005

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП).

Научный руководитель:

доктор технических наук, профессор Осипов Леонид Андроникович

Официальные оппоненты: доктор технических наук,

профессор Яковлев Сергей Алексеевич

кандидат технических наук, доцент Бржезовский Александр Викторович

Ведущая организация Санкт-Петербургский институт информатики и автоматизации Российской академии наук, г. Санкт-Петербург.

Защита состоится «¿2_» 2005 г. в часов на заседании

диссертационного совета Д 212233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, Санкт-Петербург, ул. Б. Морская, 67, ГУАП.

С диссертацией можно ознакомиться в библиотеке ГУАП.

Автореферат разослан « /X » 2005 г.

Ученый секретарь ,

диссертационного совета п Г\ __ Р

доктор технических наук, профессор Осипов Л.А.

¿рое-?

з

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Прогнозирование показателей социально-экономических процессов региона используется в системах поддержки принятия решений как при государственном управлении, гак и при управлении масштабной организацией. Вопрос получения прогноза, при котором используется ретроспективная информация о поведении только прогнозируемого показателя (однофакгорное прогнозирование), актуален как для задач вычисления прогнозных значений отдельных показателей в крачка- и среднесрочной перспективе, так и для задач комплексного прогнозирования социально-экономического развития. В последнем случае прогнозирование в сочетании с экспертными оценками может применяться при формировании сценариев эволюции экономической системы для комплексного имитационного моделирования развития субъекта Российской Федерации.

Необходимая интерактивность анализа и прогнозирования социально-экономических процессов должна обеспечиваться не только благодаря эффективным алгоритмам обработки данных и прогнозирования, но и за счет быстрого извлечения необходимой информации. При прогнозировании большого числа рядов значений, извлекаемых из базы данных (БД), основная доля временных затрат может приходиться на обработку запроса в системе управления базами данных (СУБД). Большой объем баз данных социально-экономических показателей диктует необходимость использования специальных методов повышения производительности СУБД.

Целью работы является разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона, а также повышение производительности систем управления большими базами данных социально-экономических показателей за счет использования сжатия данных.

Задачами диссертационного исследования являются:

• разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развитая региона на основе модели авторегрессии и проинтегрированного скользящего среднего;

• разработка алгоритмов сжатия баз данных социально-экономических показателей без потерь информации для повышения ггооизводительносги

СУБД;

• реализация предложенных алгоритмов в виде комплекса программ, обеспечивающего прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных;

• проведение вычислительных экспериментов по прогнозированию социально-экономических показателей развития субъекта Российской Федерации, по оценке точности прогноза, получаемого дня разработанного алгоритма, по оценке изменения скорости выполнения типовых запросов и уменьшения размера хранимых данных в случае использования алгоритмов сжатия базы данных.

Методы исследования. Для решения поставленных задач в работе использованы: теория вероятностей, математическая статистика, нелинейное программирование, анализ временных рядов, теория кодирования дискретных источников сообщений, теория сложности алгоритмов.

Основные положения, выносимые на защиту:

1. Алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе набора моделей авторегрессии и проинтегрированного скользящего среднего (АРПСС).

2. Алгоритмы сжатия баз данных без потерь информации, основанные на словарном и статистическом кодировании с использованием контекстного моделирования.

3. Комплекс программ, обеспечивающий кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных.

4. Результата вычислительных экспериментов по прогнозированию, по оценке точности прогноза для предложенного алгоритма, по оценке изменения скорости выполнения запросов к сжатой базе данных и уменьшения размера хранимых данных.

Научная новизна работы состоит в следующем:

• разработанный алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона отличается использованием набора моделей класса АРПСС, каждая из которых идентифицируется для прогнозирования ровно на к шагов вперед;

• предложенный алгоритм словарного кодирования для применения в СУБД обеспечивает сохранение упорядочивания и позволяет минимизировать число перестроек словаря при появлении новых значений; разработанный

алгоритм словарного кодирования с учетом горизонтальных зависимостей обеспечивает сильное сжатие данных в случае детерминированной или тесной зависимости между столбцами таблицы;

• разработанный алгоритм статистического кодирования с использованием контекстного моделирования, предназначенный для применения в СУБД, обладает свойством сохранения упорядочивания и не требует больших временных затрат при кодировании новых, ранее не встречавшихся значений атрибута;

• разработанный комплекс программ обеспечивает кратко- и среднесрочное прошозироваиие показателей социально-экономического развития региона по предложенному алгоритму и отличается возможностью храпения и обработки сжатых данных для повышения скорости обработки запросов.

Практическая ценность. Разработан алгоритм прогнозирования социально-экономических показателей развития региона. Предложены алгоритмы сжатия баз данных социально-экономической информации Создан комплекс программ, обеспечивающий кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона и позволяющий хранить и обрабатывать сжатые данные. При выполнении вычислительных экспериментов показало, что реализация разработанного алгоритма прогнозирования позволяет увеличить точность предсказания, а реализация алгоритмов сжатия баз данных - достичь более компактного представления хранимых данных и большей скорости обработки запросов, чем известный аналог. Результаты работы могут быть использованы в автоматизированных информационных системах анализа и прогнозирования развития территории.

Внедрение и реализация результатов работы. Основные теоретические и практические результаты были внедрены и использованы в комплексе программ для анализа социально-экономических процессов Санкт-Петербурга и комплексного имитационного моделирования развития субъекта Российской Федерации на примере Санкт-Петербурга. Результата работы были получены при выполнении хозяйственной договорной научно-исследовательской работы (НИР №199), проведенной Санкт-Петербургским государственным университетом аэрокосмического приборостроения.

Полученные в диссертационной работе результаты используются в учебном процессе кафедры вычислительных машин и комплексов ГУ АЛ.

Апробация работы. Основные положения докладывались на: международной конференции «Региональная информатика 2004» (г Санкт-Петербург, 22-24 июня 2004 г.), всероссийской научной конференции «Управление и информационные технологии» (г. Санкт-Петербург, 3-4 апреля 2003 г.), трех научных сессиях аспирантов и молодых ученых ГУАП (г. Санкт-Петербург, 2002-2004 годы).

Публикации. По теме работы опубликовано 7 печатных работ, в том числе одна монография.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованных источников (86 наименований) и четырех приложений. Основная часть работы изложена на 149 страницах машинописного текста, содержит 31 рисунок и 21 таблицу. Приложения насчитывают 21 страницу и содержат 12 рисунков и 6 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность выбранной темы, определена цель и сформулированы решаемые в работе задачи. Перечислены новые научные результаты, полученные при выполнении работы, показаны практическая ценность и апробация работы, описаны внедрение и реализация результатов. Приведены основные положения, выносимые на защиту.

В разделе 1 обоснована актуальность работы, поставлена ее цель, проведен анализ способов решения задачи прогнозирования социально-экономических показателей и подходов к решению задачи компактного представления баз данных социально-экономических показателей.

Были проанализированы особенности рядов макросециалыгых и макроэкономических показателей развитая субъекта Российской Федерации на примере Санкт-Петербурга. Отмечено, что имеются следующие особенности: пригодные к обработке ряды являются короткими; ряды квартальных и месячных значений имеют существенную сезонную компоненту; основная масса рядов имеет значимый линейный тренд.

Проведен анализ подходов к решению задачи однофакторного прогнозирования. При оценке подходов помимо учета указанных особенностей рядов принимались во внимание точность предсказания для набора типичных показателей, вычислительная сложность алгоритма, а также возможность и простота интерпретации модели или прогностического выражения. По

совокупности характеристик в качестве базового подхода выбран метод предсказания па основе модели АРГ1СС.

Дня обеспечения оперативности анализа и прогнозирования динамики показателей необходимо быстрое извлечение необходимой информации из машинной базы данных. Проанализированы особенности баз данных социально-экономических показателей и способы повышения производительности СУБД.

Типичное ядро базы данных для рассматриваемой задачи состоит из таблицы фактов, или таблицы значений, и набора таблиц-справочников. Основная доля объема базы - 90% и более приходится на таблицу фактов. Она содержит главным образом числовые и короткие строковые значения. Решающее влияние на скорость выполнения запроса имеют операции, выполняемые над таблицей значений. Основными запросами являются запросы на чтение информации.

При анализе выделены 3 группы методов повышения производительности, каждая из которых связана с одной из следующих работ: проектирование логической структуры БД формирование физической структуры БД, изменение алгоритмов работы и внутреннего устройства СУБД. Сжатие данных относится к третьей группе. Достоинство подхода состоит в том, что в большинстве случаев он может применяться в комплексе с другими способами.

Для применения в СУБД требуются специфические приемы сжатия данных без потерь информации. Число операций декодирования данных должно минимизироваться. Повышение быстродействия возможно часто лишь в том случае, если запросы выполняются непосредственно на сжатых данных. Поэтому важно, чтобы алгоритмы сжатия обладали свойством сохранения упорядочивания. Это позволяет корректно выполнять операции неэквивалентного сравнения закодированных значений. В результате может существенно уменьшаться число обязательных операций декодирования.

С учетом специфики характеристик и особенностей использования баз данных социально-экономических показателей среди проанализированных подходов к сжатию баз данных были выбраны следующие способы: статистический подход с использованием арифметического кодирования, а также словарный подход, при котором фразами словаря являются значения колонки (атрибута).

На основании проведенного анализа сформулированы задачи исследования.

В разделе 2 разработан и исследован на искусственно сгенерированных данных алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона. Рассмотрены вопросы программной реализации алгоритма.

При использовании АРПСС ряд y(t), преобразованный с помощью d -

кратного взятия разностей значений в последовательность разностей Ady(t), описывается процессом авторегрессии порядка р со скользящим средним порядка q в остатках:

/"VW + Iay'O-i)-ieje{l-j) + e{t) , (1)

м j-1

где yid)(t) = ^у(') - d -кратная разность y(t), A[y(t) = y(t)-y(t 1); £, -константа (свободный член); a, - параметры авторегрессии, / = \,р; в} -параметры скользящего среднего, / =\,q; s(t) - случайная компонента (остаток), т.е. разница между величиной y(d)(t) и ее модельным значением

Л).

Полная модель с учетом периодической составляющей с периодом Т кратко описывается в виде АРПСС(р ,d ,q )(P ,D ,Q )t и выражается как

<2,

А(В)-АТ(В)

где А^ =(1 - й7)л; - среднее значение; В - оператор сдвига,

А(В)

By(l) = y(t-1), А1 =1 -В; &(В) = \-в1В-...-вчВч - оператор скользящего

среднего; @т(В) = \-втВт ~...-втдВт°-, А{В) = \-а,В-...-арВр -

оператор авторегрессии; АГ(В) = 1 - атВт ~...-ат РВТ р.

При известном подходе расчет параметров модели (2), т.е. ее идентификация, выполняется путем решения задачи минимизации ошибки e(i) между текущим значением y(i) и модельным у (0 > вычисленным на основании предшествующих отсчетов. Это ошибка f(/ + l|i) мри прогнозе на 1 шаг вперед на основании значений, известных в момент времени t. Прогнозные

y(l + k\t)=F

значения на несколько шагов вперед формируются в результате подстановки в (2) ранее рассчитанных проточных величии, так что

(?(t + k-1\t),...,y(t + ]\t\y(t),y(t-\),...y{t-p+l\ \

^(t)A<- Ч + 0,в(4©/ {В\а{В),Ат{Ъ\Н)'

Суть разработанного подхода заключается в использовании независимых моделей АРПСС М(к>, каждая из которых применяется для получения прогноза ровно на некоторое к шагов вперед, к -1,1, где I - горизонт прогнозирования. Пусть Ft(x,l(r)) - уравнение для модели М<*> , где X - параметры модели, l(i) - весь объем информации о ряде у it), известный в момент времени t. Тогда для разработанного алгоритма:

K<+*IO = Ft(Xj(0). (4)

Получаемое прогностическое выражение для у таково, что в зависимости от требуемой дальности прогноза к выбирается модель Mik). Значения параметров X модели М(к) находятся при решении задачи минимизации ошибки прогноза на к шагов вперед

e(t + k\t)=y(t + k)-?(t + k\t), (5)

п

+ -»min. (6)

(=i

Для решения оптимизационной задачи (6) были проанализированы три процедуры минимизации. Для набора процессов, сгенерированных по типичным для социально-экономических показателей моделям АРПСС, не было выявлено значимых отличий между оценками параметров, получаемых для разных подходов. Был выбран метод Гаусса-Ньютона как вычислительно нетрудоемкий.

Вид формулы (5) в конкретном случае зависит от структуры модели АРПСС и дальности прогноза к. Показано, что выражение для c(t + к\t) формируется путем замены неизвестных авторегрессионных слагаемых ay^it-i) их оценками по уравнению АРПСС, а неизвестных элементов скользящего среднего в} s(t -j) - нулями. Например, для АРПСС (2,0,0):

ЯО^ + я^-Ц + а^-г). (7)

При к = 2 из формул (5) и (7) следует:

£(t + 2\l) = y(t+2)-nt + 2\t),

Величина у(г + 1|/) не известна, поэтому используется ее оценка +11 0 в соответствии с (7):

у(1 + 21 Г) = £ + + д,у(/ Ю + ауЦ -11 /))+ \ 1) = = £ + + + а2у(?-1))+ .

В результате

*(/ + 210 + 2)-(£ + а1(е + ауЦ) + 1))+ а&М). (8)

Полученное выражение (8) подставляется в (6) при решении оптимизационной задачи для оценки параметров модели М(2) АРПСС (2,0,0).

Проведено сравнение точности прогноза искусственно сгенерированных рядов для известного (подход 1) и предложенного подхода (подход 2). Рассмотрены ряды для моделей АРПСС, характерных для социально-экономических показателей: АРПСС(р ,¿/,<7X^,0,6)12 с числом параметров /?,</,<7,/>,/},£> = 0,2, при этом р, ц, Р, <2 не равны нулю одновременно. Вычислительные эксперименты отличались следующим: числом параметров модели, использованной для генерации ряда (модель источника данных); видом модели АРПСС, использованной для протезирования ряда (прогнозной модели), в обычном режиме совпадавшей с моделью источника данных; значениями коэффициентов я,, 6>; длиной временного ряда (объемом выборки) п; шириной и> «окна», в пределах которого вычислялись прогнозные значения, далее использовавшиеся при сравнении; положением роз «окна» относительно начала ряда; горизонтом прогнозирования 1.

Проверялась нуль-гипотеза Нт о неизменности выборочного среднего ошибок прогноза вне зависимости от подхода:

Нт:тг=тг. (9)

Гипотеза (9) проверялась для критериев средней ошибки предсказаний А и среднеквадратичной ошибки предсказаний 3 :

А=-5>(о-т, (ю)

Х=.'-11(у(0-Л0)2. (И)

н-ы

Изменение критического уровня а, при котором Нт следует отвергнуть, в зависимости от размера выборки п показано на рисунке 1. Уровень

соответствует непараметрическому критерию Вилкоксона, который применялся вследствие отсутствия достаточных оснований считать распределения оценок нормальными.

1 о 08 -06 04 -

1000 500 300 200 100 л

□ средняя ошибка а среднеквадратичная ошибка

Рисунок 1 - Изменение критического уровня а, при котором следует отвергнуть гипотезу Нт, для критериев А и 2 в зависимости от размера

выборки п

В таблице 1 приведена сводная статистика изменения ошибок по критериям (10) и (11) в зависимости от плана и размера выборки. Значения для А и 2 нормированы относительно соответствующих величин при п = 10ОО. Для и = 100 отмечено уменьшение ошибки прогнозирования по предложенному алгоритму относительно известного на 8% по критерию (10) и на 6% по критерию (11).

Таблица 1 Изменение ошибок предсказания в зависимости от п

Величина п \ 1000| 500| 300| 200| 100

Средняя ошибка п редсказаний А

А для АРПСС 100 1 06 1 08 1 12 1 19

А для АРПСС, к шагов вперед 100 1.05 1.05 107 109

отношение А для АРПСС, к шагов вперед (подход 2), к А для АРПСС (подход 1) 0.997 0.984 0.971 0.956 0.919

значение статистики Вилкоксона 041 037 1 10 163 191

соответствующий уровень а 083 071 0.27 010 006

Среднеквадратичная ошибка предсказаний ~А

3 для АРПСС 100 107 1 11 1.18 124

X для АРПСС, к шагов вперед 1.00 1.06 109 1.13 1.16

отношение 5 для АРПСС, к тагов вперед (подход 2), к А для API ICC (подход 1) 1.005 0.997 0.988 0.957 0.937

значение статистики Вилкоксона -0.24 006 031 083 098

соответствующий уровень а 081 096 076 040 033

Таким образом, для сгенерированных дшгных выявлено превосходство предложенного подхода над известным в условиях малой выборки. Также определено, что оценки параметров, получаемые для предложенного алгоритма, имеют случайный разброс, статистически значимо не превышающий разброс для оценок, получаемых при известном способе идентификации, при уровне значимости а = 0.1. Это свидетельствует о стабильности оценок.

Проведена оценка вычислительной сложности предложенного алгоритма Для алгоритма идентификации модели получено выражение 0(пКм ), где К — число параметров модели АРПСС. Поэтому вычислительная сложность процедуры идентификации линейна относительно размера данных и экспоненциально связана с горизонтом прогнозирования /. Но при интересующих значениях / это не приводит к существенному замедлению вычислений. Операции расчета прогнозных значений имеют такую же сложность, что и для известного подхода.

Для выполнения вычислительных экспериментов разработана программа прогнозирования социально-экономических показателей по предложенному алгоритму. Реализация выполнена в среде комплекса SAS System, позволяющего производить статистическую обработку данных.

В разделе 3 решена задача разработки алгоритмов сжатия баз данных социально-экономических показателей. Исследованы вопросы реализации алгоритмов посредством комплекса программ.

Разработаны три алгоритма сжатия баз данных. Во всех случаях сжатие выполняется на уровне значений атрибута.

Первый алгоритм - словарное кодирование с сохранением упорядочивания, кратко обозначенный как Diet. Алгоритм основан на известном подходе и отличается сохранением упорядочивания для закодированных строк. Фразами р} словаря D являются уникальные значения

сжимаемой /'-й колонки (атрибута, столбца) /, некоторой таблицы. Словарь может разделяться несколькими колонками разных таблиц. Дня сохранения упорядочивания Pj сортируются в порядке, определенном для кодируемой

колонки. Номера фраз W^ ' являются кодовыми словами значений колонки. Кодирующее преобразование есть

t,{k)^Wi'\jui(k)=pJ,D = \pJ}, (12)

где 1,0е) - значение i -й колонки для k -й строки таблицы.

Для минимизации временных затрат, обусловленных перестройкой словаря, при кодировании нового значения номера равномерно распределяются по пространству возможных номеров, так что

(1

2+j\d +1)

(13)

где d - количество вакантных позиций между номерами при условии их

256'—i DI

равномерного распределения, d = ———', | D |> 0, | D \ - размер словаря.

Использование алгоритма предполагает, что для заданной колонки существующей таблицы определяется словарь, после чего значения колонки сжимаются. В дальнейшем при появлении новых значений атрибута словарь может изменяться.

Второй разработанный алгоритм сжатия - это статистическое кодирование на базе контекстного моделирования, кратко обозначенный как Context. Значения посимвольно кодируются с помощью арифметического кодера. Оценки вероятностей символов формируются способом предсказания по частичному совпадению. Оценка вероятности q(s) символа s определяется наблюдаемой частотой его появления для набора текущих, или активных контекстов. Под активным контекстом CL понимается строка фиксированной длины L, обработанная непосредственно перед оценкой текущего символа s. Совокупность счетчиков символов для некоторого контекста CL образует контекстную модель СМ1'. Оценка вероятности q(s) в соответствии с предсказанием по частичному совпадению производится по формуле

q(s) = q(s\CML)- f\q(e\CMk) (14)

¿=¿+1

где q(s\CML) - оценка вероятности 5 для CML, в которой s был успешно оценен, т.е. q(s j CML) > 0; N - максимальная длина контекстов; q(e | СМк) -оценка вероятности ухода из С.Мк вследствие невозможности оценить s (символ s ранее не встречался в соответствующем контексте С1).

Вероятность символа ухода е рассчитывается по так называемому методу D:

q(e\CML) = -- ?-/V (15)

у{с'У

где а количество разных х в СМ'; f(cL) - общее число просмотров

контекста С1', соответствующего СМ1.

Максимальная длина контекстов ограничивается небольшим числом N, L<N. Использовался порядок N = 1 для уменьшения затрат памяти и времени при декодировании.

За счет сортировки счетчиков в соответствии с алфавитным порядком символов достигается сохранение упорядочивания. При кодировании числовых данных необходимы промежуточные обратимые преобразования, позволяющие сравнивать числа в прямом порядке образующих их байтовых значений, т.е. как обычные строки.

Третьим разработанным способом сжатия является алгоритм словарного кодирования с учетом горизонтальных зависимостей между колонками таблицы, кратко Depend. Словарь, используемый при обработке очередного значения атрибута, зависит от текущего значения набора некоторых факторных колонок - детерминанта О. При сильной зависимости сжимаемой колонки /, от

а = {tam,...,ta(jy...,ta(z)} , «(/)*/, размер словаря может существенно уменьшаться относительно числа всех уникальных значений колонки 1г. При обработке используется совокупность словарей Dn. Каждый словарь Dn содержи! только уникальные значения обрабатываемой колонки, встречающиеся для некоторого уникального значения Оя детерминанта. Кодирующее преобразование имеет вид

/,(*)-> У U,(k)=pf\№ = nn,Dn=\pM\, (16)

где W{"'J ) - кодовое слово фразы р(п) для словаря Dn; Q^ значение

детерминанта для текущей строки с номером к.

При выборе детерминанта должна минимизироваться стоимость

c = L(D)+Lc, (17)

где / (£>) - размер представления общего словаря D =-{£>„} ; Lc - размер сжатых данных колонки t,.

Оптимальный алгоритм минимизации стоимости (17) сводится к перебору и имеет экспоненциальную сложность вычислений, что может быть неприемлемо для больших таблиц. Для определения П предложено использовать разработанный субоптимальный алгоритм с полиноминальной сложностью, в котором используется обучающая (тестовая) выборка.

Алгоритм Е>еретк1 не обеспечивает сохранения упорядочивания, но позволяет достигать сильного сжатия при тесных зависимостях между колонками, что характерно для таблиц фактов при их денормализации.

Для всех алгоритмов сжатия определены минимальный и максимальный коэффициент сжатая. Оценена сложность кодирования и декодирования, для всех алгоритмов линейная или фиксированная относительно размера входных данных.

Для проведения вычислительных экспериментов разработан программный комплекс, обеспечивающий функциональность ядра реляционной СУБД с поддержкой обработки и хранения сжатых данных. Реализованы основные операторы плана выполнения запроса, позволившие оценить скорость выполнения типичных запросов к базе данных социально-экономических показателей.

В разделе 4 представлены результаты вычислительных экспериментов с программными реализациями разработанных алгоритмов.

Произведено сравнение точности прогноза для предложенного алгоритма, известного подхода с использованием модели АРПСС и прогнозирования с применением модели экспоненциального сглаживания (ЭП). Использовались месячные ряды. Усредненные результаты сравнения прогнозов на тестовой выборке для 40 временных рядов разных показателей даны в таблице 2 ниже. Соответствующие величины ошибок прогноза по критериям (10) и (11) для М(1) взяты за единицу. Сравнение производилось при прогнозе на 6 месяцев вперед.

Таблица 2 - Сравнение нормированных ошибок прогноза на тестовой выборке

Критерий Модель, использованная для прогноза на к тагов вперед

Мт при ¡Мт,к = 1 Мт,к = 1,6 ЭП

V* = 1,6 [Мт,к = 23

А 1 0.97 0.95 0.94 1.32

X 1 0.98 0.97 0.% 137

Относительно известного подхода с применением АРПСС по критерию (10) отмечено повышение точности прогноза на 6%, по критерию (11)- на 4% при прогнозировании на 6 месяцев вперед. Рассмотренный для сравнения подход на основе ЭП показал существенно худшие результаты. В качестве иллюстрации на рисунке 2 для одного из показателей даны графики:

реального ряда (обозначен как "у"), прогнозных значений для модели Мт ("к = 1"), прогнозных значений для комбинации Мт и М<2) {'к = 2"), прогнозных значений для набора М(*\ к = Г,6 ("к = 6").

Время

Рисунок 2 - Прогнозные значения для коэффициента рождаемости

Для тестовой базы данных социально-экономических показателей определены изменение скорости выполнения типовых запросов и размера хранимых данных при использовании сжатия. Сводные показатели изменения скорости представлены на рисунках 3 и 4. Для рассмотренной базы сжатие позволило повысить скорость выполнения ряда типовых операций на 20-25%, а для некоторых запросов - почти в 7 раз. Разница увеличивается при невозможности котирования существенной части таблицы. Размер хранимых данных сократился в 725 раза. Характеристики сравнивались с показателями для СУБД MySQL, поддерживающей сжатие данных. Для СУБД MySQL не отмечено увеличения производительности в случае применения сжатия данных.

□ Несжатая таблица, нет кеша

04

I 0 34

вв Несжатая таб/мцн, кеш н Сжатая таблица, нет кеша

I 02 &

m

ш Сжатая таблица, нет кеша, без учета

инициатизации декодирования щ Сжатая таблица, кеш

г Сжатая таблица, кеш, без учета инициализации декодирования

Рисунок 3 - Среднее время выполнения запросов при индексном доступе

□ Несжатая табгмца, нет кеша

а Несжатая табшца, кеш

ш Сжатая табтца, нет кеша

в Сжатая табтца, нет кеша, без учета

инициализации декодирования о Сжатая таблица, кеш

□ Сжатая тэбгеца, кеш, без учета инкратзации декодирования

Рисунок 4 - Среднее время выполнения запросов при последовательном

доступе

С помощью разработанного комплекса программ было осуществлено прогнозирование развили Санкт-Петербурга по 9 показателям, по которым имелись самые последние на момент исследования данные. Прогноз выполнен до июня 2005 года, базу прогноза составили значения с 1999 по 2004 годы.

В заключении перечислены основные результаты, полученные в дисссртащюнной работе.

Приложения. В приложении А изложены необходимые понятия об устройстве и функционировании реляционной СУБД, используемые в работе. Примеры кодирования для разработанных алгоритмов сжатия баз данных представлены в приложении Б. Результаты прогнозирования важных социально-экономических показателей развития Санкт-Петербурга приведены в приложении В. Описание сжимаемой базы данных дано в приложении Г.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе набора моделей АРПСС, идентифицируемых для прогноза ровно на заданное к шагов вперед. Предложен способ идентификации моделей для прогнозирования ровно на к шагов вперед. Определена вычислительная сложность алгоритма

2. Разработан алгоритм словарного кодирования, при котором фразами словаря выступают значения сжимаемого атрибута. Алгоритм обеспечивает сохранение упорядочивания сжатых данных.

3. Предложен алгоритм статистического кодирования с использованием контекстного моделирования. Алгоритм обеспечивает сохранение

упорядочивания и не требует больших временных затрат при кодировании новых, ранее не встречавшихся значений атрибута.

4. Разработан алгоритм словарного кодирования с учетом горизонтальных зависимостей между колонками таблицы, при котором словарь, используемый для обработки текущего значения столбца, зависит от текущего значения некоторого набора «факторных» столбцов. Алгоритм обеспечивает сильное сжатие данных в случае детерминированной или тесной зависимости ■ между столбцами таблицы.

5. Все алгоритмы сжатия данных обеспечивают произвольный доступ к закодированному значению колонки. Определена вычислительная сложность ' алгоритмов, предельные значения коэффициента сжатия.

6. Предложенные алгоритмы программно реализованы. Создан комплекс программ, обеспечивающий прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных.

7. Проведены вычислительные эксперименты, показавшие, что использование алгоритмов сжатия баз данных социально-экономических показателей привело к ускорению выполнения типовых запросов на 20-25% и уменьшению размера хранимых данных в 725 раза.

8. Проведены вычислительные эксперименты для проверки величины ошибки прогноза, получаемой для разработанного алгоритма. Точность предсказания макросоциальных и макроэкономических показателей Санкт-Петербурга на несколько процентов выше, чем для известного подхода.

9. С помощью разработанного комплекса программ выполнено прогнозирование 9 важных социально-экономических показателей развития Санкт-Петербурга на 2005 год.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

4

1 Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А.Ратушняк, М.Смирнов, В.Юкин. М.: ДИАЛОГ-МИФИ, 2002.384 с.

2 Осипов Л.А., Смирнов М.А. Автопрогнозирование социально-экономических показателей посредством совокупности специализированных моделей // Информационно-управляющие системы. 2004. №2. СПб. С. 50-54.

3 Осипов Л.А., Смирнов М.А. Использование методов сжатия данных без потерь информации в условиях жестких ограничений на ресурсы устройства-декодера // Информационно-управляющие системы. 2004. №4. СПб. С. 7-15.

4 Осипов Л.А., Смирнов М.А. Использование экономного кодирования информации для повышения производительности хранилищ данных // IX Санкт-Петербургская международная конференция "Региональная информаггика-2004 (РИ-2004)", СПб, 2004. С. 212.

5 Смирнов М.А. Использование методов безущербного сжатия данных в СУБД // Седьмая научная сессия аспирантов ГУАП. Сборник докладов в 2 частях. 4.1. Технические науки. СПб, 2004. С. 370-373.

6 Смирнов М.А. Об одном подходе к автопрогнозированию показателей социально-экономического развитая региона // Управление и информационные технологии // Всероссийская научная конференция 34 апреля 2003 г. Санкт-Петербург. Сборник докладов в двух томах. Том 2.2003. С. 239-243.

7 Смирнов М.А. Об одном подходе к построению критерия оптимизации при решении задачи автопрогнозирования социально-экономических показателей // Шестая научная сессия аспирантов ГУАП. Сборник докладов в 2 частях. 4.1. Технические науки. СПб, 2003. С. 295-298.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ № 242

Отпечатано в отделе оперативной полиграфии ГУАП

190000, Санкт-Петербург, ул. Б. Морская, 67

»И 436 1

РНБ Русский фонд

2006-4 10364

i

Аббревиатуры и сокращения.

Введение.

1 Анализ подходов к прогнозированию социально-экономических показателей и сжатию баз данных. Постановка задач исследования.

1.1 Цель исследования.

1.2 Анализ способов решения задачи прогнозирования социально-экономических показателей.

1.2.1 Характерные особенности прогнозирования социально-экономических показателей.

1.2.2 Известные способы решения задачи прогнозирования.

1.2.3 Выбор подхода к прогнозированию.

1.3 Анализ подходов к решению задачи компактного представления баз данных социально-экономических показателей.

1.3.1 Особенности баз данных социально-экономических показателей.

1.3.2 Методы повышения производительности СУБД.

1.3.3 Использование методов сжатия данных без потерь информации в СУБД.

1.4 Постановка задач исследования.

1.5 Выводы.

2 Прогнозирование социально-экономических показателей.

2.1 Модель авторегрессии и проинтегрированного скользящего среднего.

2.2 Построение прогностических моделей.

2.3 Вычислительные эксперименты на искусственно сгенерированных данных.

2.3.1 Описание экспериментов и результаты.

2.3.3 Эксперименты для ряда с моделью АРПСС (2,0,0).

2.4 Оценка сложности вычислений для предлагаемого подхода.

2.5 Выводы.

3 Алгоритмы сжатия баз данных социально-экономических показателей без потерь информации.

3.1 Словарное кодирование с сохранением упорядочивания Diet.

3.2 Статистическое кодирование на базе контекстного моделирования Context.

3.2.1 Понятия и определения.

3.2.2 Описание алгоритма.

3.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend.

3.3.1 Описание алгоритма.

3.3.2 Определение набора факторных колонок (детерминанта).

3.4 Теоретические оценки наилучшего и наихудшего коэффициента сжатия.

3.4.1 Словарное кодирование с сохранением упорядочивания Diet.

3.4.2 Статистическое кодирование на базе контекстного моделирования Context.

3.4.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend.

3.5 Теоретические оценки скорости выполнения основных операций поиска и извлечения данных из БД в зависимости от коэффициента сжатия.

3.6 Теоретические оценки сложности алгоритмов экономного кодирования.

3.6.1 Словарное кодирование с сохранением упорядочивания Diet.

3.6.2 Статистическое кодирование на базе контекстного моделирования Context.

3.6.3 Кодирование с учетом горизонтальных зависимостей между колонками Depend.

3.7 Сводные теоретические характеристики разработанных алгоритмов.

3.8 Выводы.

4 Вычислительные эксперименты по прогнозированию показателей развития Санкт-Петербурга и сжатию базы данных.

4.1 Прогнозирование социально-экономических показателей.

4.1.1 Описание эксперимента.

4.1.2 Результаты эксперимента.

4.2 Экономное кодирование информации базы данных социально-экономических показателей.

4.2.1 Общая характеристика реализации.

4.2.2 Реализация физических операторов.

4.2.3 Описание эксперимента.

4.2.4 Результаты эксперимента.

4.2.5 Сравнение с СУБД Sybase IQ.

4.3 Выводы.

Актуальность темы. Прогнозирование показателей социально-экономических процессов региона используется в системах поддержки принятия решений как при государственном управлении, так и при управлении масштабной организацией. Вопрос получения прогноза, при котором используется ретроспективная информация о поведении только прогнозируемого показателя, актуален как для задач вычисления прогнозных значений отдельных показателей в кратко- и среднесрочной перспективе, так и для задач комплексного прогнозирования социально-экономического развития. В последнем случае прогнозирование в сочетании с экспертными оценками может применяться при формировании сценариев эволюции экономической системы для комплексного имитационного моделирования развития субъекта Российской Федерации. Применение комплексной модели позволяет достичь сбалансированности прогнозных значений макроэкономических показателей.

Необходимая интерактивность анализа и прогнозирования социально-экономических процессов должна обеспечиваться не только благодаря эффективным алгоритмам обработки данных и прогнозирования, но и за счет быстрого выполнения операций извлечения необходимых данных. При прогнозировании большого числа рядов значений, извлекаемых из БД, основная доля затрачиваемого времени может приходиться на обработку запроса в СУБД. Большой объем баз данных социально-экономических показателей диктует необходимость использования специальных методов повышения производительности СУБД.

Целью работы является разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона, а также повышение производительности систем управления большими базами данных социально-экономических показателей за счет использования сжатия данных.

Задачами диссертационного исследования являются:

• разработка алгоритма кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе модели авторегрессии и проинтегрированного скользящего среднего;

• разработка алгоритмов сжатия баз данных социально-экономических показателей без потерь информации для повышения производительности СУБД;

• реализация предложенных алгоритмов в виде комплекса программ, обеспечивающего прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных;

• проведение вычислительных экспериментов по прогнозированию социально-экономических показателей развития субъекта Российской Федерации, по оценке точности прогноза, получаемого для разработанного алгоритма, по оценке изменения скорости выполнения типовых запросов и уменьшения размера хранимых данных в случае использования алгоритмов сжатия базы данных.

Методы исследования. Для решения поставленных задач в работе использованы: теория вероятностей, математическая статистика, нелинейное программирование, анализ временных рядов, теория кодирования дискретных источников сообщений, теория сложности алгоритмов.

Основные положения, выносимые на защиту:

1. Алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона на основе набора моделей авторегрессии и проинтегрированного скользящего среднего (АРПСС).

2. Алгоритмы сжатия баз данных без потерь информации, основанные на словарном и статистическом кодировании с использованием контекстного моделирования.

3. Комплекс программ, обеспечивающий кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона при условии хранения и обработки сжатых данных.

4. Результаты вычислительных экспериментов по прогнозированию, по оценке точности прогноза для предложенного алгоритма, по оценке изменения скорости выполнения запросов к сжатой базе данных и уменьшения размера хранимых данных.

Научная новизна работы состоит в следующем:

• разработанный алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона отличается использованием набора моделей класса АРПСС, каждая из которых идентифицируется для прогнозирования ровно на к шагов вперед;

• предложенный алгоритм словарного кодирования для применения в СУБД обеспечивает сохранение упорядочивания и позволяет минимизировать число перестроек словаря при появлении новых значений; разработанный алгоритм словарного кодирования с учетом горизонтальных зависимостей обеспечивает сильное сжатие данных в случае детерминированной или тесной зависимости между столбцами таблицы;

• разработанный алгоритм статистического кодирования с использованием контекстного моделирования, предназначенный для применения в СУБД, обладает свойством сохранения упорядочивания и не требует больших временных затрат при кодировании новых, ранее не встречавшихся значений атрибута;

• разработанный комплекс программ обеспечивает кратко- и среднесрочное прогнозирование показателей социально-экономического развития региона по предложенному алгоритму и отличается возможностью хранения и обработки сжатых данных для повышения скорости обработки запросов.

Практическая ценность. Разработан алгоритм прогнозирования социально-экономических показателей развития региона. Предложены алгоритмы сжатия баз данных социально-экономической информации. Создан комплекс программ, обеспечивающий кратко- и .среднесрочное прогнозирование показателей социально-экономического развития региона и позволяющий хранить и обрабатывать сжатые данные. При выполнении вычислительных экспериментов показано, что реализация разработанного алгоритма прогнозирования позволяет увеличить точность предсказания, а реализация алгоритмов сжатия баз данных — достичь более компактного представления хранимых данных и большей скорости обработки запросов, чем известный аналог. Результаты работы могут быть использованы в автоматизированных информационных системах анализа и прогнозирования развития территории.

Внедрение и реализация результатов работы. Основные теоретические и практические результаты были внедрены и использованы в комплексе программ для анализа социально-экономических процессов Санкт-Петербурга и комплексного имитационного моделирования развития субъекта Российской Федерации на примере Санкт-Петербурга. Результаты работы были получены при выполнении хозяйственной договорной научно-исследовательской работы (НИР №199), проведенной Санкт-Петербургским государственным университетом аэрокосмического приборостроения по заданию СПб ГУП «Санкт-Петербургский информационно-аналитический центр».

Полученные в диссертационной работе результаты используются в учебном процессе кафедры вычислительных машин и комплексов ГУАП.

Апробация работы. Основные положения докладывались на: международной конференции «Региональная информатика - 2004» (г. Санкт-Петербург, 22-24 июня 2004 г.), всероссийской научной конференции «Управление и информационные технологии» (г. Санкт-Петербург, 3-4 апреля 2003 г.), трех научных сессиях аспирантов и молодых ученых ГУАП (г. Санкт-Петербург, 2002-2004 годы).

По теме работы опубликовано 7 печатных работ, в том числе одна монография.

4.3 Выводы

Результаты описанных вычислительных экспериментов были опубликованы автором в работах [67,68, 69, 75, 76].

1. Получены результаты сравнительного анализа точности прогнозирования социально-экономических показателей развития Санкт-Петербурга для предложенного и известного способа прогнозирования на основе моделей АРПСС, а также метод прогнозирования с использованием модели экспоненциального сглаживания.

Вычислительным экспериментом на представительном наборе рядов СЭП показано, что за счет использования разработанного подхода при неизменном количестве параметров модели на несколько процентов повышается точность прогноза на определенное число шагов вперед. Отмечено среднее увеличение точности прогноза на 6% по критерию средней ошибки предсказаний А и на 4% по критерию среднеквадратичной ошибки предсказаний Л на горизонте прогнозирования 1 = 6 месяцев.

2. Получены экспериментальные оценки изменения скорости выполнения запросов и изменения размера хранимых данных при сжатии баз данных социально-экономических показателей без потерь информации.

Предложенные алгоритмы сжатия позволили достичь в разы более компактного представления таблицы значений СЭП. Получен коэффициент сжатия К =0.138, что соответствует уменьшению размера хранимых данных в 7.25 раза. При этом во многих ситуациях скорость выполнения типовых запросов UC3IC для сжатой БД по меньшей мере не упала, что выгодно отличает экспериментальную программу от стандартной СУБД MySQL, также поддерживающей сжатие данных. Это демонстрирует эффективность применения алгоритмов сжатия с сохранением упорядочивания, часто позволяющих выполнять обработку данных без их предварительного декодирования.

Простые запросы, требующие извлечения небольших порций данных по индексированным атрибутам, выполняются в типичной ситуации примерно с одинаковой скоростью U на несжатых данных и сжатых по предложенным алгоритмам, если не учитывать однократные временные затраты на инициализацию программных модулей декодеров. Если при отсутствии подходящей индексной структуры доступ реализуется через последовательное сканирование таблицы, то скорость U^ выполнения запроса к сжатым данным выше на 20-25%.

Сделанные оценки и выкладки показывают, что нет оснований считать скорость обработки типовых запросов в специализированной СУБД Sybase IQ выше, чем в предложенной реализации CDB.

Заключение

1. Разработан и исследован алгоритм кратко- и среднесрочного прогнозирования показателей социально-экономического развития региона.

• Предложен способ идентификации моделей класса АРПСС для прогнозирования ровно на к шагов вперед. Предложен алгоритм прогнозирования на основе применения набора таких моделей.

• Проанализированы результаты прогнозирования по предложенному алгоритму на искусственно сгенерированных данных. Выявлена стабильность оценок параметров модели. Ошибка прогноза, получаемая для предложенного алгоритма, статистически значимо не отличается от ошибки прогноза для известного подхода. Отмечено улучшение точности прогнозирования относительно моделей, получаемых при известном типовом способе идентификации модели АРПСС для сгенерированных рядов длиной п < 1000.

• Получена оценка сложности вычислений оценок параметров при использовании предложенного подхода, равная 0(пКм), где К— число параметров модели АРПСС, / — горизонт прогнозирования. Трудоемкость вычислений экспоненциально зависит от /, но степенная составляющая зависит только от К, К «п.

Сложность собственно расчета прогнозных значений не отличается от сложности расчетов при обычном подходе, что определяет практическую ценность алгоритма.

2. Разработаны и исследованы алгоритмы сжатия баз данных социально-экономических показателей без потерь информации, допускающие возможность эффективного выполнения запросов непосредственно над сжатыми данными в целях повышения производительности систем управления большими базами данных.

• Разработан алгоритм словарного кодирования, при котором фразами словаря выступают значения атрибута. Алгоритм обеспечивает сохранение порядка сортировки (свойство сохранения упорядочивания). Показано, что время кодирования линейно зависит от размера входных данных, а декодирование имеет сложность 0(l).

• Разработан алгоритм статистического кодирования с использованием контекстного моделирования. Алгоритм обеспечивает сохранение упорядочивания и не требует больших временных затрат при кодировании новых, ранее не встречавшихся значений атрибута. Показано, что время кодирования и декодирования линейно относительно размера входных данных в практической ситуации.

• Разработан алгоритм словарного кодирования с учетом горизонтальных зависимостей между колонками таблицы, при котором словарь, используемый для обработки текущего значения столбца, зависит от текущего значения некоторого набора других столбцов — детерминанта Q. Алгоритм обеспечивает сильное сжатие данных в случае детерминированной или сильной зависимости между столбцами таблицы. Предложен субоптимальный алгоритм нахождения структуры Q. Показано, что время кодирования линейно относительно размера входных данных и размера значения Q, а время декодирование линейно относительно размера значения Q.

• Все предложенные алгоритмы отличаются тем, что обеспечивают произвольный доступ к сжатым данным на уровне значения атрибута.

• Получены теоретические оценки скорости выполнения основных операций поиска и извлечения данных из БД в зависимости от коэффициента сжатия К. Определены предельные значения коэффициентов сжатия для всех алгоритмов.

• Определены области предпочтительного применения алгоритмов.

3. Создан комплекс программ, обеспечивающий прогнозирование социально-экономических показателей развития региона по предложенному в работе алгоритму. Разработан комплекс программ управления данными по социально-экономическим показателям, отличающийся возможностью хранения и обработки сжатых данных для повышения скорости обработки запросов.

4. Проведены вычислительные эксперименты для проверки величины ошибки прогноза, получаемой для разработанного алгоритма, в сравнении с известными подходами на наборе социально-экономических показателей Санкт-Петербурга. Для рассмотренных рядов отмечено среднее увеличение точности прогноза на 6% по критерию средней ошибки предсказаний А и на 4% по критерию среднеквадратичной ошибки предсказаний X на горизонте прогнозирования 1 = 6 месяцев.

Выполнены вычислительные эксперименты для оценки изменения скорости выполнения типовых запросов и изменения размера хранимых данных в случае использования алгоритмов сжатия на примере реальной базы данных социально-экономических показателей субъектов Российской Федерации.

• Для таблицы значений показателей тестовой БД СЭП получен коэффициент сжатия К = 0.138, что соответствует уменьшению размера хранимых данных в 7.25 раза и существенно лучше результата, полученного для стандартной СУБД MySQL, также поддерживающей сжатие данных.

• Простые запросы, требующие извлечения небольших порций данных по индексированным атрибутам, выполнялись разработанным программным комплексом в типичной ситуации примерно с одинаковой скоростью на несжатых и сжатых данных, если не учитывать однократные временные затраты на инициализацию декодирования табличных данных. Если в случае отсутствия подходящей индексной структуры доступ реализовывался через последовательное сканирование таблицы, то скорость выполнения запроса к сжатым данным выше на 20-25%. При этом для СУБД MySQL скорость обработки запросов к сжатым данным неизменно ниже скорости запросов к несжатым данным.

Таким образом, разработанный автором алгоритм кратко- и среднесрочного прогнозирования социально-экономических показателей региона обеспечивает большую точность прогноза, чем известные подходы на базе моделей авторегрессии и проинтегрированного скользящего среднего, при несущественном росте вычислительных затрат на выполнение процедуры оценки параметров модели.

Разработанные автором алгоритмы сжатия баз данных обеспечивают не только более компактное представление хранимых данных по социально-экономическим показателям и соответствующую экономию внешней постоянной памяти, но и повышение скорости обработки характерных запросов к данным.

1. Цыбатов В.А., Дубровин Д.В. Методы, модели и системы прогнозирования регионального развития: Учеб. пособие / Под ред. Г.Р. Хасаева. Самара: Изд-во Самар. гос. экон. акад., 2003. 248 с.

2. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Исследование зависимостей. М.: Финансы и статистика, 1985, 487 с.

3. Айвазян С.А., Мхитарян B.C. Прикладная статистика и основы эконометрики: Учебник для вузов. М.: ЮНИТИ, 1998. 1022 с.

4. Box G.E.P., Jenkins G.M., Reinsel G.C. Time Series Analysis: Forecasting and Control. Third Edition. Englewood Cliffs, NJ: Prentice Hall, 1994, p. 575.

5. Pollock D.S.G. A Handbook of Time-Series Analysis, Signal Processing and Dynamics. Academic Press, 1999. 784 p.

6. Gardner E.S., Jr. Exponential smoothing: The state of the art. Journal of Forecasting, n.4, 1985, p. 1-28.

7. Кульдишев Г.С., Френкель A.A. Анализ временных рядов и прогнозирование. М: Статистика, 1973. 103 с.

8. SAS Institute Inc., SAS OnlineDoc®, Version 8, Сагу, NC: SAS Institute Inc., 1999. http://v8doc.sas.com/sashtml/

9. Лукашин Ю.П. Анализ временных рядов по методу интегрированной авторегрессии—скользящей средней. М.: АН СССР. Ин-т мировой экономики и междунар. отношений, 1975. Вып. 5. 80 с.

10. Грицевич И.Г. Моделирование временных рядов с помощью схем Бокса-Дженкинса // Математические методы в экономике и международных отношениях. М.: ИМЭМО, 1974. Вып. 3.

11. Engle R. Autoregressive Conditional Heteroscedasticity with Estimates of the Variance of United Kingdom Inflations. Econometrica, n. 50, 1982, p.987-1008.

12. Bollerslev T. Generalized Autoregressive Conditional Heteroscedasticity. Journal of Econometrics, n. 31, 1986, p.307-327.

13. Greene W.H. Econometric analysis. Second edition. Macmillan Publishing Company, New York, 1993, p. 1000.

14. Шеппард Н. Статистические аспекты моделей типа ARCH и стохастическая волатильность //Обозрение прикладной и промышленной математики. Т.З, вып.6, 1996. С. 765-828.

15. Абрамович М.С. Применение непараметрических спектральных методов для обработки временных рядов с неоднородностями: Автореф. диссертации канд. физ.-мат. наук (05.13.16), Минск: Белорус, гос. ун-т., 1999. 20 с.

16. Гренджер К., Хатанака М. Спектральный анализ временных рядов в экономике. М.: Статистика, 1972. 167 с.

17. Модели временных рядов с приложениями в гидрометеорологии / В.Е. Привальский, В.А. Панченко, Е.Ю. Асарина. СПб: Гидрометеоиздат, 1992.226 с.

18. Теребеж В.Ю. Анализ временных рядов в астрофизике. М.: Наука, 1992. 391 с.

19. Труш Н.Н. Статистический спектральный анализ временных рядов: Автореф. диссертации канд. физ.-мат. наук (01.01.05), Минск: Белорус, гос. ун-т, 1999. 40 с.

20. Безверхний В.А. Спектральный анализ коротких рядов наблюдений. М.: Б.И., 1986. 26 с.

21. Малинов В.А. Адаптивное оценивание тренда с регулированием интервала наблюдений: Автореф. диссертации канд. техн. наук (05.13.01), Горький: Горьковский политехнический институт им. А.А. Жданова, 1983. 19 с.

22. Ефимов В.М., Галактионов Ю.К., Шушпанова Н.Ф. Анализ и прогноз временных рядов методом главных компонент / Отв. ред. Ю.С. Равкин. Новосибирск: Наука. Сиб. отд-ние. 68 с.

23. Меленец Ю.В. Анализ временных рядов с периодическими временными характеристиками: Автореф. диссертации канд. физ.-мат. наук (01.01.05), Минск: Белорус, гос. ун-т, 1984. 15 с.

24. Степанова Н.В. Выделение трендов временных рядов при измерениях, производимых в случайные моменты времени: Автореф. диссертации канд. физ.-мат. наук (05.13.16), Томск: Томский государственный университет им. В.В. Куйбышева, 1987. 15 с.

25. Зеленко JI.C. Методы, алгоритмы и программное обеспечение корреляционного анализа неэквидистантных временных рядов: Автореф. диссертацииканд. техн. наук (05.13.16), Самара: Самарский гос. аэрокосм, ун-т им. акад. С.П. Королева, 1994. 17 с.

26. Зенкин А.И., Уразаев Р.П. Об одной модели прогнозирования случайных процессов. М.: ВЦ АН СССР, 1986. 14 с.

27. Уразаев Р.П. Методы генерации алгоритмов прогнозирования при помощи операций над базовыми алгоритмами. М.: ВЦ АН СССР, 1988.25 с.

28. Полищук Ю.М., Ципилева Т.А. Новый подход к обработке временных нестационарных процессов. Томск: ТФ СО АН СССР, 1988. 23 с.

29. Мельникова Е.Н. Классификация и оценивание параметров временных рядо-ав с многократными "разладками": Автореф. диссертации канд. физ.-мат. наук, Минск: Белорус, гос. ун-т, 1992. 21 с.

30. ЧижД.А. Прогнозирование структуры земельного фонда с использованием цепей Маркова //Проблемы прогнозирования. 1999. N4. С. 150-152.

31. Головченко В.Б. Прогнозирование временных рядов по разнородной информации / Отв. ред. чл.-корр. РАН С.Н. Васильев; Рос. акад. наук, Сибирское отд., Ин-т динамики систем и теории управления. Новосибирск: Наука, 1999. 86 с.

32. Garcia-Molina Н., Ullman J.D., Widom J. Database System Implementation. — New Jersey: Prentice Hall. 653 p.

33. Graefe G. Query Evaluation Technique for Large Databases // ACM Computing Surveys, 25(2), June 1993, p. 73-170.

34. Ramakrishnan R., Gehrke J. Database Management Systems. McGraw-Hill, 2001.906 p.

35. Iyer B.R., Wilhite D. Data Compression Support in Databases. In Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, 1994, p. 695-704.

36. Chen Z. Building Compressed Database Systems. A Dissertation Presented to the Faculty of the Graduate School of Cornell University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy, Aug. 2002, p. 165.

37. Ruth S., Keutzer P. Database Compression for Large Business Files. Datamation, 18, Sept. 1972, p. 62.

38. Alsberg P.A. Space and Time Savings Through Large Data Base Compression and Dynamic Restructuring. Proc. IEEE 63(8), August 1975, p. 1114-1122.

39. The Implementation and Performance of Compressed Databases / T. Westmann, D. Kossmann, S. Helmer, G. Moerkotte. SIGMOD Record, 29(3), 2000, p. 55-67.

40. Goldstein J., Ramakrishnan R., Shaft U. Compressing relations and indexes. Proc. IEEE Conf. on Data Engineering, Orlando, FL, USA, 1998, p. 370-379.

41. Roth M.A., Van Horn S. Database compression. ACM SIGMOD Record, 22(3), Sept. 1993, p. 31-39.

42. Li J., Rotem D., Wong H. A New Compression Method with Fast Searching on Large Databases. Proceedings of 13th International Conference on Very Large Data Bases, 1987, Brighton, p. 311-318.

43. Eggers S., Olken F., Shoshani A. A Compression Technique for Large Statistical databases. Proc. VLDB Conf, September 1981, p. 424-434.

44. Eggers S., Shoshani A. Efficient Access of Compressed Data Performance. Proc. VLDB, Montreal, Oct. 1980, p. 205.

45. Data Compression in a Pharmaceutical Drug Candidate Database / Z.B. Miled, H. Li, O. Bukhres, M. Bern, R. Jones, R. Oppelt. Informatica (Slovenia) 27(2), 2003, p. 213-224.

46. Cormack G.V. Data Compression in Database Systems. Comm. of ACM, 28(12), December 1985, p. 1336-1342.

47. Antoshenkov G. Dictionary-based order-preserving string compression. In VLDB Journal, 6(1), 1997, p. 26-39.

48. Ray G. Data Compression in Databases. Master's Thesis, Dept. of Computer Science and Automation, Indian Institute of Science, June 1995.

49. Ray G., Haritsa J., Seshadri S. Database compression: A performance enhancement tool. In Proc. COMAD, Pune, India, December 1995.

50. Bassiouni M., Mukherjee A., Tzannes N. Experiments on Improving the Compression of Special Data Types. Proc. IEEE Data Compression Conference, Snowbird, Utah, April 8-11, 1991, p. 433.

51. Bell Т., Witten I, Cleary J. Modeling for Text Compression HACM Computing Surveys, Vol.21, No.4, Dec. 1989, p.557-591.

52. Zandi A., Iyer В., Langdon G. Sort Order Preserving Data Compression for Extended Alphabets. IEEE Data Compression Conf., Snowbird, Utah, March 30 -April 1, 1993, p. 330-339.

53. Morris M. Teradata Multi-Value Compression V2R5.0. A Teradata White Paper, EB-3099, July 2002.

54. Poess M. Table Compression in Oracle9/ Release 2: A Performance Analysis. An Oracle White Paper, January 2003.

55. Ng W.K., Ravishankar C.V. Block-Oriented Compression Techniques for Large Statistical Databases. Knowledge and Data Engineering, 9(2), 1997, p. 314-328.

56. Ng W.K., Ravishankar C.V. Relational Database Compression Using Augmented Vector Quantization. ICDE 1995, p. 540-549.

57. Ng W.K., Ravishankar C.V., Chinya V. Data compression system and method representing records as differences between sorted domain ordinals representing field values. US Patent 5,603,022. Feb. 1997.

58. Vo B.D., Vo K-P. Using Column Dependency to Compress Tables. Proc. IEEE Data Compression Conference, Snowbird, Utah, March 23-25, 2004, p. 92-101.

59. Engineering the compression of massive tables: an experimental approach. / A.L. Buchsbaum, D.F. Caldwell, K.W. Church, G.S. Fowler, S. Muthukrishnan Proc. 11th Annual ACM-S1AM Symposium on Discrete Algorithms, 2000, p. 175184.

60. Indexing and Compression in Data Warehouses / K. Goyal, K. Ramamritham, A. Datta, H. Thomas. Technical Report, Indian Institute of Technology, Bombay, April 1999.

61. Stockinger K. Multi-Dimensional Bitmap Indices for Optimising Data Access within Object Oriented Databases at CERN. PhD. Nov. 2001.

62. Indexing and Compression in Data Warehouses / K.B. Goyal, K. Ramamritham, A. Datta, H.M. Thomas. Proceedings of the Int'l. Workshop Design and Management of Data Warehouses '99, Heidelberg, Germany, June 14-15, 1999.

63. Johnson T. Performance Measurements of Compressed Bitmap Indices. Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999 (VLDB'99), Edinburgh, Scotland, UK, p. 278-289.

64. Сушков Ю.А. Об одном способе организации случайного поиска //Исследование операций и статистическое моделирование: Межвуз. сб. научн. тр./Л.: ЛГУ, 1972. Вып. 1.

65. Hayes В. The Vibonacci Numbers. American Scientist, Vol. 87, No. 4, July-August 1999, p. 296-301.

66. Осипов JI.A., Смирнов М.А. Автопрогнозирование социально-экономических показателей посредством совокупности специализированных моделей // Информационно-управляющие системы. 2004. №2. СПб. С. 50-54.

67. Шкарин Д. Повышение эффективности алгоритма РРМ //Проблемы передачи информации. Т. 37, №3, 2001. С. 44-54.

68. Witten I.H, Neal R.M., Cleary J.G. Arithmetic coding for data compression. Com-mun. ACM, 30(6), 1987, p. 520-540.

69. Кнут Д. Искусство программирования. Том 3. СПб.: Вильяме, 2000. 832 с.

70. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2004. 960 с.

71. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. М.: ДИАЛОГ-МИФИ, 2002. 384 с.

72. Смирнов М.А. Использование методов безущербного сжатия данных в СУБД // Седьмая научная сессия аспирантов ГУ АЛ. Сборник докладов в 2 частях. 4.1. Технические науки. СПб, 2004. С. 370-373.

73. Осипов JI.A., Смирнов М.А. Использование экономного кодирования информации для повышения производительности хранилищ данных // IX Санкт-Петербургская международная конференция "Региональная информатика-2004 (РИ-2004)", СПб, 2004. С. 212.

74. Осипов JI.A., Смирнов М.А. Использование методов сжатия данных без потерь информации в условиях жестких ограничений на ресурсы устройства-декодера // Информационно-управляющие системы. 2004. №4. СПб. С. 7-15.

75. MySQL АВ (2004). MySQL Reference Manual for version 4.0.18.

76. Sybase, Inc. Sybase IQ Administration Guide, 1997.

77. Oracle Corp. Oracle Online Documentation Library. 2001.

78. Смирнов М.А. Оценка вероятности ухода в алгоритмах РРМ / Санкт-Петербургский государственный университет аэрокосмического приборостроения, СПб, 2000. 15 с. Деп. в ВИНИТИ 31.10.2000г„ № 2741-В00.

79. MacNicol R., French В. Sybase IQ Multiplex Designed For Analytics. Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004, p. 1227-1229.

80. Sybase, Inc. Adaptive Server IQ 12.5 Administration and Performance Guide. 2003.

81. Sybase, Inc. Sybase IQ. Accelerating Your Atfalytical Results. Part №L02348. 2003.

82. Teklitz F. Sybase Business Intelligence and Data Warehousing Solutions for Sybase IQ. Changing the Rules of the Game: Sybase IQ. Sybase White Paper. Part №L02369. 2003.