Gala Yadgar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Gala Yadgar has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Joseph (Seffi) Naor
Technion, Haifa, Israel
4 shared publications - Tomer Lange
Technion, Haifa, Israel
4 shared publications - Sarai Sheinvald
Software Engineering, Ort Braude College of Engineering
2 shared publications - Zhaoyan Shen
Shandong University, Qingdao, China
2 shared publications - Zili Shao
The Chinese University of Hong Kong
2 shared publications - Abhinav Duggal
Dell EMC, USA
1 shared publication
Latest Publications
- Open Access
- 27 September 2026
- Published by Association for Computing Machinery (ACM)
- p. 84-91
Towards A System Model for DNA-based Storage
DNA storage is emerging as a promising medium for long-term data retention, attracting significant academic and industrial interest. However, the biological properties of DNA and current technological limitations impose unique system-level constraints: pool capacity and object count are limited, reads convert durable DNA into a more fragile hydrated form, and each pool can serve only a limited number of requests before replenishment is required. In this paper, we present the first comprehensive system model of DNA storage that captures these constraints and analyze their system-level implications. Our results show that current efforts to improve storage density and expand primer libraries must be complemented by proportional increases in read limits, support for efficient bulk retrieval during replenishment, and DNA-aware storage management policies that balance competing threats to data durability. These findings demonstrate that DNA storage requires fundamentally different system designs than conventional digital storage.
- 27 September 2026
- Published by Association for Computing Machinery (ACM)
- p. 84-91
Open AccessTowards A System Model for DNA-based Storage
DNA storage is emerging as a promising medium for long-term data retention, attracting significant academic and industrial interest. However, the biological properties of DNA and current technological limitations impose unique system-level constraints: pool capacity and object count are limited, reads convert durable DNA into a more fragile hydrated form, and each pool can serve only a limited number of requests before replenishment is required. In this paper, we present the first comprehensive system model of DNA storage that captures these constraints and analyze their system-level implications. Our results show that current efforts to improve storage density and expand primer libraries must be complemented by proportional increases in read limits, support for efficient bulk retrieval during replenishment, and DNA-aware storage management policies that balance competing threats to data durability. These findings demonstrate that DNA storage requires fundamentally different system designs than conventional digital storage.
- Open Access
- 5 November 2025
- Published by Elsevier in Performance Evaluation
- Vol. 170
Near-optimal PCM wear leveling under adversarial attacks
- 5 November 2025
- Published by Elsevier in Performance Evaluation
- Vol. 170
Open AccessNear-optimal PCM wear leveling under adversarial attacks
- Open Access
- 3 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 21 (4) , 1-28
Physical vs. Logical Indexing with IDEA: Inverted Deduplication-Aware Index
In the realm of information retrieval, the need to maintain reliable term-indexing has grown more acute in recent years, with vast amounts of ever-growing online data used for data mining and natural language processing, and searched by a large number of search-engine users. At the same time, an increasing portion of primary storage systems employ data deduplication, where duplicate logical data chunks are replaced with references to a unique physical copy. We show that indexing deduplicated data with deduplication-oblivious mechanisms might result in extreme inefficiencies: the index size would increase in proportion to the logical data size, regardless of its duplication ratio, consuming excessive storage and memory and slowing down lookups. In addition, the logically sequential accesses during index creation would be transformed into random and redundant accesses to the physical chunks. Indeed, to the best of our knowledge, term indexing is not supported by any deduplicating storage system. In this article, we propose the design of a deduplication-aware term-index that addresses these challenges. IDEA maps terms to the unique chunks that contain them, and maps each chunk to the files in which it is contained. This basic design concept improves the index performance and can support advanced functionalities such as inline indexing, result ranking, and proximity search. Our prototype implementation based on Lucene (the search engine at the core of Elasticsearch) shows that IDEA can reduce the index size and indexing time by up to 73% and 94%, respectively, and reduce term-lookup latency by up to 82% and 59% for single and multi-term queries, respectively.
- 3 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 21 (4) , 1-28
Open AccessPhysical vs. Logical Indexing with IDEA: Inverted Deduplication-Aware Index
In the realm of information retrieval, the need to maintain reliable term-indexing has grown more acute in recent years, with vast amounts of ever-growing online data used for data mining and natural language processing, and searched by a large number of search-engine users. At the same time, an increasing portion of primary storage systems employ data deduplication, where duplicate logical data chunks are replaced with references to a unique physical copy. We show that indexing deduplicated data with deduplication-oblivious mechanisms might result in extreme inefficiencies: the index size would increase in proportion to the logical data size, regardless of its duplication ratio, consuming excessive storage and memory and slowing down lookups. In addition, the logically sequential accesses during index creation would be transformed into random and redundant accesses to the physical chunks. Indeed, to the best of our knowledge, term indexing is not supported by any deduplicating storage system. In this article, we propose the design of a deduplication-aware term-index that addresses these challenges. IDEA maps terms to the unique chunks that contain them, and maps each chunk to the files in which it is contained. This basic design concept improves the index performance and can support advanced functionalities such as inline indexing, result ranking, and proximity search. Our prototype implementation based on Lucene (the search engine at the core of Elasticsearch) shows that IDEA can reduce the index size and indexing time by up to 73% and 94%, respectively, and reduce term-lookup latency by up to 82% and 59% for single and multi-term queries, respectively.
- Open Access
- 8 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 136-150
Let It Slide: Online Deduplicated Data Migration
- 8 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 136-150
Open AccessLet It Slide: Online Deduplicated Data Migration
- Open Access
- 16 June 2025
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 53 (1) , 52-54
Optimal SSD Management with Predictions
Flash-based solid state drives (SSDs) have emerged as a leading storage technology, but their unique constraints pose fundamental management challenges. Unlike hard-disk drives, SSDs do not allow in-place updates: data must be written to a clean location within a block, and only entire blocks can be cleaned. Moreover, when a block is cleaned, all valid data it stores must first be rewritten elsewhere, resulting in additional writes that harm both performance and device longevity. In this work, we present one of the few worst-case analyses of algorithms for minimizing rewrites in SSDs. Our model falls within the framework of learning-augmented algorithms: algorithms that receive advice from a prediction oracle and their performance is analyzed as a function of the oracle's error. We introduce a novel algorithm for this model, and prove that it achieves optimal worst-case guarantees. Experiments on a range of SSD workloads confirm the practical advantages of the proposed algorithm over existing SSD management schemes.
- 16 June 2025
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 53 (1) , 52-54
Open AccessOptimal SSD Management with Predictions
Flash-based solid state drives (SSDs) have emerged as a leading storage technology, but their unique constraints pose fundamental management challenges. Unlike hard-disk drives, SSDs do not allow in-place updates: data must be written to a clean location within a block, and only entire blocks can be cleaned. Moreover, when a block is cleaned, all valid data it stores must first be rewritten elsewhere, resulting in additional writes that harm both performance and device longevity. In this work, we present one of the few worst-case analyses of algorithms for minimizing rewrites in SSDs. Our model falls within the framework of learning-augmented algorithms: algorithms that receive advice from a prediction oracle and their performance is analyzed as a function of the oracle's error. We introduce a novel algorithm for this model, and prove that it achieves optimal worst-case guarantees. Experiments on a range of SSD workloads confirm the practical advantages of the proposed algorithm over existing SSD management schemes.
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 52-54
Optimal SSD Management with Predictions
- 9 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 52-54
Open AccessOptimal SSD Management with Predictions
- Open Access
- 27 May 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 9 (2) , 1-28
Optimal SSD Management with Predictions
Recently, flash-based solid state drives (SSDs) have become a primary storage solution due to their advantages over hard-disk drives. Nonetheless, SSD management presents unique challenges. First, SSDs update data by writing a new copy to a clean slot, rather than overwriting old data. Second, SSDs support cleaning of entire blocks, while slots cannot be cleaned individually. Third, when cleaning a block, any valid data it stores must first be rewritten to another location, which adversely affects the SSD endurance and throughput. In this work, we address the SSD management problem, where the objective is to minimize the number of rewrites in SSDs. We approach the problem from a theoretical perspective, analyzing algorithms in a worst-case fashion. Motivated by recent advances in machine learning, we consider a learning-augmented setting where the algorithm has access to a predictive oracle, with performance guarantees expressed as a function of the error in the oracle's output. Our main contribution is Gladiator, a novel online algorithm that optimally leverages predictions to enhance the performance of SSDs. Compared to prior work, Gladiator requires no additional non-volatile memory and is less sensitive to prediction errors. We further demonstrate the effectiveness of Gladiator under reasonable assumptions on the input distribution, and extend it to an extremely efficient offline algorithm. Empirical results confirm its superiority over state-of-the-art practical solutions across diverse SSD workloads.
- 27 May 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 9 (2) , 1-28
Open AccessOptimal SSD Management with Predictions
Recently, flash-based solid state drives (SSDs) have become a primary storage solution due to their advantages over hard-disk drives. Nonetheless, SSD management presents unique challenges. First, SSDs update data by writing a new copy to a clean slot, rather than overwriting old data. Second, SSDs support cleaning of entire blocks, while slots cannot be cleaned individually. Third, when cleaning a block, any valid data it stores must first be rewritten to another location, which adversely affects the SSD endurance and throughput. In this work, we address the SSD management problem, where the objective is to minimize the number of rewrites in SSDs. We approach the problem from a theoretical perspective, analyzing algorithms in a worst-case fashion. Motivated by recent advances in machine learning, we consider a learning-augmented setting where the algorithm has access to a predictive oracle, with performance guarantees expressed as a function of the error in the oracle's output. Our main contribution is Gladiator, a novel online algorithm that optimally leverages predictions to enhance the performance of SSDs. Compared to prior work, Gladiator requires no additional non-volatile memory and is less sensitive to prediction errors. We further demonstrate the effectiveness of Gladiator under reasonable assumptions on the input distribution, and extend it to an extremely efficient offline algorithm. Empirical results confirm its superiority over state-of-the-art practical solutions across diverse SSD workloads.
- Open Access
- 9 November 2024
- Published by Springer Nature in Journal of Network and Systems Management
- Vol. 33 (1) , 1-31
PASE: Pro-active Service Embedding in The Mobile Edge
Mobile edge computing offers ultra-low latency, high bandwidth, and high reliability. Thus, it can support a plethora of emerging services that can be placed in close proximity to the user. One of the fundamental problems in this context is maximizing the benefit from the placement of networked services, while meeting bandwidth and latency constraints. In this study, we propose an adaptive and predictive resource allocation strategy for virtual-network function placement comprising services at the mobile edge. Our study focuses on maximizing the service provider’s benefit under user mobility, i.e., uncertainty. This problem is NP-hard. Therefore, we propose a heuristic solution: we exploit local knowledge about the likely movements of users to speculatively allocate service functions. We allow the service functions to be allocated at different edge nodes, as long as latency and bandwidth constraints are met. We evaluate our proposal against a theoretically optimal algorithm as well as against recent previous work, using widely used simulation tools. Through an extensive simulation study, we demonstrate that under realistic scenarios, an adaptive and proactive strategy coupled with flexible placement can achieve close-to-optimal benefit.
- 9 November 2024
- Published by Springer Nature in Journal of Network and Systems Management
- Vol. 33 (1) , 1-31
Open AccessPASE: Pro-active Service Embedding in The Mobile Edge
Mobile edge computing offers ultra-low latency, high bandwidth, and high reliability. Thus, it can support a plethora of emerging services that can be placed in close proximity to the user. One of the fundamental problems in this context is maximizing the benefit from the placement of networked services, while meeting bandwidth and latency constraints. In this study, we propose an adaptive and predictive resource allocation strategy for virtual-network function placement comprising services at the mobile edge. Our study focuses on maximizing the service provider’s benefit under user mobility, i.e., uncertainty. This problem is NP-hard. Therefore, we propose a heuristic solution: we exploit local knowledge about the likely movements of users to speculatively allocate service functions. We allow the service functions to be allocated at different edge nodes, as long as latency and bandwidth constraints are met. We evaluate our proposal against a theoretically optimal algorithm as well as against recent previous work, using widely used simulation tools. Through an extensive simulation study, we demonstrate that under realistic scenarios, an adaptive and proactive strategy coupled with flexible placement can achieve close-to-optimal benefit.
- Open Access
- 6 February 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE BITS the Information Theory Magazine
- Vol. 3 (4) , 39-50
Data Storage at the Edge: Challenges and Opportunities
Edge systems are envisioned to provide storage and compute infrastructure at interoperating edge nodes located near the user. An edge node is orders-of-magnitude smaller than its datacenter counterpart in terms of power, network connectivity, and available compute resources. These differences have dramatic effects on the applicability of fundamental storage-related algorithms in edge settings. This article introduces the emerging edge architecture to the information theory community. We focus primarily on the applications and components of edge storage systems that are of interest to this community, on the challenges that stem from their limitations and constraints, and on the opportunities that arise from their special use cases.
- 6 February 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE BITS the Information Theory Magazine
- Vol. 3 (4) , 39-50
Open AccessData Storage at the Edge: Challenges and Opportunities
Edge systems are envisioned to provide storage and compute infrastructure at interoperating edge nodes located near the user. An edge node is orders-of-magnitude smaller than its datacenter counterpart in terms of power, network connectivity, and available compute resources. These differences have dramatic effects on the applicability of fundamental storage-related algorithms in edge settings. This article introduces the emerging edge architecture to the information theory community. We focus primarily on the applications and components of edge storage systems that are of interest to this community, on the challenges that stem from their limitations and constraints, and on the opportunities that arise from their special use cases.
- Open Access
- 15 November 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 18 (4) , 1-29
The what , The from , and The to : The Migration Games in Deduplicated Systems
Deduplication reduces the size of the data stored in large-scale storage systems by replacing duplicate data blocks with references to their unique copies. This creates dependencies between files that contain similar content and complicates the management of data in the system. In this article, we address the problem of data migration, in which files are remapped between different volumes as a result of system expansion or maintenance. The challenge of determining which files and blocks to migrate has been studied extensively for systems without deduplication. In the context of deduplicated storage, however, only simplified migration scenarios have been considered. In this article, we formulate the general migration problem for deduplicated systems as an optimization problem whose objective is to minimize the system’s size while ensuring that the storage load is evenly distributed between the system’s volumes and that the network traffic required for the migration does not exceed its allocation. We then present three algorithms for generating effective migration plans, each based on a different approach and representing a different trade-off between computation time and migration efficiency. Our greedy algorithm provides modest space savings but is appealing thanks to its exceptionally short runtime. Its results can be improved by using larger system representations. Our theoretically optimal algorithm formulates the migration problem as an integer linear programming (ILP) instance. Its migration plans consistently result in smaller and more balanced systems than those of the greedy approach, although its runtime is long and, as a result, the theoretical optimum is not always found. Our clustering algorithm enjoys the best of both worlds: its migration plans are comparable to those generated by the ILP-based algorithm, but its runtime is shorter, sometimes by an order of magnitude. It can be further accelerated at a modest cost in the quality of its results.
- 15 November 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 18 (4) , 1-29
Open AccessThe what , The from , and The to : The Migration Games in Deduplicated Systems
Deduplication reduces the size of the data stored in large-scale storage systems by replacing duplicate data blocks with references to their unique copies. This creates dependencies between files that contain similar content and complicates the management of data in the system. In this article, we address the problem of data migration, in which files are remapped between different volumes as a result of system expansion or maintenance. The challenge of determining which files and blocks to migrate has been studied extensively for systems without deduplication. In the context of deduplicated storage, however, only simplified migration scenarios have been considered. In this article, we formulate the general migration problem for deduplicated systems as an optimization problem whose objective is to minimize the system’s size while ensuring that the storage load is evenly distributed between the system’s volumes and that the network traffic required for the migration does not exceed its allocation. We then present three algorithms for generating effective migration plans, each based on a different approach and representing a different trade-off between computation time and migration efficiency. Our greedy algorithm provides modest space savings but is appealing thanks to its exceptionally short runtime. Its results can be improved by using larger system representations. Our theoretically optimal algorithm formulates the migration problem as an integer linear programming (ILP) instance. Its migration plans consistently result in smaller and more balanced systems than those of the greedy approach, although its runtime is long and, as a result, the theoretical optimum is not always found. Our clustering algorithm enjoys the best of both worlds: its migration plans are comparable to those generated by the ILP-based algorithm, but its runtime is shorter, sometimes by an order of magnitude. It can be further accelerated at a modest cost in the quality of its results.