Организация доступа, хранения и извлечения знаний в темпоральных базах данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Нгуен Доан Куонг

• Нгуен Доан Куонг
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Нгуен Доан Куонг

ВВЕДЕНИЕ.

Сокращения и обозначения.

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

1.1. Организации доступа и хранения данных в темпоральных БД.

1.2. Обзор методов интеллектуальной обработки временных рядов.

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

1.3.1. Темпоральная надстройка над реляционной СУБД.

1.3.2. Интеллектуальная обработка временных рядов.

Выводы.

ГЛАВА 2 РЕАЛИЗАЦИЯ ТЕМПОРАЛЬНОЙ БАЗЫ ДАННЫХ НА ОСНОВЕ РЕЛЯЦИОННОЙ СУБД.

2.1. Темпоральные модели данных.

2.2. Трансляция SQL/Temporal в SQL-92.

2.3. Темпоральная алгебра.

2.3.1. Темпоральная выборка.

2.3.2. Темпоральная проекция.

2.3.3. Темпоральное объединение.

2.3.4. Темпоральное пересечение.

2.3.5. Темпоральная разность.

2.3.6. Темпоральное произведение.

2.3.7. Темпоральная агрегация.

2.3.8. Склейка.

2.4. Темпоральные ограничения целостности.

2.5. Операции модификации.

Выводы.

ГЛАВА 3 ИССЛЕДОВАНИЕ МЕТОДОВ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ВРЕМЕННЫХ РЯДОВ, ХРАНЯЩИХСЯ В ТЕМПОРАЛЬНЫХ СУБД.

3.1. Обзор методов извлечения знаний.

3.2. Предварительная обработка временных рядов.

3.2.1. Фильтрация данных временных рядов.

3.2.2. Индикатор обобщенного тренда.

3.3. ПРОГНОЗИРОВАНИЕ ПОВЕДЕНИЯ ВРЕМЕННЫХ РЯДОВ.

3.3.1. Формирование гистограмм распределения.

3.3.2. Предсказание поведения временных рядов.

Выводы.

Введение диссертации (часть автореферата) на тему «Организация доступа, хранения и извлечения знаний в темпоральных базах данных»

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

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

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

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

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

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

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

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

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

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

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

• рассматриваемые временные ряды являются нелинейными и нестационарными;

• вид нелинейности временного ряда априорно не известен и не описан аналитически;

• в результате решения задачи требуется нахождение краткосрочного прогноза.

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

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

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

3. Разработка схемы трансляции темпоральных запросов в запросы к современной реляционной промышленной СУБД.

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

5. Разработка методики прогнозирования поведения временного ряда на основе структурированной статистической информации.

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

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

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

Методы исследования: Исследования проводились с использованием теории реляционной алгебры, теории вероятности и методов теории искусственного интеллекта, применяемых в направлении "обнаружение знаний в темпоральных базах данных".

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

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

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

• предложен набор операций темпоральной алгебры для эффективного манипулирования временными рядами;

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

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

• предложена методика краткосрочного прогнозирования поведения временных рядов;

• разработан способ классификации состояния «хаотической» системы по ее временному ряду.

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

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

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

• эффективность предложенной методики краткосрочного прогнозирования поведения временных рядов продемонстрирована на примере временных рядов мирового валютного рынка FOREX.

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

• Архитектура темпоральной СУБД и набор операций темпоральной алгебры.

• Схема трансляции темпоральных запросов в запросы к реляционной СУБД.

• Метод структуризации и накопления статистической информации о поведении временных рядов.

• Методика краткосрочного прогнозирования поведения временных рядов.

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

Результаты работы в части прогнозирования временных рядов использования в учебном процессе на кафедре математического обеспечения и применения ЭВМ СПбГЭТУ "ЛЭТИ" при проведении занятий по курсу "теория вероятности и математическая статистика".

Апробация работы: Результаты работы докладывались на международной конференции по мягким вычислениям и измерениям в 2005 г. на конференциях ППС СПбГЭТУ "ЛЭТИ" в 2004-2006 гг.

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

