[pt] OTIMIZAÇÃO ESTATÍSTICA DE BUSCAS PARA ESTRUTURAS HIERÁRQUICAS ESPACIAIS

Detalhes bibliográficos
Ano de defesa: 2008
Autor(a) principal: RENER PEREIRA DE CASTRO
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: MAXWELL
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11695&idi=1
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11695&idi=2
http://doi.org/10.17771/PUCRio.acad.11695
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.