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

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.