Compact data structures for large and complex datasets
![Thumbnail](/dspace/bitstream/handle/2183/19438/SilvaCoira_Fernando_TD_2017.pdf.jpg?sequence=5&isAllowed=y)
Use este enlace para citar
http://hdl.handle.net/2183/19438
Excepto si se señala otra cosa, la licencia del ítem se describe como Atribución-NoComercial-SinDerivadas 3.0 España
Colecciones
- Teses de doutoramento [2147]
- OpenAIRE [351]
Metadatos
Mostrar el registro completo del ítemTítulo
Compact data structures for large and complex datasetsAutor(es)
Directores
Ladra, SusanaParamá, Jose R.
Fecha
2017Resumen
[Abstract]
In this thesis, we study the problem of processing large and complex collections of
data, presenting new data structures and algorithms that allow us to efficiently store
and analyze them. We focus on three main domains: processing of multidimensional
data, representation of spatial information, and analysis of scientific data.
The common nexus is the use of compact data structures, which combine in a
unique data structure a compressed representation of the data and the structures to
access such data. The target is to be able to manage data directly in compressed
form, and in this way, to keep data always compressed, even in main memory. With
this, we obtain two benefits: we can manage larger datasets in main memory and
we take advantage of a better usage of the memory hierarchy.
In the first part, we propose a compact data structure for multidimensional
databases where the domains of each dimension are hierarchical. It allows efficient
queries of aggregate information at different levels of each dimension. A typical
application environment for our solution would be an OLAP system.
Second, we focus on the representation of spatial information, specifically on
raster data, which are commonly used in geographic information systems (GIS) to
represent spatial attributes (such as the altitude of a terrain, the average temperature,
etc.). The new method enables several typical spatial queries with better response
times than the state of the art, at the same time that saves space in both main
memory and disk. Besides, we also present a framework to run a spatial join between
raster and vector datasets, that uses the compact data structure previously presented
in this part of the thesis.
Finally, we present a solution for the computation of empirical moments from a
set of trajectories of a continuous time stochastic process observed in a given period
of time. The empirical autocovariance function is an example of such operations.
In this thesis, we propose a method that compresses sequences of floating numbers
representing Brownian motion trajectories, although it can be used in other similar
areas. In addition, we also introduce a new algorithm for the calculation of the
autocovariance that uses a single trajectory at a time, instead of loading the whole
dataset, reducing the memory consumption during the calculation process. [Resumo]
Nesta tese estudamos o problema de procesar grandes coleccións de datos,
presentando novas estruturas de datos compactas e algoritmos que nos permiten
almacenalas e analizalas de forma eficiente. Centrámonos en tres dominios principais:
procesamento de datos multidimensionais, representación de información espacial e
análise de datos científicos.
O nexo común é o uso de estruturas de datos compactas, que combinan nunha
única estrutura de datos unha representación comprimida dos datos e as estruturas
para acceder a tales datos. O obxectivo é poder manipular os datos directamente en
forma comprimida, e desta maneira, manter os datos sempre comprimidos, incluso na
memoria principal. Con esto obtemos dous beneficios: podemos xestionar conxuntos
de datos máis grandes na memoria principal e aproveitar un mellor uso da xerarquía
da memoria.
Na primera parte propoñemos unha estructura de datos compacta para bases de
datos multidimensionais onde os dominios de cada dimensión están xerarquizados.
Permítenos consultar eficientemente a información agregada (sumar valor máximo,
etc) a diferentes niveis de cada dimensión. Un entorno de aplicación típico para a
nosa solución sería un sistema OLAP.
En segundo lugar, centrámonos na representación de información espacial,
especificamente en datos ráster, que se utilizan comunmente en sistemas de
información xeográfica (SIX) para representar atributos espaciais (como a altitude
dun terreo, a temperatura media, etc.). O novo método permite realizar
eficientemente varias consultas espaciais típicas con tempos de resposta mellores que
o estado da arte, ao mesmo tempo que reduce o espazo utilizado tanto na memoria
principal como no disco. Ademais, tamén presentamos un marco de traballo para
realizar un join espacial entre conxuntos de datos vectoriais e ráster, que usa a
estructura de datos compacta previamente presentada nesta parte da tese.
Por último, presentamos unha solución para o cálculo de momentos empíricos
a partir dun conxunto de traxectorias dun proceso estocástico de tempo continuo
observadas nun período de tempo dado. A función de autocovarianza empírica
é un exemplo de tales operacións. Nesta tese propoñemos un método que
comprime secuencias de números flotantes que representan traxectorias de movemento Browniano, aínda que pode ser empregado noutras áreas similares. Ademais, tamén
introducimos un novo algoritmo para o cálculo da autocovarianza que emprega unha
única traxectoria á vez, en lugar de cargar todo o conxunto de datos, reducindo o
consumo de memoria durante o proceso de cálculo. [Resumen]
En esta tesis estudiamos el problema de procesar grandes colecciones de datos,
presentando nuevas estructuras de datos compactas y algoritmos que nos permiten
almacenarlas y analizarlas de forma eficiente. Nos centramos principalmente en tres
dominios: procesamiento de datos multidimensionales, representación de información
espacial y análisis de datos científicos.
El nexo común es el uso de estructuras de datos compactas, que combinan en
una única estructura de datos una representación comprimida de los datos y las
estructuras para acceder a dichos datos. El objetivo es poder manipular los datos
directamente en forma comprimida, y de esta manera, mantener los datos siempre
comprimidos, incluso en la memoria principal. Con esto obtenemos dos beneficios:
podemos gestionar conjuntos de datos más grandes en la memoria principal y
aprovechar un mejor uso de la jerarquía de la memoria.
En la primera parte proponemos una estructura de datos compacta para bases de
datos multidimensionales donde los dominios de cada dimensión están jerarquizados.
Nos permite consultar eficientemente la información agregada (suma, valor máximo,
etc.) a diferentes niveles de cada dimensión. Un entorno de aplicación típico para
nuestra solución sería un sistema OLAP.
En segundo lugar, nos centramos en la representación de la información espacial,
específicamente en datos ráster, que se utilizan comúnmente en sistemas de
información geográfica (SIG) para representar atributos espaciales (como la altitud
de un terreno, la temperatura media, etc.). El nuevo método permite realizar
eficientemente varias consultas espaciales típicas con tiempos de respuesta mejores
que el estado del arte, al mismo tiempo que reduce el espacio utilizado tanto en la
memoria principal como en el disco. Además, también presentamos un marco de
trabajo para realizar un join espacial entre conjuntos de datos vectoriales y ráster,
que usa la estructura de datos compacta previamente presentada en esta parte de la
tesis.
Por último, presentamos una solución para el cálculo de momentos empíricos a
partir de un conjunto de trayectorias de un proceso estocástico de tiempo continuo
observadas en un período de tiempo dado. La función de autocovariancia empírica
es un ejemplo de tales operaciones. En esta tesis proponemos un método que comprime secuencias de números flotantes que representan trayectorias de movimiento
Browniano, aunque puede ser utilizado en otras áreas similares. En esta parte,
también introducimos un nuevo algoritmo para el cálculo de la autocovariancia que
utiliza una única trayectoria a la vez, en lugar de cargar todo el conjunto de datos,
reduciendo el consumo de memoria durante el proceso de cálculo
Palabras clave
Almacenes de datos (Informática)-Gestión
OLAP
Tecnología
OLAP
Tecnología
Descripción
Programa Oficial de Doutoramento en Computación . 5009V01
Derechos
Atribución-NoComercial-SinDerivadas 3.0 España