III: Medium: Collaborative Research: U4U - Taming Uncertainty with Uncertainty-Annotated Databases

III：媒介：合作研究：U4U - 利用不确定性注释数据库来克服不确定性

• 批准号: 1956149
• 负责人: Oliver Kennedy
• 金额: $ 53.29万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1956149&HistoricalAwards=false
• 关键词: III; Medium; Collaborative; Research; U4U

Uncertainty is prevalent in data analysis, no matter what the size of the data, the application domain, or type of analysis. Common sources of uncertainty include missing values, sensor errors, bias, outliers, and many other factors. Classical deterministic data management does not track uncertainty and, thus requires data quality issues to be resolved before data is ingested into the system, which is often not feasible. The net effect is that inherently uncertain data is being treated as certain. However, if ignored, data uncertainty results in hard to trace errors, which in turn can have severe real world implications such as unfounded scientific discoveries, financial damages, or even medical decisions based on incorrect data. While there exist techniques for managing incomplete data, these techniques are generally too heavy-weight for real-world usage and may hide relevant information from users. The goal of this project is to develop light-weight techniques for managing uncertain data that empower a wide range of applications to manage uncertainty.Current methods for managing uncertain data are often computationally expensive and are only applicable to limited types of queries. The planned research will result in novel methods for managing uncertain data that bridge the gap between deterministic and incomplete data management. The foundation of this project are uncertainty-annotated databases, which enrich data with uncertainty labels and provide semantics for propagating these labels through queries. The result is a strict generalization of classical data management that combines the performance, generality, and ease-of-use of deterministic data management with the strong correctness guarantees of incomplete database techniques. Achieving this goal is highly non-trivial, because query evaluation over uncertain data is intractable, even for relatively simple uncertain data models and restricted classes of queries. Three main research thrusts will be explored that address the main challenges in developing such a technique: (i) uncertainty-annotated databases will be extended with attribute-level annotations and an compact encoding of an over-approximation of possible answers. This enables the approach to handle missing data and to deal with non-monotone queries such as queries with aggregation; (ii) methods to compactly approximating incomplete databases will be developed to deal with the large or even infinite sets of possible results produced by queries over uncertain data; (iii) optimized algorithms for query evaluation over uncertainty-annotated databases will be developed to address the performance limitations of queries over uncertain data. The planned work will significantly enhance the state-of-the-art in uncertain data management by, for the first time, enabling principled uncertainty management for complex queries at a reasonable cost.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

不确定性在数据分析中普遍存在，无论数据的大小，应用域或分析类型的大小如何。不确定性的常见来源包括缺失值，传感器错误，偏见，离群值和许多其他因素。经典的确定性数据管理不会跟踪不确定性，因此需要在将数据摄入到系统中之前要解决数据质量问题，这通常是不可行的。净效应是，本质上不确定的数据被视为确定的。但是，如果被忽略，数据不确定性会导致难以追踪错误，从而基于错误的数据，这可能会产生严重的现实世界影响，例如毫无根据的科学发现，财务损失，甚至是医疗决策。尽管存在管理不完整数据的技术，但这些技术通常对于现实世界中的使用过度过重，并且可能会隐藏用户的相关信息。该项目的目的是开发轻重量技术来管理不确定的数据，以授权广泛的应用程序来管理不确定性。管理不确定数据的流动方法通常在计算上很昂贵，并且仅适用于有限类型的查询。计划的研究将为管理不确定的数据提供新的方法，以弥合确定性和不完整数据管理之间的差距。该项目的基础是不确定性不确定的数据库，它们具有不确定性标签的数据，并提供了通过查询传播这些标签的语义。结果是对经典数据管理的严格概括，将确定性数据管理的性能，通用性和易用性与不完整数据库技术的强烈正确性保证相结合。实现这一目标是高度不平凡的，因为对不确定数据的查询评估也很棘手，即使对于相对简单的不确定的数据模型和限制性查询类别也是如此。将探讨三个主要的研究作用，即解决开发这种技术的主要挑战：（i）不确定性不确定的数据库将通过属性级注释进行扩展，并紧凑地编码可能的答案。这使方法可以处理丢失的数据并处理非主持酮查询，例如汇总的查询； （ii）将开发紧凑近似数据库的方法，以处理由不确定数据而不是查询产生的大型甚至无限的可能结果集； （iii）将开发针对不确定性注销数据库的查询评估的优化算法，以解决不确定数据的查询的性能限制。计划的工作将首次以合理的成本为复杂查询实现原则的不确定性管理，从而大大提高不确定数据管理的最新工作。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来通过评估来获得支持的。

项目成果

Runtime provenance refinement for notebooks

笔记本的运行时出处细化

• DOI: 10.1145/3530800.3534535
• 发表时间: 2022
• 期刊: Proceedings of the 14th International Workshop on the Theory and Practice of Provenance
• 作者: Deo, Nachiket;Glavic, Boris;Kennedy, Oliver
• 通讯作者: Kennedy, Oliver

Overlay Spreadsheets

叠加电子表格

• DOI: 10.1145/3597465.3605220
• 发表时间: 2023
• 期刊: HILDA '23: Proceedings of the Workshop on Human-In-the-Loop Data Analytics
• 作者: Kennedy, Oliver;Glavic, Boris;Brachmann, Michael
• 通讯作者: Brachmann, Michael

Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds

具有属性级别界限的复杂查询的高效不确定性跟踪

• DOI: 10.1145/3448016.3452791
• 发表时间: 2021
• 期刊: SIGMOD '21: International Conference on Management of Data
• 作者: Feng, Su;Glavic, Boris;Huber, Aaron;Kennedy, Oliver A.
• 通讯作者: Kennedy, Oliver A.

The Right Tool for the Job: Data-Centric Workflows in Vizier

适合工作的工具：Vizier 中以数据为中心的工作流程

• 发表时间: 2022
• 期刊: Bulletin of the Technical Committee on Data Engineering
• 作者: Oliver Kennedy, Boris Glavic