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

CIF：小型：协作研究：通过约束设计理论利用分布式存储系统中的数据流行度

• 批准号: 1816913
• 负责人: Olgica Milenkovic
• 金额: $ 25万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816913&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Leveraging

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.

近年来，见证了大规模的分布式存储系统实施以及随附的数据分析和编码方法，这些方法可实现其可靠，安全和低延迟的操作。然而，在许多系统研究中，重要的数据需求（受欢迎程度）功能与系统访问控制，私人信息检索和计算复杂性具有很大的影响。这可以部分归因于以下事实：大多数云存储设施都采用不同的存储平台来用于冷热数据，从而部分解决了与可变数据需求相关的问题。但是，即使在冷热数据类别中，数据受欢迎程度也存在很大的差异，这些差异会引起许多非平凡的系统设计挑战。为了解决这些问题，拟议的研究计划旨在开发一个新的数学对象家族，尤其是受约束设计和施坦纳系统。设计代表了地面集的子集的有限收集，该集合的元素满足了相对于集体交叉点和布置的预定义对称约束。设计的元素与数据块相关联，而元素的子集表示要存储在同一磁盘或服务器上的数据块；鉴于它们的简单性和丰富的数学结构，设计在许多实用的分布式存储系统平台中都取得了巨大成功。在对象和数据文件的不一致需求的情况下，仅相交约束无法确保基本的实现约束。因此，必须配备非负受欢迎程度的元素，并且对基础组合设计进行了修改，以满足数据受欢迎程度值强制执行的其他代数和频率约束。这种新模型导致有关加权和标记组合设计的结构的独特数学问题集合。要考虑的特定问题包括开发用于平衡服务器访问的设计，在存在受欢迎程度侧信息的情况下进行私人信息检索以及标记批次代码的横向设计。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛的影响审查标准通过评估来通过评估来支持的。

项目成果

Finding the second-best candidate under the Mallows model

在 Mallows 模型下寻找第二好的候选者

• DOI: 10.1016/j.tcs.2022.06.029
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Liu, Xujun;Milenkovic, Olgica
• 通讯作者: Milenkovic, Olgica