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

• Янкелевич, Алексей Владимирович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Янкелевич, Алексей Владимирович

ВВЕДЕНИЕ

ГЛАВА 1. ПРОБЛЕМЫ ПОИСКА ИНФОРМАЦИОННЫХ ШАБЛОНОВ В ХРАНИЛИЩАХ И ПОТОКАХ ИНФОРМАЦИИ

1.1. ЭВОЛЮЦИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ

1.2. Анализ современных средств поиска информационных шаблонов

1.2.1. Информационный шаблон

1.2.2. элементные множества и последовательности элементных множеств

1.2.3. Ассоциативные правила

1.2.4. Основы теории поиска информационн ых шаблонов

1.2.5. Компактное представление коллекций шаблонов

1.2.6. Кластеризация

1.3. Выводы и постановка задачи

ГЛАВА 2. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПОИСКА ИНФОРМАЦИОННЫХ ШАБЛОНОВ В ХРАНИЛИЩАХ ИНФОРМАЦИИ

2.1. Задача поиска последовательностей элементных множеств в хранилище транзакций

2.2. Разработка алгоритма поиска последовательностей элементных множеств в хранилище транзакций

2.3. Исследование эффективности алгоритма

2.4. Выводы

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ ПОИСКА ШАБЛОНОВ В ПОТОКАХ ТРАНЗАКЦИЙ

3.1. Задача поиска информационных шаблонов в потоке транзакций

3.2. Разработка алгоритма поиска элементных множеств в потоке транзакций

3.3. Исследование эффективности алгоритма поиска элементных множеств в потоке транзакций

3.4. Разработка алгоритма поиска последовательностей элементных множеств в потоке транзакций

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

3.6. Выводы

ГЛАВА 4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ В ЗАДАЧАХ ИНФОРМАЦИОННО-АНАЛИТИЧЕСКОГО ОБЕСПЕЧЕНИЯ

4.1. Система автоматизации информационной инфраструктуры

4.2. выводы

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

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

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

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

• обработка финансовой информации;

• анализ покупательской активности;

• мониторинг в системах безопасности;

• обработка потоков данных и мониторинг в системах автоматизации бизнес-процессов;

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

Одним из решений обозначенных проблем являются так называемые системы извлечения данных (англ. Data Mining). Научная область систем извлечения данных включает в себя практически все наиболее значимые направления исследования прикладного использования алгоритмов искусственного интеллекта. К этим направлениям можно отнести классификацию, кластеризацию, поиск информационных шаблонов, прогнозирование. Одним из наиболее практически значимых направлений является поиск информационных шаблонов. Под поиском информационных шаблонов понимается поиск и классификация взаимосвязей, закономерностей в гетерогенном хранилище или потоке информации. Поскольку выявление взаимосвязей, подразумевает выполнение операций не на уровне отдельных информационных объектов, а на уровне всего хранилища/потока информации, то этот процесс является гораздо более вычислительно- и ресурсоемким, нежели обычные процедуры поиска и классификации в базах данных. Таким образом, совершенствование алгоритмов поиска и классификации взаимосвязей и закономерностей в гетерогенных хранилищах и потоках информации является важной и актуальной для дальнейшего развития средств автоматизированного анализа. Несмотря на то, что история разработки алгоритмов искусственного интеллекта, предназначенных для классификации, кластеризации и предсказания, насчитывает уже более полувека, направление, связанное с поиском информационных шаблонов, является относительно новым. Первые значимые исследования в этой области датированы началом 90-х годов прошлого века. Сама концепция информационного шаблона впервые была предложена исследователями лаборатории IBM Research в 1992 году. Исследователями М.Заки, Р.Агравалем была описана математическая модель поиска информационных шаблонов, предложена концепция элементного множества и последовательности элементных множеств.

Цели и задачи. Целью работы является повышение скорости работы алгоритмов поиска информационных шаблонов в хранилищах информации и разработка новых алгоритмов поиска информационных шаблонов в потоках информации.

Реализация поставленной цели подразумевает решение следующих задач:

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

• Исследование проблемы поиска элементных множеств и последовательностей в потоках информации;

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

• Разработка алгоритма поиска элементных множеств в потоке информации;

• Разработка алгоритма поиска последовательностей в потоке информации;

• Программная реализация разработанных алгоритмов.

Объект исследования. Объектом исследования являются программные средства, математические методы и модели поиска информационных шаблонов в гетерогенных хранилищах и потоках информации.

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

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

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

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

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

• Предложен метод оценки ресурсоемкости алгоритма поиска элементных множеств и последовательностей элементных множеств;

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

Реализация результатов. Разработанные в данной работе программные средства входят в состав комплекса «Система автоматизации информационной инфраструктуры», внедренного в компании ЗАО «КРОК инкорпорейтед».

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на трех конференциях: в 2005, 2006 годах на всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» и 2007 году на XXXVI международной конференции молодых ученых «Информационные технологии в науке, социологии, экономике и бизнесе IT+S&E'07».

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

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

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

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

