Competitive Data-Structure Dynamization
Competitive Data-Structure Dynamization
复制标题
DOI：
10.1145/3672614
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Claire Mathieu;R. Rajaraman;N. Young;A. Yousefi
中科院分区：
文献类型：
--
作者：
Claire Mathieu;R. Rajaraman;N. Young;A. Yousefi
数据结构动态化是使静态数据结构动态化的一般方法。它被广泛用于几何设置，并在LevelDB和Google Bigtable等大数据数据库中以所谓的合并(或压缩)策略为幌子。以前的理论工作是基于对均匀输入的最坏情况的分析-一次插入一项并且读取率不变。在实践中，合并策略不仅必须处理批插入和不同的读/写比率，它们还可以利用这种不一致性来降低每个输入的成本。为了模拟这一点，我们通过两个新的在线集合覆盖问题，通过竞争分析的镜头启动了数据结构动态化的研究。对于每一个，输入是一系列不相交的加权项目集。布景一次揭晓一套。算法必须用一套涵盖到目前为止揭示的所有物品的封面来回应每一件物品。它通过添加一个或多个集合并任选地移除现有集合来从先前的封面递增地获得封面。对于每个新集合，该算法产生的构建成本等于集合中项目的权重。在第一个问题中，目标是最小化总构建成本加上总查询成本，其中该算法在每个时刻t产生等于当前覆盖大小的查询成本。在第二个问题中，目标是最小化构建成本，同时保持查询成本在任何时候都不超过(K)(给定参数)。我们给出了两个变种的确定性在线算法，其竞争比分别为\(theta(\log^*n)\)和\(k\)。对于第二个变量，后一种比率是最优的。
Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs – insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis, via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost, where the algorithm incurs a query cost at each time t equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^* n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant.