Optimización del uso de memoria en la generación de Compressed Path Databases

Hong, Zihao (2021). Optimización del uso de memoria en la generación de Compressed Path Databases. Thesis (Master thesis), E.T.S. de Ingenieros Informáticos (UPM).

Description

Title: Optimización del uso de memoria en la generación de Compressed Path Databases
Author/s:
  • Hong, Zihao
Contributor/s:
  • Swoboda, Nik
Item Type: Thesis (Master thesis)
Masters title: Inteligencia Artificial
Date: July 2021
Subjects:
Freetext Keywords: Compressed Paths Databases, Inteligencia Artificial, Optimización en memoria, Dijkstra, Algoritmo de Floyd-Warshall, Run-Length Encoding, Artificial Intelligence, Memory Optimization, Floyd-Warshall algorithm
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

Actualmente, en un mundo cada vez más tecnológico, se generan más y más datos, de los cuales, si no se aprovechan, sólo ocupan en espacio sin proporcionar un beneficio. El algoritmo de Compressed Path Databases (CPD) se trata de una solución proporcionada para reducir el tiempo de ejecución de la planificación de rutas. La idea básica es en lugar de gastar tiempo en ejecución, extraer lo posible del proceso para moverlo a la etapa de preprocesamiento, de forma que al tener los datos precalculados de ante mano, se hace más rápido el tiempo de ejecución. Sin embargo, esta fase de preproceso genera una gran cantidad de datos de la planificación, y en consecuencia, espacio en almacenamiento, causando un problema cuando se haya un límite de este espacio. Para resolver este segundo problema, se plantea una serie de métodos para comprimir los datos obtenidos, sin tener impacto negativo en el coste de tiempo de ejecución. El enfoque de este TFM es proponer dos métodos nuevos para reducir el uso de memoria, uno de forma práctica y otro de forma teórica.---ABSTRACT---Nowadays, in a more and more technological world, data gets bigger and bigger and if it not used, it will just occupy space without providing a benefit. Compressed Path Databases (CPD) are a solution provided to reduce the computational cost of planning problem. The basic idea of this approach is instead of spending time during the execution of the path planning, extract all possible calculations and move them into the preprocessing period. Thus, we will have data prepared for execution, making the execution time much faster in the execution phase. However, this preprocessing phase generates a great amount of data, consequently, memory, which is needed for storage, causing a space issue if the memory is limited. To solve this second issue, a second part of the approach is to reduce the size of these data structures, while maintaining the same cost at execution time. The focus of this Master’s Thesis is to propose two optimizations to minorize the quantity of memory used by the preprocessed data by compressing it. One more practical and one more theoretical approach will be presented.

More information

Item ID: 68628
DC Identifier: https://oa.upm.es/68628/
OAI Identifier: oai:oa.upm.es:68628
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 24 Sep 2021 09:52
Last Modified: 24 Sep 2021 09:52
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM