$$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$
INFORMAÇÕES SOBRE DIREITOS AUTORAIS


As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.

A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.

A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.

A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital

Avançada


Estatísticas | Formato DC|



Título: COMPRESSÃO DE NÚMEROS NATURAIS, SEQUÊNCIA DE BITS E GRAFOS
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Autor(es): BRUNO TENORIO AVILA

Colaborador(es):  EDUARDO SANY LABER - Orientador
Número do Conteúdo: 19597
Catalogação:  01/06/2012 Idioma(s):  PORTUGUÊS - BRASIL

Tipo:  TEXTO Subtipo:  TESE
Natureza:  PUBLICAÇÃO ACADÊMICA
Nota:  Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19597@1
Referência [en]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=19597@2
Referência DOI:  https://doi.org/10.17771/PUCRio.acad.19597

Resumo:
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).

Descrição Arquivo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS  PDF
CAPÍTULO 1  PDF
CAPÍTULO 2  PDF
CAPÍTULO 3  PDF
CAPÍTULO 4  PDF
CAPÍTULO 5  PDF
REFERÊNCIAS BIBLIOGRÁFICAS, APÊNDICE  PDF
Agora você pode usar seu login do SAU no Maxwell!!
Fechar Janela



* Esqueceu a senha:
Senha SAU, clique aqui
Senha Maxwell, clique aqui