Dissertação

{en_GB=Fractal Dimension and Space Filling Curve} {} EVALUATED

{pt=Curvas preenchedoras de espaço são fractais gerados por computador que podem ser usadas para indexar espaços de baixas dimensões. Existem estudos anteriores que as usam como método de acesso nestes cenários, contudo são muito conservadores usando-as apenas em espaços até quatro dimensões. Adicionalmente, os métodos alternativos tendem a apresentar um desempenho pior do que uma pesquisa linear quando os espaços ultrapassam as dez dimensões. Deste modo, no contexto da minha tese, estudo as curvas preenchedoras de espaço e as suas propriedades assim como os desafios apresentados pelos dados multidimensionais. Eu proponho o uso destas, especificamente da curva de Hilbert, como um método de acesso para indexar pontos multidimensionais até trinta dimensões. Eu começo por mapear os pontos para a curva de Hilbert gerando os seus h-values. Em seguida, desenvolvo três heuristicas para procurar vizinhos aproximadamente mais próximos de um dado ponto de pesquisa com o objectivo de testar o desempenho da curva. Duas heurísticas usam a curva com método de acesso direto e a restante usa a curva como chave secundária combinada com uma variante da B-tree. Estas resultam de um processo iterativo que basicamente consiste no planeamento, concepção e teste da heurística. De acordo com os resultados do teste, a heurística é alterada ou é criada uma nova. Os resultados experimentais com as três heurísticas provam que a curva de Hilbert pode ser usada como método de acesso e que esta consegue funcionar pelo menos em espaços até trinta e seis dimensões., en=Space-filling curves are computer generated fractals that can be used to index low-dimensional spaces. There are previous studies using them as an access method in these scenarios, although they are very conservative only applying them up to four-dimensional spaces. Additionally, the alternative access methods tend to present worse performance than a linear search when the spaces surpass the ten dimensions. Therefore, in the context of my thesis, I study the space-filling curves and their properties as well as challenges presented by multidimensional data. I propose their use, specifically the Hilbert curve, as an access method for indexing multidimensional points up to thirty dimensions. I start by mapping the points to the Hilbert curve generating their h-values. Then, I develop three heuristics to search for approximate nearest neighbors of a given query point with the aim of testing the performance of the curve. Two of the heuristics use the curve as a direct access method and the other uses the curve as a secondary key retrieval combined with a B-tree variant. These result from an iterative process that basically consists of planning, conceiving and testing the heuristic. According to the test results, the heuristic is adjusted or a new one is created. Experimental results with the three heuristics prove that the Hilbert curve can be used as an access method, and that it can operate at least in spaces up to thirty-six dimensions.}
{pt=Fractais, Curva de Hilbert Preenchedora de Espaço, Indexação de Baixas Dimensões, Vizinho Aproximadamente Mais Próximo, en=Fractals, Hilbert Space-Filling Curve, Low-Dimensional Indexing, Approximate Nearest Neighbor}

junho 1, 2015, 14:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Andreas Miroslaus Wichert

Departamento de Engenharia Informática (DEI)

Professor Auxiliar