[pt] OTIMIZAÇÃO ESTATÍSTICA DE BUSCAS PARA ESTRUTURAS HIERÁRQUICAS ESPACIAIS
Ano de defesa: | 2008 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
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. |