EAGER: Algorithms for Data Set Versioning: Store or Re-create?

在从医学到气候变化等多个领域的科学研究中，通过技术便利获取大型数据集正日益成为科学研究的关键，研究人员团队同时参与访问、修改和清理数据集。不足为奇的是，这种协作使用数据带来了与数据管理相关的重大挑战。事实上，大规模数据集的持续修改经常导致随着时间的推移创建数千个版本的数据集，特别是作为多个用户？随时间推移访问和编辑数据。这种激增引发了一些基本问题：一个文档的所有版本都应该保存吗？虽然这当然很方便，但存储成本可能高得令人望而却步。或者，是否应该只保存某个版本？在这种情况下，虽然存储成本很低，但由于更改现有版本所涉及的工作，重新创建特定版本的成本可能会显著上升。该项目侧重于在大数据环境中平衡存储需求与高效信息检索所带来的基本挑战。因此，这项提议的主要研究目标是设计可证明良好的算法，这些算法不仅将导致对存储和再创建权衡的更深入的理解，而且将有助于开发基于坚实的理论基础的有效的数据存储系统。在之前的NSF资助的项目中，PI已经与女性和高中生进行了广泛而成功的合作，这个项目也将涉及类似的合作。在过去的五年中，国际和平研究所已经毕业了三名女性博士，目前正在为另外三名提供咨询。他还与几名正在攻读博士学位的女本科生合作过。此外，国际计算机协会还发挥了关键作用，建立了与国家编织网络项目的联系，支持妇女计算协会的部门分会，并组织了各种活动，重点是将知名女计算机科学家作为当前学生的榜样。这个基本问题可以在图论框架内建模为有向加权图。每个节点表示一个版本。在一般形式中，每条边(a，b)具有两个相关参数--权重表示在给定a的副本的情况下生成版本b的存储成本，以及成本表示实际执行将a转换为b的计算的成本。虽然这两个参数密切相关，但它们可以是不同的。此外，边际权重和成本可能非常不对称。这样做的主要原因是，当通过删除数据创建新版本时，我们可以简单地指定删除很大一部分数据，而插入的反向操作需要实际指定要插入的数据。在这个框架中，目标是计算一棵有根的树，树的结构和深度控制着存储和重新创建的权衡。虽然对于无向图的这个问题已经有了很深的理解，但这些方法都不能有效地用于有向图。这个项目将加深对这一基本问题的理解。

Technologically facilitated access to large data sets is increasingly emerging as key to scientific research in areas ranging from medicine to climate change with teams of researchers simultaneously engaged in accessing, modifying and cleaning data sets. Not surprisingly, such collaborative data-use has engendered substantial challenges related to data management. Indeed, the continuous modification of large-scale data sets frequently results in the creation of thousands of versions of data sets over time, especially as multiple users? access and edit the data over time. Such proliferation raises some basic questions: Should all versions of a document be saved? While this is certainly convenient, the storage costs may be prohibitively high. Alternatively, should only a certain version be saved? In this case, while the storage costs are low, the cost of recreating a particular version can rise significantly due to the effort involved in making changes to an existing version. This project focuses on the fundamental challenges arising from balancing storage needs with efficient retrieval of information in the context of big data. Thus the primary research goal of this proposal is to design provably good algorithms that will not only result in a deeper understanding of the storage and re-creation tradeoff but will also contribute to the development of effective data storage systems that are based on a sound theoretical foundation.In previous NSF-funded projects, the PI has collaborated extensively and successfully with women and high school students and this project will also involve similar collaborations. Over the course of the past five years, the PI has graduated three women PhDs and is currently advising another three. He has also worked with several women undergraduates who are now pursuing doctoral degrees. Additionally, the PI has played a key role establishing connections with the national Braid project, supporting the departmental chapter of the Association of Women in Computing and organizing events and activities focused on bringing in established women computer scientists as role models for current students. This fundamental problem can be modeled within a graph theoretic framework, as a directed weighted graph. Each node denotes a version. In the general form each edge (a,b) has two associated parameters - a weight denoting the storage cost to generate version b, given a copy of a and a cost denoting the cost to actually perform the computation of converting a to b. While both these are closely related, they could be different. In addition, the edge weights and costs can be wildly asymmetric. The primary reason for this is that when a new version is created by deleting data, we can simply specify that a significant portion of the data is deleted, however the reverse operation of insertion needs to actually specify the data to be inserted. In this framework, the goal is to compute a rooted tree and the structure and depth of the tree controls the storage and re-creation trade-off. While there exists a deep understanding of this problem for undirected graphs, none of those methods work effectively for directed graphs. This project will develop a deeper understanding of this basic problem.