Título
[pt] OTIMIZAÇÃO ESTATÍSTICA DE BUSCAS PARA ESTRUTURAS HIERÁRQUICAS ESPACIAIS
Título
[en] STATISTICAL OPTIMIZATION OF SPATIAL HIERARCHICAL STRUCTURES SEARCHS
Autor
[pt] RENER PEREIRA DE CASTRO
Vocabulário
[pt] MODELAGEM GEOMETRICA
Vocabulário
[pt] HASH TABLE
Vocabulário
[pt] 2D-TREE
Vocabulário
[pt] MATEMATICA DISCRETA
Vocabulário
[pt] GEOMETRIA COMPUTACIONAL
Vocabulário
[en] GEOMETRIC MODELING
Vocabulário
[en] HASH TABLE
Vocabulário
[en] DISCRETE MATHEMATICS
Vocabulário
[en] COMPUTATIONAL GEOMETRY
Resumo
[pt] Este trabalho surgiu da seguinte observação: os clássicos
algoritmos de busca em 2d-tree começam da raiz para acessar
dados armazenados nas folhas. Entretanto, como as folhas
são os nós mais distantes da raiz, por que começar as
buscas pela raiz? Com representações clássicas de 2d-trees,
não existe outra forma de acessar uma folha. Existem 2d-
trees, porém, que permitem acessar em tempo constante
qualquer nó, dado sua posição e seu nível. Para o algoritmo
de busca, a posição é conhecida, mas o nível
não. Para estimar o nível de um nó qualquer, um método de
otimização estatística do custo médio das buscas é
proposto. Como os piores custos de busca são obtidos quando
se começa da raiz, este método melhora ambos: o consumo de
memória pelo uso de 2d-trees que permitem acessar em
tempo constante qualquer nó, e o tempo de execução através
da otimização proposta.
Resumo
[en] This work emerged from the following observation: usual
search procedures for 2d-trees start from the root to
retrieve the data stored at the leaves. But since the
leaves are the farthest nodes to the root, why
start from the root? With usual 2d-trees representations,
there is no other way to access a leaf. However, there
exist 2d-trees which allow accessing any node in constant
time, given its position in space and its depth in the
2d-tree. Search procedures take the position as an input,
but the depth remains unknown. To estimate the depth of an
arbitrary node a statistical optimization of the average
cost for the search procedures is introduced. Since the
highest costs of these algorithms are obtained when
starting from the root, this method improves on both, the
memory footprint by the use of 2d-trees which allow
accessing any node in constant time, and execution
time through the proposed optimization.
Orientador(es)
GEOVAN TAVARES DOS SANTOS
Coorientador(es)
THOMAS LEWINER
Banca
GEOVAN TAVARES DOS SANTOS
Banca
SINESIO PESCO
Banca
HELIO CORTES VIEIRA LOPES
Banca
LUIZ HENRIQUE DE FIGUEIREDO
Banca
WALDEMAR CELES FILHO
Banca
JORGE STOLFI
Banca
THOMAS LEWINER
Banca
CLAUDIO ESPERANCA
Catalogação
2008-05-29
Apresentação
2008-03-07
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11695@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11695@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.11695
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT E SUMÁRIO PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF