[pt] Esta tese aborda os problemas de compressão para os seguintes tipos
de dados: sequência de bits e grafos web. Para o problema de compressão de
sequência de bits, demonstramos a relação entre algoritmos de intercalação
e codificadores de fonte binária. Em seguida, mostramos que os algoritmos
de intercalação binária (Hwang e Lin, 1972), recursivo (Dudzinski, 1981)
e probabilístico (Vega, 1993), geram respectivamente os codificadores de
entropia baseado em comprimentos de carreiras codificados com o código
de Rice, o codificador de intercalação binária (Moffat, 2000) e o codificador
de Rice aleatório, na qual é um novo variante do código de Rice.
Para o problema de compressão de grafos web, propomos uma nova representa
ção compacta para grafos web, intitulada árvore-w, construída especificamente
para memória externa (disco), sendo a primeira nesse gênero.
Propomos também um novo tipo de layout projetado especificamente para
grafos web, intitulado layout escalado. Além disso, mostramos como construir
um layout cache-oblivious para explorar a hierarquia de memórias,
sendo a primeira desse tipo. Apresentamos vários tipos de consultas que
podem ser executadas e é a primeira representação a suportar execução de
consulta de leitura aleatória em lote e a otimização de consultas avançadas,
inclusive em memória principal. Por fim, executamos uma série de experimentos
que mostra que a árvore-w apresenta taxas de compressão e de
tempo de execução competitivas com outras representações compactas em
memória principal. Assim, demonstramos empiricamente a viabilidade de
uma representação compacta para memória externa na prática, contrariando
a afirmação de vários pesquisadores (Suel, 2001) (Buehrer, 2008). / [en] This thesis addresses the problems of compression for the following
data types: numbers, sequence of bits and webgraphs. For the problem of
compression of a sequence of bits, we demonstrate the relationship between
merge algorithms and binary source coders. Then, we show that the algorithms
binary merge (Hwang and Lin, 1972), recursive merge (Dudzinski,
1981) and probabilistic merge (Vega, 1993), generate respectively an entropy
coder based runlengths encoded with the Rice code, the interpolative binary
coder (Moffat, 2000) and the random Rice coder, which is a new variant of
the Rice code. For the problem of webgraph compression, we propose a new
compact representation for webgraphs, entitled w-tree, built specifically for
external memory (disk), being the first one in this genre. We also propose a
new type of layout designed specifically for webgraphs, entitled scaled layout.
In addition, we show how to build a cache-oblivious layout to explore the
hierarchy of memories, being the first of its kind. We offer several types of
queries that can be performed and it is the first representation to support
batched random read query execution and advanced query optimization,
including in main memory. Finally, we performed a series of experiments
showing that the w-tree provides compression rates and running times competitive
with other compact representations for main memory. Therefore,
we demonstrate empirically the feasibility of a compact representation for
external memory in practice, contrary to the assertion of several researchers
(Suel, 2001) (Buehrer, 2008).
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:19597 |
| Date | 01 June 2012 |
| Creators | BRUNO TENORIO AVILA |
| Contributors | EDUARDO SANY LABER |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0015 seconds