# Dynamic Data Layout Optimization with Worst-case Guarantees

arXiv: https://arxiv.org/abs/2405.04984 · HTML: https://mlsanity.com/paper/2405.04984/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 52 references that are in the map.
- First posted on arXiv 8 May 2024.

## Builds on (most cited first, 8 of 8)

- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [Metrical task systems on trees via mirror descent and unfair gluing](https://mlsanity.com/paper/1807.04404/) (2018)
- [TASM: A Tile-Based Storage Manager for Video Analytics](https://mlsanity.com/paper/2006.02958/) (2020)
- [Pure entropic regularization for metrical task systems](https://mlsanity.com/paper/1906.04270/) (2019)
- [Online Learning with Many Experts](https://mlsanity.com/paper/1702.07870/) (2017)
- [Approximate Partition Selection for Big-Data Workloads using Summary Statistics](https://mlsanity.com/paper/2008.10569/) (2020)
- [Multiscale entropic regularization for MTS on general metric spaces](https://mlsanity.com/paper/2111.10908/) (2021)

## Built on by (most cited first, 1 of 1)

- [HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]](https://mlsanity.com/paper/2505.01538/) (2025)

## Abstract (arXiv)

Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve query performance by skipping over large numbers of irrelevant partitions during query processing. This mapping is referred to as a data layout. Recent works have shown that customizing the data layout to the anticipated query workload greatly improves query performance, but the performance benefits may disappear if the workload changes. Reorganizing data layouts to accommodate workload drift can resolve this issue, but reorganization costs could exceed query savings if not done carefully. In this paper, we present an algorithmic framework OReO that makes online reorganization decisions to balance the benefits of improved query performance with the costs of reorganization. Our framework extends results from Metrical Task Systems to provide a tight bound on the worst-case performance guarantee for online reorganization, without prior knowledge of the query workload. Through evaluation on real-world datasets and query workloads, our experiments demonstrate that online reorganization with OReO can lead to an up to 32% improvement in combined query and reorganization time compared to using a single, optimized data layout for the entire workload.