Структура и объем диссертации: Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, включающего 138 наименований, и трех приложений. Основная часть работы изложена на 100 страницах машинописного текста. Работа содержит 63 рисунков и 3 таблицы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Нгуен Доан Куонг

Выводы

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

2) Предложены новые средства технического анализа временных рядов: индикатор обобщенного тренда и тренд ИОТ.

3) Введено понятие канонического состояния, которое используется для классификации состояний «хаотических» систем.

4) Предложен способ хранения статистической информации о поведении временного ряда, опирающийся на понятие канонического состояния «хаотической» системы.

5) Разработан алгоритм накопления статистической информации о поведении временного ряда.

6) Разработан алгоритм интерпретации статистических данных для произвольного состояния «хаотической» системы.

7) Проведен анализ статистической информации, когда в качестве «хаотической» системы использовались результаты торгов по валютной паре «евро - доллар США» на рынке FOREX.

8) Результаты анализа показали справедливость основных положений предложенного метода анализа временных рядов и возможность использования статистической информации для краткосрочного прогноза поведения «хаотической» системы.

ЗАКЛЮЧЕНИЕ

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

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

1) Предложены принципы реализации темпоральной СУБД в виде надстройки над существующей реляционной СУБД.

2) Предложен набор операций темпоральной алгебры, реализация которого в надстройке над реляционной СУБД делает ее темпоральной СУБД.

3) Для трансляции запросов на SQL/Temporal в запросы на SQL-92 предложена двухэтапная схема: трансляция с SQL/Temporal во внутреннее представление операций темпоральной алгебры и последующее преобразование этого представления в конструкции на SQL-92.

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

5) Предложена методика прогнозирования поведения временного ряда на основе структурированной статистической информации.

6) Предложен индикатор обобщенного тренда (НОТ) и индикатор тренда ИОТ. Эта пара позволяет классифицировать состояние хаотической системы по временному ряду, отражающему ее функционирование.

101

Список литературы диссертационного исследования кандидат технических наук Нгуен Доан Куонг, 2006 год

1. Dreyer W., Kotz Dittrich A., Schmidt D., Research Perspectives for Time Series Management Systems // Data Mining and Knowledge Discovery. 1994. Vol. 23, № l.P. 10-15.

2. Han J., Gong W., Yin Y., Mining Segment-Wise Periodic Patterns in Time-Related Databases // Proc. 1998 Int. Conf. On Knowledge Discovery and Data Mining (KDD'98), New York City, NY, Aug. 1998. P. 214-218.

3. Han J., Dong G., Yin Y., Efficient Mining of Partial Periodic Patterns in Time Series Database // Proc. 1999 Int. Conf. on Data Engineering (ICDE'99), Sydney, Australia, March 1999.

4. Srikant R., Agrawal R., Mining Quantitative Association Rules in Large Relational Tables // Proc. ACM-SIGMOD 1996 Conference on Management of Data, Montreal, Canada, 1996.

5. Manilla H., Toivonen H., Verkamo A.I., Discovery of Frequent Episodes in Event Sequences // Data Mining and Knowledge Discovery. 1997. Vol. 1, № 3. P. 259-289.

6. Tsai C., Wu S., A study for Second Order Modeling of Fuzzy Time Series // Proc. of 1999 IEEE International Fuzzy System Conference, Aug., 1999. P. 719-725.

7. Fayyad U. M., Piatetsky-Shapiro G., Smyth P. and Uthurusamy R. (editors). 1996. Advances in Knowledge Discovery and Data Mining. MIT Press.

8. Keogh E. J., Chakrabarti K., Pazzani M. J. and Mehrotra S. Dimensionality reduction for fast similarity search in large time series databases // Knowledge and Information Systems Journal. 2000. Vol. 3, № 3. P. 263-286.

9. Joentgen A., Mikenina L., Weber R. and Zimmermann H.-J. Dynamic fuzzy data analysis based on similarity between functions. // Fuzzy Sets and Systems. 1999. №105. P. 81-90.

