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

由于环境和社会的变化，如森林砍伐、城市扩张和人口/交通的快速增长，现代城市系统在可持续发展方面面临着越来越大的挑战。为了应对这些挑战，一项基本任务是确定这些变更过程的足迹（即，何时何地）。同时，许多时空大数据集（STBD），如细粒度的环境和气候观测和详细的公共交通记录，正在向公众开放。分析这些数据以获得城市变化足迹（CHAF），有助于城市规划者预见和理解潜在的可持续性问题。然而，由于大多数更改过程的非单调性、STBD中候选模式的大基数以及计算效率和模式质量之间的非平凡权衡，这种分析提出了重大挑战。该项目将研究自动化、高效和有效的数据挖掘技术，以发现城市STBD中复杂的CHAF模式。研究结果有望提高当前STBD分析工具分析变化相关模式的能力。所提出的计算框架可以应用于解决视频和图像处理中的模式发现等广泛的其他问题。此外，研究结果将应用于现实世界的数据集，以发现有用的城市变化模式，以提高社会对可持续性的理解。除了研究之外，该项目还将促进爱荷华大学研究生水平的时空数据挖掘课程的发展，并有助于培养未来的空间计算专业人员。该项目还将整合活动，让本科生和来自代表性不足群体的学生参与进来。现有的STBD分析技术只专注于检测相对简单的CHAF模式（例如，规则形状的单调变化），并且通常只报告少量CHAF（例如，最可能或最可能的变化）。本项目将重点研究在时间上非单调、空间上形状不规则的CHAF模式。所提议的技术还将保证结果的完整性，即根据给定的定义报告数据中的所有CHAFs。具体来说，项目将探讨以下思路。(1)设计统计功能强大且计算友好的非单调CHAFs的兴趣度量。(2)设计算法构建块，以有效地评估具有相似性质（例如代数）的一系列CHAF兴趣度量函数。(3)设计保证结果完备性的子空间枚举通用计算框架。在该框架中，三维子空间及其优势关系将被建模为一种新的基于子立方体的有向无环图（SCB-DAG）。本文将探讨SCB-DAG的高效遍历和剪枝策略，以枚举候选chf。本研究将提供实际数据的理论和实验评估，以验证所提出想法的正确性、完整性和可扩展性。欲了解更多信息，请参阅项目网页：http://www.biz.uiowa.edu/faculty/xzhou/project/NSF_CRII/index.html

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