Заключение

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

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

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

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

4. Разработан алгоритм поиска последовательностей элементных множеств в потоке данных. Предложен новый подход к обработке данных внутри «плавающего окна». Проведено практическое исследование алгоритма. Предложены подходы к теоретической оценке показателей производительности алгоритма;

5. Создана библиотека программных компонент, реализующих предложенные алгоритмы;

Список литературы диссертационного исследования кандидат технических наук Янкелевич, Алексей Владимирович, 2007 год

1. Ramesh С. Agarwal, Charu С. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent item sets. Journal of Parallel and Distributed Computing, 61:350-371, 2001.

2. G. Ausiello, P. Crescenzi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, 1999.

3. Setsuo Arikawa and Einoshin Suzuki, editors. Discovery Science, 7th International Conference, DS 2004, Padova, Italy, October 2-5, 2004,

4. Proceedings, volume 3245 of Lecture Notes in Computer Science. Springer, 2004.

5. Ralph Kimball, "The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses", John Wiley & Sons, 1996 и "The Data Webhouse Toolkit: Building the Web-Enabled Data Warehouse", John Wiley & Sons, 2000

6. E.F. Codd, S.B. Codd, and C.T.Salley, Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Technical report, 1993

7. Янкелевич A.B. Построение автоматизированных систем текстовой классификации на базе векторной модели // Математическое моделирование и управление в сложных системах. Сборник научных трудов. Выпуск 8. М.: МГАПИ, 2005.-с. 98-101.

8. Янкелевич А.В. Фонетический анализ в задачах текстовой классификации // Математическое моделирование и управление в сложных системах. Сборник научных трудов. Выпуск 8. М.: МГАПИ, 2005. - с. 101-102.

9. Ахрем А. А., Янкелевич А.В. Поиск максимальных последовательностей элементных множеств с помощью битовых матриц // Труды ИСА РАН «Информационно аналитические аспекты в задачах управления», Т.29. М.:КомКнига, 2007. - с. 276-289.

10. Янкелевич А.В. Алгоритм поиска максимальных последовательностей элементных множеств с помощью битовых матриц // Сборник трудов X Всероссийской научно-технической конференции (Москва, МГУ ПИ, 19-20 апреля 2007г.) М.: МГУПИ, 2007. - с.180-184.

11. Г. Корн, Т. Корн, Справочник по математике, М. «Наука» 1973 г., 832 стр. с илл.

12. Гутер Р.С., Резниковский П.Т., Программирование и вычислительная математика, М. «Наука» 1971 г., 264 стр. с илл.

13. Бермант А.Ф., Краткий курс математического анализа для втузов,М. Физматгиз 1963г., 664 стр. с илл.

14. Аттетков А.В., Галкин С.В., Зарубин B.C., Методы оптимизации, М. МГТУ им. Н.Э. Баумана

15. Правовая охрана программ для ЭВМи баз данных. М.: Издательство ПРИОР,2002. - 48 с.

16. Кнут Д.Э. Искусство программирования, том. 3. Сортировка и поиск.,СПб.: Издательский дом «Вильяме»

17. Кнут Д.Э. Искусство программирования, том. 1. Основные алгоритмы.,СПб.: Издательский дом «Вильяме»

18. Топп У., Форд У. Структуры данных С++

19. Дейт К.Дж., Введение в системы баз данных,6-е издание,24.0'Коннор Дж. Искусство системного мышления, Пер. с англ.

20. М.: Альпина Бизнес Букс,2006. 256 с.

21. Jean-Fran, cois Boulicaut and Savso Dvzeroski, editors. 2nd International Workshop on Knowledge Discovery in Inductive Databases, 2003.

22. Francesco Bonchi, Fosca Giannotti, Alessio Mazzanti, and Dino Pedreschi. ExAnte: Anticipated data reduction in constrained pattern mining. In Lavravc et al.

23. Mihai B'adoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr'eal, Qu'ebec, Canada, pages 250-257. ACM, 2002.

24. J'er'emy Besson, C'eline Robardet, and Jean-Fran.cois Boulicaut. Constraint-based mining of formal concepts in transactional data. In Dai et al. DSZ04., pages 615-624.

25. Leo Breiman. Random forests. Machine Learning, 45:5-32,2001.

26. Artur Bykowski, Jouni K. Sepp'anen, and Jaakko Holm'en. Model-independent bounding of the supports of Boolean formulae in binary data. In Mika Klemettinen and Rosa Meo, editors, KDID. Helsinki University Printing House, Helsinki, 2002.