10. Faloutsos С., Ranganathan M. and Manolopoulos Y. Fast subsequence matching in time-series databases. // In Proc. of ACM SIGMOD Int. Conf. on Data Management. 1994. P. 419-429.

11. Chung F.-l., Fu T.-C., Luk R. W. P. and Ng, V. Flexible time series pattern matching based on perceptually important points // In IJCAI-01 Workshop on Learning from Temporal and Spatial Data. 2001. Seattle, USA. P. 1-7.

12. Chatfield C. The Analysis of Time Series An Introduction. 1989. Chapman and Hall, 4th edition.

13. Quinlan J. R. Induction of decision trees. // Machine Learning. 1986. Vol. 1. P. 81-106.

14. Quinlan J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers. 1993.

15. Clark P. and Niblett T. The CN2 inductionalgorithm. // Machine Learning. 1989. Vol. 3. P. 262-283.

16. Kadous M. W. Learning comprehensible descriptions of multivariate time series. // Proc. of the 16th Int. Conf. on Machine Learning. 1999. P. 454-463.

17. Karimi K. and Hamilton H. J. Finding temporal relations: Causal bayesian networks vs. C4.5. // Proc. of the 12th Int. Symp. on Methodologies for Intelligent Systems. 2000. Charlotte, NC, USA. P. 266-273.

18. Savnik I., Lausen G., Kahle H.-P., Spiecker H. and Hein S. Algorithm for matching sets of time series. // In Int. Conf. on Principles of Data Mining and Knowledge Discovery. 2000. P. 277-288.

19. Martinelli M. Pattern recognition in time-series. Technical Analysis in Stocks & Commodities. 1998.

20. Sankoff D. and Kruskal J. B. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison Wesley. 1983.

21. Agrawal R., Faloutsos C. and Swami A. Efficient similarity search in sequence databases. // In Proc. of the 4th Int. Conf. on Foundations of Data Organizations and Algorithms. 1993. Chicago. P. 69-84.

22. Agrawal R., Lin K.-L., Sawhney H. S. and Shim, K. Fast similarity search in the presence of noise, scaling, and translation in time series databases. // In Proc. of the 21st Int. Conf. on Very Large Databases. 1995. Zurich, Switzerland.

23. Keogh E. J. and Pazzani M. J. An indexing scheme for fast similarity search in large time series databases. // In Proc. of the 11th Int. Conf. on Scientific and Statistical Database Management. 1999. Cleveland, Ohio.

24. Kim, E. D. Lam J. M. W. and Han, J. Aim: Approximate intelligent matching for time series data. // Proc. of the 2nd Int. Conf. on Data Warehousing and Knowl. Discovery. 2000. London, UK. Springer. LNCS, vol. 1874, P. 347-357.

25. Das G., Lin K.-I., Mannila H., Renganathan G. and Smyth P. Rule discovery from time series. // In Proc. of the 4th Int. Conf. on Knowl. Discovery and Data Mining. 1998. AAAI Press. P. 16-22.

26. Srikant R. and Agrawal R. Mining sequential patterns: Generalizations and performance improvements. // In Proc. of the 5th Int. Conf. on Extending Database Technology. 1996. Avignon, France. P. 3-17.

27. Mannila H. and Salmenkivi M. Finding simple intensity descriptions from event sequence data. In Proc. of the 7th Int. Conf. on Knowl. Discovery and Data Mining. 2001. San Francisco, USA. P. 341-346.

28. Li Y., Wang X. S., and Jajodia S. Discovering temporal patterns in multiple granularities. // In the 1st Int. Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining. 2000. Lyon, France. Springer. LNAI, vol. 2007. P. 5-19.

29. Rainsford C. P. and Roddick J. F. Adding temporal semantics to association rules. In Proc. of 10th Europ. Conf. on Machine Learning. 1999. Springer. LNAI, vol. 1704. P. 504-509.

