In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Fatih Akdag

will defend his dissertation

A Computational Framework for Finding Interestingness Hotspots in Spatial Datasets

Abstract

The significant growth of spatial data increased the need for automated discovery of spatial knowledge. An important task when analyzing spatial data is detecting hotspot regions with specific patterns. In this thesis, we propose a novel methodology for discovering interestingness hotspots in spatial datasets. We define interestingness hotspots as contiguous regions in space which are interesting based on a domain expert’s notion of interestingness captured by an interestingness function. We propose computational methods for finding interestingness hotspots in point-based, polygon-based and gridded spatial-temporal datasets. The proposed framework identifies hotspots maximizing an externally given interestingness function defined on any number of spatial or non-spatial attributes using a 5-step methodology, which consists of: (1) identifying neighboring objects in the dataset, (2) generating hotspot seeds, (3) growing hotspots from identified hotspot seeds, (4) post-processing to remove highly overlapping hotspots, and (5) finding the scope of hotspots. In particular, we introduce novel hotspot growing algorithms that grow hotspots from hotspot seeds. Moreover, we present a novel graph-based post-processing algorithm, which removes highly overlapping redundant hotspots and employs a graph simplification step that significantly improves the runtime of finding maximum weight independent set in the overlap graph of hotspots. The proposed post-processing algorithm which relies on finding maximum weight cliques is quite generic and can be used with any methods to cope with overlapping hotspots or clusters. We evaluate our framework in case studies using a gridded air pollution dataset, point-based crime and taxicab datasets and find hotspots employing different interestingness functions. Experiments show that our approach succeeds in accurately discovering interestingness hotspots and does well in comparison to traditional hotspot detection methods.

Date: Monday, November 21, 2016
Time: 12:45 PM 
Place: PGH 550
Advisor: Dr. Christoph F. Eick

Faculty, students, and the general public are invited.