27. Yves Bastide, Rafik Taouil, Nicolas Pasquier, Gerd Stumme, and Lotfi Lakhai. Mining frequent patterns with counting inference. SIGKDD Explorations, 2(2):66-75,2000.

28. Christian S. Calude. Algorithmic Information Theory: An Algorithmic Perspective. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2nd edition, 2002.

29. Toon Calders. Computational complexity of itemset frequency satisfiability. In Proceedings of the Twenty-Third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-18,2004, Maison de la Chimie, Paris, France. ACM, 2004.

30. Toon Calders. Deducing bounds on the supports of itemsets. In Meo et al. MLK04., pages 214-233.

31. Marek Chrobak and Christoph D'urr. Reconstructing polyatomic structures from discrete X-rays: NPcompleteness proof for three atoms. Theoretical Computer Science, 259(l-2):81-98, 2001.

32. Toon Calders and Bart Goethals. Minimal k-free representations of frequent sets. In Lavra"c et al.

33. Gemma Casas-Garriga. Discovering unbounded episodes in sequential data. In Lavravc et al.

34. E. G. Coffman Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis. Perfect packing theorems and the averagecase behaviour of optimal and online bin packing. SIAM Review, 44(1 ):95-108,2002.

35. Nick Cercone, Tsau Young Lin, and Xindong Wu, editors. Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November 2 December 2001, San Jose, California, USA. IEEE Computer Society, 2001.

36. W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11,2003, San Diego, CA, USA. ACM, 2003.

37. Luc De Raedt. A perspective on inductive databases. SIGKDD Explorations, 4(2):69-77, 2003.

38. Heikki Mannila and Hannu Toivonen. Levelwise search and borders of theories in knowledge discovery. Data Mining and Knowledge Discovery, 1(3):241-258,1997.

39. Luc De Raedt, Manfred Jaeger, Sau Dan Lee, and Heikki Mannila. A theory of inductive query answering. In Kumar and Tsumoto KT02., pages 123-130.

40. Luc Dehaspe and Hannu T.T. Toivonen. Discovery of relational association rules. In Savso Dvzeroski and Nada Lavravc, editors, Relational Data Mining, pages 189-212. Springer, 2001.

41. Vladimir Estivill-Castro. Why so many clustering algorithms a position paper. SIGKDD Explorations, 4(l):65-75, 2002.

42. Tapio Elomaa and Juho Rousu. On the computational complexity of optimal multisplitting. Fundamenta Informaticae, 47(1—2):35—52, 2001.

43. Alexandre Evfimievski, Ramakrishnan Srikant, Rakesh Agrawal, and Johannes Gehrke. Privacy preserving mining of association rules. In Hand et al.

44. Usama Fayyad. The digital physics of data mining. Communications of the ACM, 44(3):62-65, 2001.

45. Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. Journal of the Association for Computing Machinery, 47(6):987—1011, 2000.

46. Uriel Feige. A threshold of In n for approximation set cover. Journal of the Association for Computing Machinery, 45(4):634 652,1998.

47. Tom'as Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In Proceedings of the twentieth annual ACM

48. Symposium on Theory of Computing, Chicago, Illinois, May 2-4, 1988, pages 434-444. ACM, 1988.

49. Walter D, Fisher. On grouping for maximum homogeneity. Journal of the American Statistical Association, 53(284):789-798,1958.

50. Csilla Farkas and Sushil Jajodia. The inference problem: A survey. SIGKDD Explorations, 4(2):6-l 1,2002.

51. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and Systems Science, 57(2): 187-199, 1998.

52. Usama Fayyad and Ramasamy Uthurusamy. Evolving data mining into solutions for insights. Communications of the ACM, 45(8):28-31,2002.

53. Zvi Galil. Efficient algorithms for finding maximum matchings in graphs. ACM Computing Surveys, 18(l):23-38, 1986.

54. Robert Gwadera, Mikhail Atallah, and Wojciech Szpankowski. Reliable detection of episodes in event sequences. In Wu et al. WTS03., pages 67-74.

55. Floris Geerts, Bart Goethals, and Taneli Mielik'ainen. Tiling databases. In Arikawa and Suzuki AS04., pages 278-289.

56. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman and Company, 1979.

57. R. Giegerich and S. Kurtz. From Ukkonen to Mc-Creight and Weiner: A unifying view of linear-time suffix tree construction. Algorithmica, 19:331-353, 1997.

58. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31:228 248, 1999.

59. Dimitrios Gunopulos, Roni Khardon, Heikki Mannila, Sanjeev Saluja, Hannu Toivonen, and Ram Sewak Sharma. Discovering all most specific sentences. References 189ACM Transactions on Database Systems, 28(2): 140-174, 2003.

60. Lise Getoor, Ted E. Senator, Pedro Domingos, and Christos Faloutsos, editors. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 27, 2003. ACM, 2003.

