XINFORMAÇÕ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.
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
Título: COMPRESSÃO DE NÚMEROS NATURAIS, SEQUÊNCIA DE BITS E GRAFOS Autor: BRUNO TENORIO AVILA
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
EDUARDO SANY LABER - ORIENTADOR
Nº do Conteudo: 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:
Título: COMPRESSÃO DE NÚMEROS NATURAIS, SEQUÊNCIA DE BITS E GRAFOS Autor: BRUNO TENORIO AVILA
Nº do Conteudo: 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 | |
CAPÍTULO 1 | |
CAPÍTULO 2 | |
CAPÍTULO 3 | |
CAPÍTULO 4 | |
CAPÍTULO 5 | |
REFERÊNCIAS BIBLIOGRÁFICAS, APÊNDICE |