30. Cohen P. R. Fluent learning: Elucidating the structure of episodes. // In Proc. of the 4th Int. Symp. on Intelligent Data Analysis. 2001. Springer. LNAI, vol. 2189. P. 268-277.

31. Guimaraes G. and Ultsch A. A method for temporal knowledge conversion. In Proc. of the 3rd Int. Symp. on Intelligent Data Analysis. 1999. Amsterdam, The Netherlands. Springer, Berlin. P. 369-380.

32. Kam P.-S. and Fu A. W.-C. Discovering temporal patterns for interval-based events. In Proc. of the 2nd Int. Conf. on Data Warehousing and Knowl. Discovery. 2000. Springer. LNCS vol. 1874. P. 317-326.

33. Villafane R., Hua K. A., Tran D. and Maulik B. Mining interval time series. // In Proc. of the 1st Int. Conf. on Data Warehousing and Knowl. Discovery. 1999. Springer. P. 318-330.

34. Villafane R., Hua K. A., Tran D. and Maulik B. Knowledge discovery from series of interval events. Journal of Intelligent Information Systems. 2000. Vol. 15, №1. P. 71-89.

35. Shatkay H. Approximate queries and representations for large data sequences. Technical Report 3, Dep. of Computer Science, BrownUniversity. 1995.

36. Keogh E. J. and Pazzani M. J. 1999. Scaling up dynamic time warping to massive datasets. // In Proc. of the 3rd Europ. Conf. on Principles of Data Mining and Knowl. Discovery. 1999. Prague, Czech Republic. Springer. LNAI, vol. 1704. P. 1-11.

37. Keogh E. J. A fast and robust method for pattern matching in time series databases. // In Proceedings of 9th Int. Conf. on Tools with AI (TAI 97). 1997.

38. Bakshi В. R. and Stephanopoulos G. Reasoning in time: Modelling, analysis, and pattern recognition of temporal process trends. In Advances in Chemical Engineering, 1995, vol. 22, P. 485-548.

39. Mcllraith S. A. Qualitative data modeling: application of a mechanism for interpreting graphical data. Computational Intelligence (Theory and Practice), 1989, vol. 5. P. 111-120.

40. Capelo A. C., Ironi L. and Tentoni S. Automated mathematical modelling from experimental data: An application to material science. IEEE Trans, on Systems, Man, and Cybernetics, 1998, Part C, vol. 28, №3. P. 356-370.

41. Hoppner F. Learning dependencies in multivariate time series. // In Proc. of the ECAI'02 Workshop on Knowledge Discovery from (Spatio-) Temporal Data. 2002. Lyon, France. P. 25-31.

42. Hoppner F. Time series abstraction methods a survey. // In Proceedings GI Jahrestagung Informatik, Workshop on Knowl. Discovery in Databases. 2002. Dortmund, Germany. Lecture Notes in Informatics. P. 777-786.

43. Hoppner F. Learning temporal rules from state sequences. // In Proc. of the IJCAI'01 Workshop on Learning from Temporal and Spatial Data. 2001. Seattle, USA. P. 25-31.

44. Hoppner F. and Klawonn F. Learning rules about the development of variables over time. // In Leondes, С. Т., editor, Intelligent Systems: Technology and Applications. 2002. CRC Press. Vol. IV, chapter 9, p. 201-228.

45. Shao, J. Application of an artificial neural network to improve short-term road ice forecasts. Expert Systems With Applications. 1998, vol. 14. P. 471-482.

46. Carrault G., Cordier M.-O. Quiniou, R. and Wang, F. Intelligent multichannel cardiac data analysis for diagnosis and monitoring. // In Proc. of the ECAI'02 Workshop on Knowledge Discovery from (Spatio-) Temporal Data. 2002. Lyon, France. P. 10-16.

47. Hoppner F. and Klawonn F. Finding informative rules in interval sequences. Intelligent Data Analysis. 2002, vol. 6, № 3. P. 237-256.

48. Hoppner F. Handling feature ambiguity in knowledge discovery from time series. // In Proc. of 5th Int. Conf. on Discovery Science. 2002. Lubeck, Germany. Springer. LNCS, vol. 2534. P. 398-405.

