2021/12/13 by Carlos Cardonha, Carlos H. Cardonha, André A. Ciré +5
Computer Science · #Advanced Data Storage Technologies #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.2112.07018
32 pages, 8 tables, 9 figures
openalex publication_date 2021/12/13 · arxiv created 2022/05/09 · arxiv updated 2022/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper investigates sequencing policies for file reading requests in linear storage devices, such as magnetic tapes. Tapes are the technology of choice for long-term storage in data centers due to their low cost and reliability. However, their physical structure imposes challenges to data retrieval operations reflected in classic optimization and operations research problems. In this work, we provide a theoretical and numerical performance analysis of low-complexity algorithms under deterministic, stochastic, and online settings, which are key in practice due to their interpretability and the large scale of existing data services. In the deterministic setting, we show that traditional policies, such as first-in first-out (FIFO), have arbitrarily poor performance, and we develop and investigate new constant-factor approximations. For the stochastic setting, we present a fully polynomial-time approximation scheme that weighs files based on their access frequencies. Finally, we investigate an online extension and propose a new algorithm with constant competitive-factor guarantees. Our numerical analysis on synthetic and real-world data suggest that the proposed algorithms may significantly outperform policies currently adopted in practice with respect to average reading times.