[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:11695 |
| Date | 29 May 2008 |
| Creators | RENER PEREIRA DE CASTRO |
| Contributors | GEOVAN TAVARES DOS SANTOS, GEOVAN TAVARES DOS SANTOS |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0023 seconds