Open Collections

Abstract

The goal of the thesis is to discover knowledge on large spatial databases. Specifically, it discusses the problem of extracting patterns and characteristics of clusters from thematic maps. For instance, a characteristic of an expensive housing cluster may be that the average household income is over 100,000 dollars. Three key issues are addressed in this thesis. The first issue is how to measure the interest/utility values of characteristics. In order to accommodate different kinds of thematic maps, two measures are proposed and analysed: one based on entropy, and the other on standard deviation. Both measures satisfy all the desirable properties, and work effectively in practice. The second issue is how to extract patterns from multiple clusters. Two pattern extraction operations are defined. The common() operation is able to find the common characteristics among multiple clusters. The different() operations is capable of discovering the characteristics which distinguish one cluster from another. The third issue is how to compute characteristics utility measures and pattern extraction operations efficiently. Four different methods are proposed and evaluated for the computation of utility measures. Complexity and experimental results indicates that a technique based on isothetic rectangle intersections is the most efficient, outperforming all the other techniques such as a technique based on R-tree technique. For the problem of how to extract patterns of multiple clusters efficiently. Two different methods for pattern extraction are evaluated. The technique based on isothetic rectangle intersections again outperforms the technique based on R-tree, and can extract patterns from hundreds of thematic maps in seconds of CPU time.