Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/38953
Type: | Dissertação |
Title: | A machine learning approach for data structure selection |
Other Titles: | Uma abordagem baseada em aprendizado de máquina para seleção de estrutura de dados |
Authors: | Tarsila Bessa Nogueira Assunção |
First Advisor: | Gisele Lobo Pappa |
First Co-advisor: | Fernando Magno Quintão Pereira |
First Referee: | Diego Elias Damasceno Costa |
Second Referee: | Adriano César Machado Pereira |
Abstract: | Accurate data structure selection can vastly improve a program's performance and memory usage. However, it is hard to understand the behavior of a data structure in an application before running it, making choosing the best data structure to use in a computer program a complex task. This dissertation presents a framework capable of automatically selecting data structures for a given program and input. The framework consists of four components: a program data extractor, which collects information on the behavior of the data structures used in the input program; a feature constructor that transforms the extracted data into machine learning features; two different offline machine learning models which automatically select data structures to be used with the given application/input combination; and a program reconstructor that creates a new version of the input program using the data structures selected by the models. The framework is evaluated with synthetic and real world applications and is capable of reaching the same level of accuracy as the original developers when selecting the data structures for the applications. |
Abstract: | Uma seleção de estrutura de dados adequada pode melhorar bastante o desempenho e uso de memória de um programa. Porém, é difícil entender o comportamento de uma estrutura de dados em uma aplicação antes de executá-la, o que torna complexa a tarefa de escolher a melhor estrutura de dados para o uso em um programa de computador. Esta dissertação apresenta um framework capaz de selecionar, de maneira automática, estruturas de dados para um programa e sua entrada. O framework é formado por quatro componentes: um componente para extração de dados, que coleta informação sobre o comportamento das estruturas de dados usadas no programa dado como entrada; um construtor de features, que transforma as informações extraídas em features para modelos de aprendizado de máquina; dois modelos de aprendizado de máquina que selecionam automaticamente estruturas de dados para serem usadas com o conjunto de programa e entrada; e um reconstrutor de programas que cria uma nova versão da aplicação dada como entrada usando as estruturas de dados selecionadas pelos modelos. O framework é avaliado em aplicações sintéticas e reais e é capaz de atingir a mesma acurácia que os desenvolvedores originais ao escolher estruturas de dados para as aplicações. |
Subject: | Computação – Teses Aprendizado de máquina – Teses Estrutura de dados – Seleção – Teses Redes neurais (Computação) – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-nc-nd/3.0/pt/ |
URI: | http://hdl.handle.net/1843/38953 |
Issue Date: | 14-Dec-2020 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
a_machine_learning_approach_for_data_structure_selection.pdf | 3.49 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License