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

CRII：III：发现时空大数据的复杂变化足迹模式以促进城市可持续发展

• 批准号: 1566386
• 负责人: Xun Zhou
• 金额: $ 15.58万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1566386&HistoricalAwards=false
• 关键词: CRII; III; Discovering; Complex; Change

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

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