Dissertação
Fractal Dimension and Space Filling Curve EVALUATED
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.
junho 1, 2015, 14:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia Informática (DEI)
Professor Auxiliar