GYGala Yadgar

Gala Yadgar

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Gala Yadgar has a total of 27 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Towards A System Model for DNA-based Storage

    by Stephanie Schustermann, Libi Kogan, Michael Factor, Dalit Naor, Gala Yadgar

    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

    Near-optimal PCM wear leveling under adversarial attacks

    by Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar

  • Open Access

    Physical vs. Logical Indexing with IDEA: Inverted Deduplication-Aware Index

    by Asaf Levi, Philip Shilane, Sarai Sheinvald, Gala Yadgar

    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

    Optimal SSD Management with Predictions

    by Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar

    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

    Optimal SSD Management with Predictions

    by Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar

  • Open Access

    Optimal SSD Management with Predictions

    by Tomer Lange, Joseph (Seffi) Naor, Gala Yadgar

    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

    PASE: Pro-active Service Embedding in The Mobile Edge

    by Oleg Kolosov, Gala Yadgar, David Breitgand, Dean H. Lorenz

    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

    Data Storage at the Edge: Challenges and Opportunities

    by Gala Yadgar, Oleg Kolosov

    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

    The what , The from , and The to : The Migration Games in Deduplicated Systems

    by Roei Kisous, Ariel Kolikant, Abhinav Duggal, Sarai Sheinvald, Gala Yadgar

    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.