49. Focardi S.M. Clustering economic and financial time series: Exploring the existence of stable correlation conditions. Technical report. 2001. Paris. P. 1-15.

50. Laloux L., Cizeau P., Bouchaud J.P. and Potters M. Noise Dressing of Financial Correlation Matrices. Phys. Rev. Lett. 1999, vol. 83, № 1467.

51. Ormerod P. and Mounfield C., Localised Structures in the Temporal Evolution of Asset Prices. // In Proc. Conf. New Approaches to Financial Economics. October 2000. Santa Fe.

52. Plerou V., Gopikrishnan P., Rosenow В., Amaral L.A.N, and Stanley H.E. Universal and Non-Universal Properties of Cross-correlations in Financial Time Series. Phys. Rev. Lett. 1999, vol. 83, № 1471.

53. Bonanno G., Vandewalle N. and Mantegna R. N. Taxonomy of Stock Market Indices, Physical Review E62, R7615-R7618, 2000.

54. Park S. and Chu W.W. Discovering and Matching Elastic Rules from Sequence Databases. Fundamenta Informaticae XX. 2001. IOS Press. P. 1-16.

55. Chu W. W., Chiang K. Abstraction of High Level Concepts from Numerical Values in Databases. // In Proc. AAAI Workshop on Knowledge Discovery in Databases, 1994.

56. Chu W. W., Cardenas A. F., Taira R. K. KMeD: a Knowledge-based Multimedia Medical Distributed Database System, Information Systems. 1995, vol. 20, № 2, P. 75-96.

57. McCreight E. M. A Space-Economical Suffix Tree Construction Algorithm. Journal of ACM. 1998, vol. 23, № 2. P. 262-272.

58. Bieganski P., Riedl J., Carlis J. V. Generalized Suffix Trees for Biological Sequence Data: Applications and Implementation. // In Proc. Hawaii International Conference on System Sciences, 1994.

59. Gavrilov M., Anguelov D., Indyk P., Motwani R. Mining The Stock Market: Which Measure Is Best? Technical Report. 2000. Department of Computer Science, Stanford University. P. 1-10.

60. Giedrius Slivinskas, Christian S. Jensen, and Richard T. Snodgrass. A foundation for conventional and temporal query optimization addressing duplicates and ordering. Knowledge and Data Engineering, 13(1 ):21-49, 2001.

61. Agrawal R. and Srikant R. Mining Sequential Patterns. // In Proc. Int. Conf. on Data Engineering (ICDE), Taipei, Taiwan, 3-14, March 1995.

62. Bettini C., Wang X.S., Jajodia S. and Lin J.-L. Discovering frequent event patterns with multiple granularities in time sequences. IEEE Transaction on Knowledge and Data Engineering. 1998, vol. 10, № 2. P. 222-237.

63. Zaki M. Sequence mining in categorical domains: incorporating constraints. // In Proc. 9th Int. Conf. on Information and Knowledge Management. 2000. P. 422-429.

64. Han J., Dong G. and Yin Y. Efficient mining partial periodic patterns in time series database. // In Proc. Int. Conf. on Data Engineering. 1999. P. 106-115.

65. Ozden В., Ramaswamy S. and Silberschatz A. Cyclic association rules. // In Proc. 14th Int. Conf. on Data Engineering. 1998. P. 412-421.

66. Yang J., Wang W. and Yu P. Mining asynchronous periodic patterns in time series data. // In Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD). 2000. P. 275-279.

67. Garofalakis M., Rastogi R. and Shim K. SPIRIT: sequential pattern mining with regular expression constraints. // In Proc. Int. Conf. on Very Large Data Bases (VLDB). 1999. P. 223-234.

68. Padmanabhan B. and Tuzhilin A. Pattern discovery in temporal databases: a temporal logic approach. // In Proc. ACMKDD. 1996. P. 351-354.

69. Yang J., Wang W. and Yu P. InfoMiner: mining surprising periodic patterns. // In Proc. ACM Knowledge Discovery and Data Mining. 2001.P. 395-400.

70. Klemetinen M., Mannila H., Ronkainen P., Toivonen H. and Verkamo A. Finding interesting rules from large sets of discovered association rules. // In Proc. CIKM, 1994.

71. Sahar S. Interestingness via what is not interesting. Proc. 5th ACM Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD). 1999. P. 332-336.

72. Spiliopoulou M. Managing interesting rules in sequence mining. // In Proc. European Conf. on Principles and Practice of Knowledge Discovery in Databases. 1999. P. 554-560.

73. Liu В., Hsu W. and Ma Y. Mining association Rules with multiple minimum supports. // In Proc. ACM SIGKDD. 1999. P. 337-341.

74. Liu В., Ни M. and Hsu W. Multi-level organization and summarization of the discovered rules. // In Proc. ACM SIGKDD. 2000. P. 208-217.

75. Wang K., He Y. and Han J. Mining frequent itemsets using support constraints. // In Proc. 26th Intl. Conf. on Very Large Data Bases (VLDB), 2000.

76. Debregeas A. and Hebrail G. Interactive interpretation of Kohonen maps applied to curves. // In Proceedings of the 4«, International Conference of Knowledge Discovery and Data Mining. 1998. P. 179-183.

77. Keogh E. and Pazzani M. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. // In

78. Proceedings of the 4«. International Conference of Knowledge Discovery and Data Mining. 1998. AAAI Press. P. 239-241.

79. Loh W., Kim S. and Whang K. Index interpolation: an approach to subsequence matching supporting normalization transform in time-series databases. // In Proceedings 9a International Conference on Information and Knowledge Management. 2000.

80. Chu K., and Wong M. Fast time-series searching with scaling and shifting. // In Proceedings of the 18a, ACM Symposium on Principles of Database Systems.1999. Philadelphia.

81. Refiei D. On similarity-based queries for time series data. // In Proc of the 15.h IEEE International Conference on Data Engineering. 1999. Sydney, Australia.

82. Korn, ., Jagadish H. and Faloutsos C. Efficiently supporting ad hoc queries in large datasets of time sequences. // In Proceedings of SIGMOD. 1997. Tucson, AZ. P. 289-300.

83. Keogh E., Chakrabarti K., Pazzani M. and Mehrotra Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems. 2001. Vol. 3, № 3, August.

84. Chan K. and Fu W. Efficient time series matching by wavelets. Proceedings of the 15a, IEEE International Conference on Data Engineering. 1999. P. 126-133.

85. Wu Y., Agrawal D. and Abbadi A. A Comparison of DFT and DWT based Similarity Search in Time-Series Databases. Proceedings of the % International Conference on Information and Knowledge Management. 2000.

86. Yi B.K. and Faloutsos C. Fast time sequence indexing for arbitrary Lp norms. Proceedings of the 26a, International Conference on Very Large Databases.2000. Cairo, Egypt. P. 385-394.

87. Wu D., Agrawal D., Abbadi E., Singh A. and Smith T. R. Efficient retrieval for browsing large image databases. Proc of the 5л International Conference on Knowledge Information. 1996. Rockville, MD. P. 11-18.

88. Keogh E,. Chu S. and Pazzani M. Ensemble-Index: A New Approach to Indexing Large Databases. // In Proc. SIGKDD, August 26-29, 2001, San Francisco, CA.

89. Minka T. and Picard R. Interactive learning using a "society of models". // In Proceedings IEEE Conference.on Computer Vision and Pattern. Recognition. 1996.

90. Belkin N., Cool C., Croft B. and Callan J. The effect of multiple query representations on information retrieval system performance. In Proceedings of the 16л ACM SIGIR Conference on Research and Development in Information Retrieval. 1993. P. 339—346.

91. Zhu Y. and Shasha D. StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time. // In Proc. VLDB International Conference. Hong Kong, China, August 2002. P. 358-369.

