neal young / Mathieu21Competitive

Datastructure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of socalled merge (or compaction) policies in bigdata databases such as Google Bigtable and LevelDB (our focus). Previous theoretical work is based on worstcase analyses for uniform inputs  insertions of one item at a time and constant read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such nonuniformity to reduce cost on a perinput basis.
To model this, we initiate the study of datastructure dynamization through the lens of competitive analysis, via two new online setcover 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.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.