Can I read Competitive Data-Structure Dynamization on EtoBox?

Competitive Data-Structure Dynamization by Mathieu, Claire; Rajaraman, Rajmohan; Young, Neal E.; Yousefi, Arman is a scholarly article available to read on EtoBox.

What is Competitive Data-Structure Dynamization about?

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 Google Bigtable and LevelDB (our focus). Previous theoretical work is based on worst-case 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 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 minim

Author

Mathieu, Claire; Rajaraman, Rajmohan; Young, Neal E.; Yousefi, Arman

Published

2020

Language

EN