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

• Гудков, Андрей Сергеевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Гудков, Андрей Сергеевич

Введение.

Глава 1 Направления решения задачи анализа данных.

1.1. Классификация аналитических систем.

1.2. Реализации интерактивного анализа данных (OLAP).

1.3. Алгоритмы агрегирования куба.

1.4. Алгоритмы поиска частых наборов и ассоциативных правил.

1.5. Эффективный просмотр ассоциативных правил.

1.6. План работы и полученные результаты.

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

2.1. Формальная постановка задач.

2.2. Структура данных - префиксное дерево.

2.3. Алгоритм выполнения запросов OLAP.л.

2.4. Алгоритм агрегирования куба с помощью перестроек префиксного дерева

2.5. Алгоритм поиска частых наборов с помощью перестроек префиксного дерева.

Глава 3 Организация просмотра ассоциативных правил.

3.1. Меры правил.

3.2. Алгоритмы поиска интересных ассоциативных правил.

3.3. Внешний вид отчёта о просматриваемых правилах.

3.4. Алгоритм интерактивного просмотра правил в виде сводной таблицы.

Глава 4 Теоретический анализ алгоритмов.

4.1. Задача о среднем числе разных элементов.

4.2. Сложность задач.

4.3. Объём префиксного дерева.

4.4. Время построения префиксного дерева.

4.5. Время подъёма уровня префиксного дерева.

4.6. Время работы алгоритма интерактивного анализа данных.

4.7. Время работы алгоритма агрегирования куба.

4.8. Время работы алгоритмов поиска частых наборов.

Глава 5 Экспериментальный анализ алгоритмов.

5.1. Алгоритмы интерактивного анализа данных.

5.2. Алгоритмы агрегирования куба.

5.3. Алгоритмы поиска частых наборов.

5.4. Меры интереса правил.

Введение диссертации (часть автореферата) на тему «Использование префиксных деревьев при построении систем анализа данных»

Актуальность темы.

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

В литературе активно исследуются три основных технологии систем анализа данных: хранилища данных, оперативная аналитическая обработка данных (Online Analytical Processing, или сокращённо OLAP), интеллектуальный анализ данных (Data Mining).

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

Если объёмы данных очень велики, то предагрегация может значительно ускорить выполнение запросов. Также агрегирование может применяться для ответа на запросы пользователя с одновременным требованием просмотра многих агрегатных данных (например, при отображении сводной таблицы). Первые алгоритмы агрегирования куба основываются на существенном использовании диска и являются достаточно медленными. Алгоритмы MemoryCube и BUC компактно используют оперативную память для проведения вычислений, но их планы выполнения являются неоптимальными. Предложенный в диссертации алгоритм перестроек префиксного дерева предлагает более быстрое выполнение по сравнению с заявленными алгоритмами при тех же объёмах обрабатываемых данных.

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

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

Цели работы.

Основными целями диссертационной работы являются:

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

2. Разработка алгоритмов удобного просмотра извлечённых правил.

3. Анализ разработанных алгоритмов.

Методы исследования.

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

Научная новизна полученных результатов.

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

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

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

Разработанный алгоритм интерактивного анализа данных внедрён в автоматизированной информационной системе "Консул ЗУ" в МИД РФ.

Апробация работы.

Основные результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих конференциях:

• XLVIII и XLIX научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2005,2006)

• XIII международной научной конференции студентов, аспирантов и молодых учёных "Ломоносов", (Москва, МГУ, 2006), а также на научных семинарах кафедры управляющих и информационных систем МФТИ и 3500 отделения ГосНИИ авиационных систем в 2002-2006 гг.

Публикации.

Основные положения работы отражены в публикациях [1-6].

Краткое содержание работы.

В главе 1 проводится обзор основных направлений решения задачи анализа данных. Рассмотрено положение систем анализа данных среди информационных систем и их классификация по способу хранения данных, способу анализа данных и степени участия человека в анализе данных. Поставлены основные задачи диссертации: реализация ответов на запросы интерактивного анализа данных (OLAP), агрегирование куба, поиск частых наборов и ассоциативных правил, эффективный просмотр ассоциативных правил. Для каждой задачи проведён обзор существующих подходов к решению.

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

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

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

В главе 5 проводится экспериментальный анализ разработанных алгоритмов для выполнения запросов интерактивного анализа данных, агрегирования куба и поиска частых наборов. При выполнении запросов интерактивного анализа данных производится сравнение с алгоритмом, основанным на хранении в виде таблицы и ответов на запросы с помощью сортировок. Сравнение производится по времени заполнения, объёму занимаемой памяти и скорости ответов на запросы. При агрегировании куба производится сравнение с алгоритмом MemoryCube. При поиске частых наборов производится сравнение четырёх предложенных алгоритмов с алгоритмами Apriori и FP-Growth.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гудков, Андрей Сергеевич

