Search

There has been an explosive growth of spatial data over the last decades thanks to the popularity of location-based services (e.g., Google Maps), affordable devices (e.g., mobile phone with GPS receiver), and fast development of data transfer and storage technologies. This significant growth as well as the emergence of new technologies emphasize the need for automated discovery of spatial patterns which can facilitate applications such as mechanical engineering, transportation engineering, and public safety. This thesis investigates novel and societally important patterns from various types of large scale spatial events such as spatial point events, spatio-temporal point events, and spatio-temporal linear events. Multiple novel approaches are proposed to address the statistical, computational, and mathematical challenges posed by different patterns. Specifically, a neighbor node filter and a shortest tree pruning algorithms are developed to discover linear hotspots on shortest paths, a bi-directional fragment-multi- graph traversal is proposed for discovering linear hotspots on all simple paths, and an apriori-graph traversal algorithm is proposed to detecting spatio-temporal intersection patterns. Extensive theoretical and experimental analyses show that the proposed approaches not only achieve substantial computational efficiency but also guarantee mathematical properties such as solution correctness and completeness. Case studies using real-world datasets demonstrate that the proposed approaches identify valuable patterns that are not detected by current state-of-the-art methods.

Similarity search is important for many data-intensive applications to identify a set of similar objects. Examples of such applications include near-duplicate detection and clustering, collaborative filtering for similarity-based recommendations, search query suggestion, and data cleaning. Conducting similarity search is a time-consuming process, especially when a massive amount of data is involved, and when all pairs are compared. Previous work has used comparison filtering, inverted indexing, and parallel accumulation of partial intermediate results to expedite its execution. However, shuffling intermediate results can incur significant communication overhead as data scales up.We have developed a fast two-stage partition-based approach for all-pairs similarity search which incorporates static partitioning, optimized load balancing, and cache-conscious data traversal. Static partitioning places dissimilar documents into different groups to eliminate unnecessary comparison between their content. To overcome the challenges introduced by skewed distribution of data partition sizes and irregular dissimilarity relationship in large datasets, we conduct computation load balancing for partitioned similarity search, with competitiveness analysis. These techniques can improve performance by one to two orders of magnitude with less unnecessary I/O and data communication and better load balance. We also discuss how to further accelerate similarity search by incorporating incremental computing and approximation methods such as Locality Sensitive Hashing. Because of data sparsity and irregularity, accessing feature vectors in memory for runtime comparison incurs significant overhead in modern memory hierarchy. We have designed and implemented cache-conscious algorithms to improve runtime efficiency in similarity search. The idea of optimizing data layout and traversal patterns is also applied to the search result ranking problem in runtime with multi-tree ensemble models.