61. Gunter Grieser, Yuzuru Tanaka, and Akihiro Yamamoto, editors. Discovery Science, 6th International Conference, DS 2003, Sapporo, Japan, October 17- 19, 2003, Proceedings, volume 2843 of Lecture Notes in Computer Science. Springer, 2003.

62. Bart Goethals and Jan Van den Bussche. On supporting interactive association rule mining. In Yahiko Kambayashi, Mukesh K. Mohania, and A. Min Tjoa, editors, DaWaK, volume 1874 of Lecture Notes in Computer Science, pages 307-316. Springer, 2000.

63. Bart Goethals and Jan Van den Bussche. Relational association rules: Getting WARMeR. In Hand et al. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foundations. Springer-Verlag, 1999.

64. David J. Hand, Niall M. Adams, and Richard J. Bolton, editors. Pattern Detection and Discovery, ESF Exploratory Workshop,1.ndon, UK, September 16-19, 2002, Proceedings, volume 2447 of Lecture Notes in Computer Science. Springer, 2002.

65. Jiawei Han, Russ B. Altman, Vipin Kumar, Heikki Mannila, and Daryl Pregibon. Emerging scientific applications in data mining. Communications of the ACM, 45(8):54-58, 2002.

66. David J. Hand. Pattern detection and discovery. In Hand et al. HAB02., pages 1-12.

67. Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, 2000.

68. Mohammed J. Zaki. SPADE: An efficient algoritm for mining frequent sequences. Machine Learning, 42:31- 60, 2001.

69. Mohammed J. Zaki. Efficiently mining frequent trees in a forest. In Hand et al. HKN02.

70. Mohammed Javeed Zaki and Mitsunori Ogihara. Theoretical foundations of association rules. In SIGMOD'

71. D. Hand, D. Keim, and R. Ng, editors. Proceedings of the Eighth ACM SIGKDD International Conference References 191 on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta, Canada. ACM, 2002.

72. PauI Helman, Bernard M. E. Moret, and Henry D. Shapiro. An exact characterization of greedy structures. SIAM Journal on Discrete Mathematics, 6(2):274 283, 1993.

73. David J. Hand, Heikki Mannila, and Padhraic Smyth. Principles of Data Mining. MIT Press, 2001.

74. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Auotmata Theory, Languages and Computation. Addison-Wesley, 2nd edition, 2001.

75. Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(l):53-87, 2004.

76. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer-Verlag, 2001.

77. Robert W. Irving and Mark R. Jerrum. Threedimensional statistical data security problems. SIAM Journal on Computing, 23(1): 170-184, 1994.

78. Thomasz Imieli'nski, Leonid Khachiyan, and Amin Abdulghani. Cubegrades: Generalizing association rules. Data Mining and Knowledge Discovery, 6(3):219-257, 2002.

79. Thomas Imielinski and Heikki Mannila. A database perspective on knowledge discovery. Communications of The ACM, 39(11):58—64, 1996.

80. Akihiro Inokuchi, Takshi Washio, and Hiroshi Motoda. Complete mining of frequent patterns from graphs: Mining graph data. Machine Learning, 50:321-354, 2003.

81. H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, and Torsten Suel. Optimal histograms with quality guarantees. In Ashish Gupta, Oded Shmueli, and Jennifer

82. Widom, editors, VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA, pages 275- 286. Morgan Kaufmann, 1998.

83. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2001.

84. Michihiro Kurakochi and George Karypis. Frequent subgraph discovery. In Cercone et al. CLW01., pages 313-320.

85. O.David Kempe, Jon Kleinberg, and 'Eva Tardos. Maximizing the spread of influence through a social network.

86. Jon Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems (NIPS), volume 15, 2002.

87. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry: Theory and Applications, 28:89-112, 2004.

88. Donald E. Knuth. Sorting and Seaching, volume 3 of The Art of Computer Programming. Addison-Wesley, second edition, 1998.

89. Ron Kohavi, Neal J. Rothleder, and Evangelos Simoudis. Emerging trends in business analytics. Communications of the ACM, 45(8):45-48, 2002.

90. Marzena Kryszkiewicz. Concise representation of frequent patterns based on disjunction-free generators. In Cercone et al., pages 305312.

91. Feng Pan, Gao Cong, Anthony К. H. Tung, Jiong Yang, and Mohammed J. Zaki. CARPENTER: Finding closed patterns in long biological datasets. In Getoor et al.

92. Jianyong Wang, Jiawei Han, and Jian Pei. CLOSET+: Searching for the best strategies for mining frequent closed itemsets. In Getoor et al.

93. J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen,U. Dayal, and M.-C. Hsu. PrefixSpan miningR.

94. О внедрении результов кандидатской диссертации «Математическое и программное обеспечение для поиска информационных шаблонов в хранилищах и потоках транзакций»