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

• Смирнов, Максим Анатольевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Смирнов, Максим Анатольевич

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

Введение.

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 скорость обработки запросов к сжатым данным неизменно ниже скорости запросов к несжатым данным.

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

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

Список литературы диссертационного исследования кандидат технических наук Смирнов, Максим Анатольевич, 2005 год

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.