92. Steere D., Baptista A., McNamee D, Pu C. and Walpole J. Research Challenges in Environmental Observation and Forecasting Systems. // In Proc. Mobile Computing and Networking. Boston, MA, USA, August 2000.

93. Koski A., Juhola M. and Meriste M. Syntactic Recognition of ECG Signals By Attributed Finite Automata. Pattern Recognition, 1995, Vol. 28, № 12. P. 19271940.

94. Hussain A., Heidemann J. and Papadopoulos C. A Framework for Classifying Denial of Service Attacks. // In Proc. ACM SIGCOMM Conference. Karlsruhe, Germany, August 2003.

95. Ganesan D., Greenstein В., Perelyubskiy D., Estrin D. and Heidemann J. An Evaluation of Multi-Resolution Search and Storage in Resource-Constrained Sensor Networks. Technical Report CENS 0010, April 2003.

96. Keogh E.J. and Kasetty S. On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration. // In Proc. International Conference on Knowledge Discovery and Data Mining. ,Edmonton, Canada, July 2002. P. 102-111.

97. Chakrabarti К., Keogh E.J., Mehrotra S. and Pazzani M.J. Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases. ACM Transactions on Database Systems. 2002. Vol. 27, №2. P. 188-228.

98. Andre-Jonsson H. and Badal D. Using Signature Files for Querying Time-Series Data. // In Principles of Data Mining and Knowledge Discovery. Trondheim, Norway, June 1997. P. 211-220.

99. Rafiei D. On Similarity-Based Queries for Time Series Data. // In Proc. International Conference on Data Engineering. March 1999. Sydney, Australia.

100. Popivanov I. and Miller R.J. Similarity Search Over Time Series Data Using Wavelets. // In Proc. International Conference on Data Engineering. San Jose, CA, USA, February 2002. P. 802-813.

101. Lazaridis I. and Mehrotra S. Capturing Sensor-Generated Time Series with Quality Guarantees. // In Proc. International Conference on Data Engineering. Bangalore, India, March 2003. P. 429^40.

102. Gilbert A.C., Kotidis Y., Muthukrishnan S. and Strauss M. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. // In Proc. VLDB International Conference. Rome, Italy, sep. 2001. P. 79-88.

103. Guha S. and Koudas N. Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation. In Proc. International Conference on Data Engineering. San Jose, CA, USA, March 2002. P. 567-576.

104. Cohen E. and Strauss M. Maintaining Time-Decaying Stream Aggregates. In Proc. ACM PODS International Conference. San Diego, CA, USA, jun 2003. P. 223-233.

105. Satrom P. and Hetland M.L. Mining interesting temporal rules with genetic programming and specialized hardware. In Proceedings of The 2003 International Conference on Machine Learning and Applications (ICMLA'03). 2003.

106. Zitzler E., Laumanns M. and Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH). Zurich, Switzerland, May 2001.

107. Carlos А. С. A short tutorial on evolutionary multiobjective optimization. // In Proc. First International Conference on Evolutionary Multi-Criterion Optimization. 2001. Springer-Verlag. Lecture Notes in Computer Science, vol. 1993.

108. Michael H. Bohlen. Temporal database system implementations. SIGMOD Rec., 24(4):53-60, 1995.

109. Babcock В., Babu S., Datar M., Motwani R. and Widom J. Models and Issues in Data Stream Systems. // In Proc. of the 2002 ACM Symp. On Principles of Database Systems. 2002, June 3-5, Madison, WI.

110. Cortes C., Fisher K., Pregibon D., Rogers A. and Smith F. Hancock: a Language for Extracting Signatures from Data Streams. // In Proc. of the 6,„ ACM SIGKDD Int'l Conference on Knowledge Discovery and Data Mining. 2000, Aug 2023, Boston, MA. P. 9-17.

111. Datar M. and Muthukrishnan S. Estimating Rarity and Similarity over Data Stream Windows. // In Proc. of the 10-European Symposium on Algorithms. 2002. Sep 17-21, Rome, Italy.

