STATISTICAL OPTIMIZATION OF SPATIAL HIERARCHICAL STRUCTURES SEARCHS / OTIMIZAÇÃO ESTATÍSTICA DE BUSCAS PARA ESTRUTURAS HIERÁRQUICAS ESPACIAIS

AUTOR(ES)
DATA DE PUBLICAÇÃO

2008

RESUMO

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.

ASSUNTO(S)

computational geometry matematica discreta 2d-tree modelagem geometrica hash table 2d-tree hash table geometric modeling geometria computacional discrete mathematics

ACESSO AO ARTIGO

Documentos Relacionados