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
O problema de alocação de disco examinado neste artigo é encontrar um método para distribuir um Arquivo de produto cartesiano binário em vários discos para maximizar os acessos de E/S de disco paralelo para recuperação de correspondência parcial. Este problema é conhecido por ser NP-difícil e abordagens heurísticas têm sido aplicadas para obter soluções subótimas. Recentemente, métodos eficientes como Módulo de Disco Binário (BDM) e métodos de Código de Correção de Erros (ECC) foram propostos juntamente com as restrições de que o número de discos nos quais os arquivos são armazenados deve ser uma potência de 2. Neste artigo, um novo O método de alocação de disco baseado em algoritmo genético (DAGA) é proposto. O DAGA não impõe restrições ao número de discos a serem aplicados e pode alocar os discos de forma adaptativa, levando em consideração os padrões de acesso aos dados. Usando a teoria do esquema, está provado que o DAGA pode realizar uma solução quase ótima com alta probabilidade. Comparando a qualidade da solução derivada do DAGA com os métodos General Disk Modulo (GDM), BDM e ECC através da simulação, mostra que 1) o DAGA é superior ao método GDM em todos os casos e 2) com as restrições sendo colocado no número de discos, o tempo médio de resposta do DAGA é sempre menor que o do método BDM e maior que o do método ECC na ausência de distorção de dados e 3) quando a distorção de dados é considerada, o DAGA tem melhor desempenho maior ou igual aos métodos BDM e ECC, mesmo quando restrições no número de discos são impostas.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -