CRII: III: Discovering Complex Change Footprint Patterns on Spatio-Temporal Big Data for Urban Sustainability

University Of Iowa, Iowa City IA

Investigators

Abstract

Modern urban systems are facing increasingly significant challenges in sustainable development due to environmental and societal changes such as deforestation, urban sprawl, and rapid population/traffic growth. To respond to the challenges, an essential task is to identify the footprints (i.e., where and when) of these change processes. In the meantime, many spatio-temporal big datasets (STBD) such as fine-grained environmental and climate observations and detailed public transportation records are being made available to the public. Analyzing these data for urban change footprints (CHAF) helps city planners foresee and understand potential sustainability issues. However, such analyses pose significant challenges due to the non-monotonic nature of most change processes, the large cardinality of candidate patterns in STBD, and the non-trivial tradeoff between computational efficiency and pattern quality. This project will investigate automated, efficient, and effective data mining techniques for the discovery of complex CHAF patterns in urban STBD. The research outcomes are expected to enhance the ability of current STBD analytics tools to analyze change-related patterns. The computational framework proposed can be applied to solve a broad range of other problems such as pattern discovery in video and image processing. Also, the research results will be applied to real-world datasets to discover useful urban change patterns to improve the society's understanding of sustainability. Beyond research, this project will facilitate the development of a graduate level spatio-temporal data mining course at the University of Iowa, and contribute to the training of future professionals in spatial computing. The project will also integrate activities to involve undergraduate students and students from underrepresented groups. Existing STBD analytical techniques only focus on detecting relatively simple CHAF patterns (e.g., regularly-shaped, monotonic changes), and typically report only a small number of CHAFs (e.g., the most or top-k likely changes). The research in this project will focus on the discovery of CHAF patterns that are non-monotonic temporally and irregularly-shaped spatially. The proposed techniques will also guarantee the completeness of results, i.e., report all the CHAFs in the data based on a given definition. Specifically, the following ideas will be explored in the project. (1) Designing interest measures of non-monotonic CHAFs that are statistically powerful and computation-friendly. (2) Designing algorithmic building blocks to efficiently evaluate a range of CHAF interest measure functions with similar properties (e.g., algebraic). (3) Designing a generic computational framework for sub-space enumeration that guarantees the completeness of results. In the proposed framework, the three-dimensional sub-spaces and their dominance relationships will be modeled as a novel sub-cube-based directed acyclic graph (SCB-DAG). Efficient traversal and pruning strategies on the SCB-DAG will be explored to enumerate candidate CHAFs. This research will provide theoretical and experimental evaluations on real data to validate the correctness, completeness and scalability of the proposed ideas. For further information see the project web page: http://www.biz.uiowa.edu/faculty/xzhou/project/NSF_CRII/index.html