Mining tree-query associations in graphs

Abstract

Outline: This thesis is further organized as follows: In Chapter 2 we formally define a novel class of patterns, called tree queries. We introduce the notion of containment among tree queries, and define it formally. Furthermore, association rules over tree queries are defined, and we conclude the chapter by defining the mining problems that we solve in this thesis. In Chapter 3 we present an algorithm for mining tree queries in a large data graph. We start by showing that we do not need to tackle the problem in its full generality. Then, we give an overall approach, basically two loops, of the presented algorithm, and discuss it in more detail. Furthermore, we discuss equivalent tree queries, and show how the algorithm must be tuned to avoid the generation of them. We conclude the chapter with some notes on how the results of this algorithm are stored and why that is useful. In Chapter 4 we present an algorithm for mining tree-query associations. Again, we show that we do need to tackle the problem in its full generality. We give an overview of the presented algorithm and show that the tree-query mining algorithm, discussed in Chapter 3, is an ideal preprocessing step. Furthermore, we discuss the remaining steps of the algorithm in more detail. We conclude the chapter by defining equivalent association rules, and by showing how we must tune the presented algorithm to avoid the generation of them. In Chapter 5 we first introduce an interactive tool, called Certhia, for browsing the mined patterns and generating association rules. Next, we give results of some smaller experiments we performed using a prototype implementation. Furthermore, we explain how are algorithms can be used to find interesting patterns and rules in data from ecology, and give examples of interesting patterns and rules we mined. In Chapter 6 we give conclusions on the presented work and give some points that need to be improved in the future.