Заключение

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

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

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

3. Введено несколько мер ценности ассоциативных правил, учитывающих их специфику, и разработан алгоритм поиска интересных ассоциативных правил с учётом этих мер.

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

5. Разработан комплекс программ для предложенных и ряда известных алгоритмов. Проведено экспериментальное сравнение их эффективности.

Список литературы диссертационного исследования кандидат физико-математических наук Гудков, Андрей Сергеевич, 2006 год

1. Бондаренко А.В., Галактионов В.А., Горемычкин В.И., Гудков А.С., Стриковский И.И. Реализация интерактивного анализа данных с помощью префиксного дерева: Препринт / ИПМ. М., 2005. - №61. -34 с.

2. Бондаренко А.В., Гудков А.С. Интерактивный анализ ассоциативных правил в базе данных. // Вестник компьютерных и информационных технологий. 2006. - №10. - С.42-45.

3. Бондаренко А.В., Гудков А.С. Поиск частых и разных комбинаций с помощью перестроек префиксного дерева. // Процессы и методы обработки информации: Сб.ст. / МФТИ. М., 2006. - С.69-78.

4. Гудков А.С. Агрегирование куба с помощью префиксного дерева. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции. / МФТИ. М., 2005. - С.92-93.

5. Гудков А.С. Меры интереса ассоциативных правил, основанные на предсказании точности. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. / МФТИ. М., 2006. - С.84-85.

6. Гудков А.С. Поиск частых комбинаций в базах данных. // Материалы XIII Международной конференции студентов, аспирантов и молодых учёных "Ломоносов", секция "Вычислительная математика и кибернетика". М., 2006. - С. 19-20.

7. Альперович М. Введение в OLAP и многомерные базы данных. // PC Week/RE. 1999. - №28(202). - С.24. WEB: http://www.olap.ru/basic/alpero2i.asp.

8. Арустамов А. Применение OLAP технологий при извлечении данных. WEB: http://www.basegroup.ru/olap/using.htm.

9. Бирюков А. Системы принятия решений и хранилища данных. // СУБД. 1997. - №4. - С.37-41.

10. Буров К. Обнаружение знаний в хранилищах данных. // Открытые системы. 1999. - №5-6. - С.67-77.

11. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс. Москва: Вильяме, 2003. - 1088 с.

12. Гро Э. Архитектуры отчётности. // Журнал клуба знатоков DWH, OLAP, XML. 2003. - №23. WEB: http://www.iso.ru/journal/articles/247.html.

13. Дюк В., Самойленко A. Data Mining: Учебный курс. СПб: Питер, 2001.-366 с.

14. Заратуйченко О. Современные подходы и методы построения аналитических информационных систем. // Тезисы выступления на семинаре НТЦ АРБ "Практические вопросы информационно-аналитической работы в коммерческом банке". Март 1998.

15. Заратуйченко О. Филиалы, данные, анализ. // Банковские технологии. 1998.-№1.-С.49-52.

16. Кузнецов С. Д. Проектирование и разработка корпоративных информационных систем. WEB: http://www.citforum.ru/cfin/prcorpsys/.

17. Кузнецов С.Д., Артемьев В. Обзор возможностей применения ведущих СУБД для построения хранилищ данных (Data Warehouse). // Тезисы доклада на 3-й ежегодной конференции "Корпоративные базы данных". Москва. - 1998. - С. 153-161.

18. Ларин С. Применение ассоциативных правил для стимулирования продаж. 2003. WEB: www.basegroup.ru/practice/salepromotion.htm.

19. Лисянский К. Архитектурные решения и моделирование данных для хранилищ и витрин данных. WEB: www.olap.ru.

20. Лобач Д. Основы OLAP. WEB: http://www.softkey.info/reviews/review.php?ID=465.

21. Львов В. Создание систем поддержки принятия решений на основе хранилищ данных. // СУБД. 1997. - №3. - С.30-40.

22. Некипелов Н., Шахиди А. Онтология анализа данных. WEB: http://www.basegroup.ru/tech/ontology.htm.

23. Педерсен Т.Б., Иенсен К. Технология многомерных баз данных. // Открытые системы. 2002. - №1. - С.45-50.

24. Сахаров А.А. Концепция построения и реализации информационных систем, ориентированных на анализ данных. // СУБД. 1996. - №4. -С.55-70.

25. Сахаров А.А. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server). // СУБД. 1996. - №3. - С.44-59.

26. Слотер Э. Архитектуры OLAP. WEB: www.oIap.ru.

27. Стариков А. Ядро OLAP системы. Часть 1 принципы построения. WEB: http://www.basegroup.ru/olap/corej3artl .htm.

28. Стариков А. Ядро OLAP системы. Часть 2 внутри гиперкуба. WEB: http://www.basegroup.ru/olap/corepart2.htm.

29. Стариков А. Ядро OLAP системы. Часть 3 построение срезов куба. WEB: http://www.basegroup.ru/olap/corepart3.htm.

30. Федоров А., Елманова Н. Введение в OLAP: часть 1. Основы OLAP. // Компьютер Пресс. 2001. - №4.

31. Федоров А., Елманова Н. Введение в OLAP: часть 2. Хранилища данных. // Компьютер Пресс. 2001. - №5.

32. Федоров А., Елманова Н. Введение в базы данных: средства Business Intelligence. // Компьютер Пресс. 2001. - №3.

33. Хрусталёв Е.М. Агрегация данных в OLAP-кубах. WEB: www.olap.ru.

34. Чаудхури С., Дайал У., Гаити В. Технология баз данных в системах поддержки принятия решений. // Открытые системы. 2002. - №1. -С.37-44.

35. Что такое Data Mining. / Intersoft Lab. // Журнал клуба знатоков DWH, OLAP, XML. 2003. - №26. WEB: http://www.iso.ru/journal/articles/275.html.

36. Шахиди A. Apriori масштабируемый алгоритм поиска ассоциативных правил. - 2002. WEB: www.basegroup.ru/rules/apriori.htm.

37. Щавелёв JT.B. Способы аналитической обработки данных для поддержки принятия решений. // СУБД. 1998. - №4-5.

38. Электронный учебник по статистике. / StatSoft, Inc. WEB: http://www.statsoft.ru/home/textbook/default.htm.

39. Agarwal S., Agrawal R., Deshpande P.M., Gupta A., Naughton J.F., Ramakrishnan R., Sarawagi S. On the computation of multidimensional aggregates. // Proceedings of 22nd VLDB Conf. 1996. - P.506-521.

40. Aggarwal C.C., Yu P.S. Mining Large Itemsets for Association Rules. // Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. 1997. - Vol.2, №1. - P.23-31.

41. Aggarwal C.C., Yu P.S. A new framework for itemset generation. // Proceedings of 17th Symposium on Principles of Database Systems. -Seattle, WA, USA. June 1998. - P. 18-24.

42. Agrawal R., Imielinski Т., Swami A. Database mining: a performance perspective. // IEEE transactions on knowledge and data engineering. -December 1993. Vol.5, №6. - P.914-925.

43. Agrawal R., Imielinski Т., Swami A. Mining Associations between Sets of Items in Massive Databases. // Proceedings of 1993 ACM-SIGMOD International Conference on Management of Data. Washington, DC, USA.-May 1993.-P.207-216.

44. Agrawal R., Srikant R. Fast Discovery of Association Rules. // Proceedings of 20th International Conference on VLDB. Santiago, Chile. - September 1994.-P.487-499.

45. Agrawal R., Gupta A., Sarawagi S. Modeling multidimensional databases. // Proceedings of International Conference on Data Engineering. -Birmingham, U.K. 1997. - P.232-243.

46. Bayardo R.J., Agrawal R., Gunopulos D. Constraint-based rule mining in large, dense databases. // Proceedings of 15th ICDE Conference. March 1999. - P.188-197.

47. Berson A., Smith S., Thearling K. Building Data Mining Applications for CRM. McGraw Hill Professional, 1999. - 510 p.

48. Beyer K., Ramakrishnan R. Bottom-up computation of sparse and iceberg CUBES. // Proceedings of SIGMOD. Philadelphia, PA, USA. - 1999. -P.359-370.

49. Borgelt C., Kruse R. Induction of association rules: Apriori implementation. // Proceedings of 15th Conference on Computational Statistics (Compstat 2002). Heidelberg, Germany. - 2002.

50. Borgelt C. Efficient implementations of apriori and eclat. // Proceedings of IEEE ICDM Workshop on Frequent Itemset Mining Implementations. -Melbourne, FL, USA. November 2003.

51. Brin S., Motwani R., Ullman J.D., Tsur S. Dynamic itemset counting and implication rules for market basket data. // Proceedings of ACM SIGMOD International Conference on Management of Data. Tucson, Arizona, USA. - May 1997. - P.255-264.

