CIF: Small: Collaborative Research:Leveraging Data Popularity in Distributed Storage Systems via Constrained Design Theory

近年来，大规模分布式存储系统的实施以及随之而来的数据分析和编码方法激增，使其能够可靠，安全，低延迟地运行。然而，在许多系统研究中，对系统访问控制、私有信息检索和计算复杂性有重要影响的数据需求（流行度）特征在很大程度上被忽视了。这可以部分归因于大多数云存储设施为热数据和冷数据使用不同的存储平台，从而在一定程度上解决了与可变数据需求相关的问题。但是，即使在热数据和冷数据类别中，数据受欢迎程度也存在显著差异，这给系统设计带来了许多重大挑战。为了解决这些问题，提出的研究计划旨在开发一个新的数学对象家族，称为约束设计，特别是斯坦纳系统。设计表示一个基集的子集的有限集合，其元素满足关于集合的相交和排列的预定义对称约束。设计的元素与数据块相关联，而元素的子集表示存储在同一磁盘或服务器上的数据块；由于其简单和丰富的数学结构，该设计在许多实际的分布式存储系统平台上得到了成功的应用。在存在对对象和数据文件的不统一需求的情况下，单独的交叉约束不能确保底层的实现约束。因此，元素必须配备非负流行值，并且修改底层组合设计以满足数据流行值强制执行的额外代数和频率约束。这个新的模型导致了一个独特的关于加权和标记组合设计的结构具有挑战性的数学问题的集合。需要考虑的特殊问题包括开发平衡服务器访问的设计，在流行侧信息存在时的私有信息检索以及标记批处理代码的横向设计。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Recent years have witnessed a surge of large-scale distributed storage system implementations and accompanying data analyses and coding methods that enable their reliable, secure and low-delay operation. Nevertheless, in many system studies, important data demand (popularity) features which have a strong bearing on system access control, private information retrieval and computational complexity have been largely overlooked. This can be attributed in part to the fact that most cloud storage facilities employ different storage platforms for hot and cold data, thereby partly addressing problems associated with variable data demands. But even within the hot and cold data categories there exist significant variations in data popularity that create many nontrivial system design challenges.To address these issues, the proposed research program aims to develop a new family of mathematical objects termed constrained designs and Steiner systems in particular. Designs represent finite collections of subsets of a ground set whose elements satisfy predefined symmetry constraints with respect to set intersections and arrangements. Elements of a design are associated with data chunks, while subsets of elements represent data chunks to be stored on the same disk or server; given their simplicity and rich mathematical structure, designs have been used with great success in many practical distributed storage system platforms. In the presence of nonuniform demands for objects and data files, intersection constraints alone fail to ensure underlying implementation constraints. Consequently, elements have to be equipped with nonnegative popularity values, and the underlying combinatorial designs modified to satisfy additional algebraic and frequency constraints enforced by data popularity values. This new model leads to a unique collection of challenging mathematical problems regarding constructions of weighted and labeled combinatorial designs. Particular problems to be considered include developing designs for balanced server access, private information retrieval in the presence of popularity side information and transversal designs for labeled batch codes.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.