The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le problème d'allocation de disque examiné dans cet article consiste à trouver une méthode pour distribuer un Fichier produit cartésien binaire sur plusieurs disques pour maximiser les accès E/S aux disques parallèles pour une récupération partielle des correspondances. Ce problème est connu pour être NP-difficile et des approches heuristiques ont été appliquées pour obtenir des solutions sous-optimales. Récemment, des méthodes efficaces telles que les méthodes Binary Disk Modulo (BDM) et Error Correcting Code (ECC) ont été proposées, accompagnées de restrictions selon lesquelles le nombre de disques sur lesquels les fichiers sont stockés doit être une puissance de 2. Dans cet article, un nouveau Une méthode d'allocation de disque basée sur un algorithme génétique (DAGA) est proposée. Le DAGA n'impose aucune restriction sur le nombre de disques à appliquer et peut allouer les disques de manière adaptative en tenant compte des modèles d'accès aux données. En utilisant la théorie des schémas, il est prouvé que le DAGA peut réaliser une solution quasi optimale avec une forte probabilité. La comparaison de la qualité de la solution dérivée par le DAGA avec les méthodes General Disk Modulo (GDM), BDM et ECC à travers la simulation, montre que 1) le DAGA est supérieur à la méthode GDM dans tous les cas et 2) avec les restrictions étant placé sur le nombre de disques, le temps de réponse moyen du DAGA est toujours inférieur à celui de la méthode BDM et supérieur à celui de la méthode ECC en l'absence de biais de données et 3) lorsque le biais de données est pris en compte, le DAGA est plus performant supérieur ou égal aux méthodes BDM et ECC, même lorsque des restrictions sur le nombre de disques sont appliquées.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Dae-Young AHN, Kyu-Ho PARK, "Disk Allocation Methods Using Genetic Algorithm" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 1, pp. 291-300, January 1999, doi: .
Abstract: The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. Comparing the quality of solution derived by the DAGA with the General Disk Modulo (GDM), BDM, and ECC methods through the simulation, shows that 1) the DAGA is superior to the GDM method in all the cases and 2) with the restrictions being placed on the number of disks, the average response time of the DAGA is always less than that of the BDM method and greater than that of the ECC method in the absence of data skew and 3) when data skew is considered, the DAGA performs better than or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_1_291/_p
Copier
@ARTICLE{e82-d_1_291,
author={Dae-Young AHN, Kyu-Ho PARK, },
journal={IEICE TRANSACTIONS on Information},
title={Disk Allocation Methods Using Genetic Algorithm},
year={1999},
volume={E82-D},
number={1},
pages={291-300},
abstract={The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. Comparing the quality of solution derived by the DAGA with the General Disk Modulo (GDM), BDM, and ECC methods through the simulation, shows that 1) the DAGA is superior to the GDM method in all the cases and 2) with the restrictions being placed on the number of disks, the average response time of the DAGA is always less than that of the BDM method and greater than that of the ECC method in the absence of data skew and 3) when data skew is considered, the DAGA performs better than or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.},
keywords={},
doi={},
ISSN={},
month={January},}
Copier
TY - JOUR
TI - Disk Allocation Methods Using Genetic Algorithm
T2 - IEICE TRANSACTIONS on Information
SP - 291
EP - 300
AU - Dae-Young AHN
AU - Kyu-Ho PARK
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1999
AB - The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. Comparing the quality of solution derived by the DAGA with the General Disk Modulo (GDM), BDM, and ECC methods through the simulation, shows that 1) the DAGA is superior to the GDM method in all the cases and 2) with the restrictions being placed on the number of disks, the average response time of the DAGA is always less than that of the BDM method and greater than that of the ECC method in the absence of data skew and 3) when data skew is considered, the DAGA performs better than or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.
ER -