52. Codd E.F., Codd S.B., Salley C.T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate. E. F. Codd & Associates, 1993.-24 p.

53. Data mining добыча данных. / Лаборатория Basegroup. WEB: http://www.basegroup.ru/tasks/datamining.htm.

54. Deshpande P.M., Agarwal S., Naughton J.F., Ramakrishnan R. Computation of Multidimensional Aggregates: Technical Report-1314 / University of Wisconsin-Madison. 1996.

55. El-Hajj M., Zaiane O. Inverted Matrix: Efficient Discovery of Frequent Items in Large Datasets in the Context of Interactive Mining. // Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003. - P.109-118.

56. Fang M., Shivakumar N., Garcia-Molina H., Motwani R., Ullman J.D. Computing Iceberg Queries Efficiently. // Proceedings of International

57. Conference on Very Large Databases (VLDB'98). New York. - August 1998. -P.299-310.

58. Fayyad U., Piatetsky-Shapiro G., Smyth P. From Data Mining to Knowledge Discovery in Databases. // Al Magazine. 1996. - №17(3). -P.37-54.

59. Fayyad U., Piatetsky-Shapiro G., Smyth P. Knowledge Discovery and Data Mining: Towards a Unifying Framework. // Proceedings of KDD-96 Conference. 1996. - P.82-88.

60. Fu L., Hammer J. CubiST: A New Algorithm for Improving the Performance of Ad-hoc OLAP Queries. // Proceedings of ACM Third International Workshop on Data Warehousing and OLAP. Washington, DC. - November 2000. - P.72-79.

61. Fu L., Hammer J. CUBIST: A New Approach to Speeding Up OLAP Queries in Data Cubes: Technical Report TR01-007 / University of Florida, Gainesville, FL. May 2001. - 19 p. WEB: citeseer.ist.psu.edu/fuO 1 cubist.html, 2001.

62. Goethals B. Survey on frequent pattern mining: Manuscript. 2003. - 43 p.

63. Graefe G. Query evaluation techniques for large databases. // ACM Computing Surveys. June 1993. - Vol.25, №2. - P.73-170.

64. Gray J., Bosworth A., Layman A., Pirahesh H. Datacube: a relational aggregation operator, generalizing group-by, cross-tab, and sub-totals. // Proceedings of IEEE ICDE. 1996. - P. 152-159.

65. Gupta H., Harinarayan V., Rajaraman A., Ullman J. Index Selection for OLAP. // Proceedings of Intl. Conf. on Data Engineering. 1997. - P.208-219.

66. Gyssens M., Lakshmanan L.V.S. A foundation for multidimensional databases. // Proceedings of 23rd VLDB Conference. Athens, Greece. -1997. -P.106-115.

67. Hahsler M. A comparison of commonly used interest measures for association rules. WEB: http://wwwai.wu-wien.ac.at/~hahsler/research/association rules/measures.html.

68. Han J., Pei J., Dong J., Wang K. Efficient computation of iceberg cubes with complex measures. // Proceedings of SIGMOD. 2001. - P. 1-12.

69. Han J., Fu Y. Discovery of multiple-level association rules from large databases. // Proceedings of 21st Int'l Conference on Very Large Databases. Zurich, Switzerland. - September 1995. - P.420-431.

70. Han J., Pei J., Yin Y. Mining frequent patterns without candidate generation. // Proceedings of ACM SIGMOD International Conference on Management of Data. Dallas, USA. - 2000. - P. 1-12.

71. Harinarayan V., Rajaraman A., Ullman J.D. Implementing data cubes efficiently. // Proceedings of ACM SIGMOD conference on management of data. 1996.-P.205-216.

72. Hipp J., Guntzer U., Nakaeizadeh G. Algorithms for Association Rule Mining A General Survey and Comparison. // SIGKDD Explorations. -July 2000. - Vol.2, №1. - P.58-64.

73. Ho C-T., Bruck J., Agrawal R. Partial-sum queries in OLAP data cubes using covering codes. // Proceedings of 16th ACM Symposium on Principles of Database Systems. Tucson, AZ, USA. - May 1997. - P.228-237.

74. Ho C.-T., Agrawal R., Megiddo N., Srikant R. Range queries in OLAP data cubes. // Proceedings of 1997 ACM SIGMOD Intl. Conf. on Management of Data. Tucson, Arizona, USA. - June 1997. - P.73-88.

75. Jaroszewicz S., Simovici D.A. Pruning redundant association rules using maximum entropy principle. // Proceedings of 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Taipei, Taiwan. -May 2002.-P. 135-147.

76. Johnson Т., Shasha D. Hierarchically Split Cube Forests for Decision Support: description and tuned design: Technical Report TR1996-727 / Department of Computer Science, New York University. November 1996.-32 p.

77. Klemettinen M., Mannila H., Ronkainen P., Toivonen H., Verkamo A.I. Finding interesting rules from large sets of discovered association rules. // Proceedings of CIKM-94. November 1994. - P.401-407.

78. Knowledge discovery in databases обнаружение знаний в базах данных. / Лаборатория Basegroup. WEB: http://www.basegroup.ru/tasks/kdd.htm.

79. Lakshmanan L.V.S., Pei J., Han J. Quotient cube: How to summarize the semantics of a data cube. // Proceedings of VLDB'02. Hong Kong, China. -2002. -P.778-789.

80. Lavrac N., Flach P., Zupan B. Rule evaluation measures: a unifying view. // Proceedings of 9th International Workshop on Inductive Logic Programming. 1999.-P. 174-185.

81. Mannila H., Toivonen H., Verkamo A.I. Efficient algorithms for discovering association rules. // Proceedings of AAAI Workshop on Knowledge Discovery in Databases (KDD-94). Seattle, Washington.1994. P.181-192.

82. Omiecinski E.R. Alternative interest measures for mining associations in databases. // IEEE Transactions on Knowledge and Data Engineering. -Jan/Feb 2003. Vol.15, №1. -P.57-69.

83. Park J.S., Chen M.-S., Yu P.S. An effective hash based algorithm for mining association rules. // Proceedings of 1995 ACM SIGMOD International Conference on Management of Data. San Jose, CA, USA.1995.-P.175-186.

84. Park J.S., Chen M.-S., Yu P.S. Using a hash-based method with transaction trimming and database scan reduction for mining association rules. // IEEE Transactions on Knowledge and Data Engineering. 1997. - Vol.9, №5. -P.813-824.

85. Pendse N. Multidimensional data structures. WEB: http://www.olapreport.com/MDStructures.htm.

86. Pendse N. OLAP architectures. WEB: http://www.olapreport.com/Architectures.htm.

87. Pendse N. What is OLAP. WEB: http://www.olapreport.com/fasmi.htm.

88. Ross K.A., Srivastava D. Fast computation of sparse datacubes. // Proceedings of 23nd VLDB Conf. Athens, Greece. - 1997. - P. 116-125.

89. Ross К., Zaman К. Optimizing selections over data cubes: Technical report CUCS-011-98 / Department of computer science, Columbia University, USA. December 1998. - 19 p.

90. Sarawagi S., Stonebraker M. Efficient Organisation of Large MultiDimensional Arrays. // Proceedings of Eleventh International Conference on Data Ingeneering. Houston, TX. - February 1994. - P.328-336.

91. Sarawagi S., Agrawal R., Gupta A. On computing the data cube: Research Report RJ 10026 / IBM Almaden Research Center, San Jose, California. -1996.- 18 p.

92. Sarawagi S. Indexing OLAP data. // Data Engineering Bulletin. 1997. -Vol.20, №l.-P.36-43.

93. Savasere A., Omiecinski E., Navathe S. An efficient algorithm for mining association rules in large databases. // Proceedings of 21st VLDB Conference. Zurich, Switzerland. - 1995. - P.432-443.

94. Srikant R., Agrawal R. Mining Generalized Association Rules. // Proceedings of 21th International Conference on VLDB. Zurich, Switzerland. - 1995. - P.407-419.

95. Tan P., Kumar V., Srivastava J. Selecting the right interestingness measure for association patterns. // Proceedings of Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. -2002.-P.32-41.

96. Toivonen H. Sampling Large Databases for Association Rules. // Proceedings of 22nd International Conference on Very Large Databases. -Bombay, India. September 1996. -P.134-145.

97. Xin D., Han J., Li X., Wah B.W. Star-cubing: computing iceberg cubes by top-down and bottom-up integration. // Proceedings of Int. Conf. on Very Large Data Bases. 2003. - P.476-487.

98. Yao Y.Y., Zhong N. An analysis of quantitative measures associated with rules. // Proceedings of Third Pacific-Asia Conference on Knowledge Discovery and Data Mining. 1999. - P.479-488.

99. Zhao Y., Deshpande P.M., Naughton J.F. An array-based algorithm for simultaneous multidimensional aggregates. // Proceedings of ACM SIGMOD Conf. 1997. - P. 159-170.

100. Zhao Y., Ramasamy K., Tufte K., Naughton J. Array-Based Evaluation of Multi-Dimensional Queries in Object-Relational Database Systems. // Proceedings of ICDE. Orlando, USA. - 1998. - P.241-249.