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

由于环境和社会的变化，如森林砍伐、城市扩张和人口/交通的快速增长，现代城市系统在可持续发展方面面临着日益重大的挑战。为了应对挑战，一项重要任务是确定足迹（即，在哪里和什么时候）这些变化过程。与此同时，许多时空大数据集（STBD），如细粒度的环境和气候观测以及详细的公共交通记录，正在向公众提供。分析这些数据以获得城市变化足迹（CHAF）有助于城市规划者预测和了解潜在的可持续性问题。然而，这样的分析提出了重大的挑战，由于大多数变化过程的非单调性，在STBD的候选模式的大基数，以及计算效率和模式质量之间的非平凡的权衡。该项目将研究自动化，高效，有效的数据挖掘技术，发现复杂的CHAF模式在城市STBD。研究成果有望提高当前STBD分析工具分析变化相关模式的能力。所提出的计算框架可以应用于解决广泛的其他问题，如模式发现在视频和图像处理。此外，研究结果将应用于现实世界的数据集，以发现有用的城市变化模式，提高社会对可持续发展的理解。除了研究之外，该项目还将促进爱荷华州大学研究生水平的时空数据挖掘课程的开发，并有助于培训未来的空间计算专业人员。该项目还将整合活动，使本科生和来自代表性不足群体的学生参与进来。现有的STBD分析技术仅专注于检测相对简单的CHAF模式（例如，规则形状、单调变化），并且通常仅报告少量CHAF（例如，最可能或前k可能的改变）。本计画的研究将集中在发现时间上非单调且空间上形状不规则的CHAF模式。所提出的技术还将保证结果的完整性，即，基于给定的定义报告数据中的所有CHAF。具体而言，本项目将探讨以下想法。(1)设计非单调CHAF的兴趣度量，这些度量在统计上是强大的并且计算友好。(2)设计算法构建块以有效地评估具有类似属性的CHAF兴趣度量函数的范围（例如，代数）。(3)设计一个通用的子空间枚举计算框架，保证结果的完整性。在该框架中，三维子空间及其支配关系将被建模为一种新的基于子立方体的有向无环图（SCB-DAG）。将探索SCB-DAG上的有效遍历和修剪策略以枚举候选CHAF。这项研究将提供理论和实验评估的真实的数据，以验证所提出的想法的正确性，完整性和可扩展性。欲了解更多信息，请访问项目网页：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