112. Guha S., Mishra N., Motwani R. and O'Callaghan L. Clustering Data Streams. // In Proc. of the 41«Symposium on Foundations of Computer Science. 2000. Nov 12-14, Redondo Beach, CA. P. 359-366.

113. Dasgupta D. and Forrest S. Novelty Detection in Time Series Data using Ideas from Immunology. // In Proc. of The International Conference on Intelligent Systems. 1996, June 19-21.

114. Huang Y. and Yu P. S. Adaptive Query Processing for Time-Series Data. // In Proc. of the 5,ь Int'l Conference on Knowledge Discovery and Data Mining. 1999. San Diego, CA, Aug 15-18. P. 282-286.

115. Kalpakis K., Gada D. and Puttagunta V. Distance Measures for Effective Clustering of ARIMA Time-Series. // In Proc. of the 2001 IEEE International Conference on Data Mining. 2001. San Jose, CA, Nov 29-Dec 2. P. 273-280.

116. Lin J., Keogh E., Lonardi S. and Patel P. Finding Motifs in Time Series. // In Proc. of the Workshop on Temporal Data Mining, at the 8, ACM SIGKDD Int'l

117. Conference on Knowledge Discovery and Data Mining. 2002. Edmonton, Alberta, Canada, July 23-26. pp. 53-68.

118. Apostolico A., Bock M. E. and Lonardi S. Monotony of Surprise and Large-Scale Quest for Unusual Words. // In Proc. of the 6.h Int'l Conference on Research in Computational Molecular Biology. 2002. Washington, DC, April 18-21. P. 22-31.

119. Gionis A. and Mannila H. Finding Recurrent Sources in Sequences. // In proceedings of the 7* International Conference on Research in Computational Molecular Biology. 2003. Apr 10-13, Berlin, Germany.

120. Reinert G., Schbath S. and Waterman M. S. Probabilistic and Statistical Properties of Words: An Overview. Journal of Computational. Biology. 2000. Vol. 7, P. 1-46.

121. Tompa M. and Buhler J. Finding Motifs Using Random Projections. // In Proc. of the 5.h Int'l Conference on Computational Molecular Biology. 2001. Montreal, Canada, Apr 22-25. P. 67-74.

122. Theodoulidis C.I. and Loucopoulos P. The time dimension in conceptual modelling. Information Systems, 16(3):273-300, 1991.

123. Jensen C.S, Snodgrass R.T., Bohlen M.H. and Steiner A. Adding valid time to sql/temporal. ISO/IEC JTC1/SC21 WG3 DBL MAD-146r2, X3H2-96-501r2, nov. 1996.

124. Jensen C.S. Temporal Database Management. PhD thesis, Aalborg University, April 2000.

125. Snodgrass R.T., Bohlen M.H., Jensen C.S. and Steiner A. Transitioning temporal support in TSQL2 to SQL3. // Lecture Notes in Computer Science, 1399:150-173, 1998.

126. Torp K., Jensen C.S. and Snodgrass R.T. Stratum approaches to temporal DBMS implementation. // In Proc. International Database Engineering and Application Symposium, pages 4-13, 1998.

127. Torp К., Jensen C.S. and Bohlen M.H. Layered temporal DBMS: Concepts and techniques. //In Database Systems for Advanced Applications, pp. 371380, 1997.

128. Slivinskas G., Jensen C.S. and Snodgrass R.T. A foundation for conventional and temporal query optimization addressing duplicates and ordering. // Knowledge and Data Engineering, 13(l):21-49, 2001.

129. Soo M.D., Snodgrass R.T. and Jensen C.S. Efficient evaluation of the valid-time natural join. // In Proc. of the 10th International Conference on Data Engineering (ICDE), pages 282-292, 1994.

130. К. Дж. Дейт. Введение в системы баз данных, 7-е издание. Вильяме,2002.

131. Bohlen М.Н., Busatto R., and Jensen C.S. Point- versus intervalbased temporal data models. Technical Report, 21, 1998.

132. Брюс Эккель. Философия Java, 3-е издание. Питер, 2003.