Com o vislumbramento de aplicações que exigiam representações em espaços multidimensionais, surgiu a necessidade de desenvolvimento de métodos de acessos eficientes a estes dados representados em R^d. Dentre as aplicações precursoras dos métodos de acessos multidimensionais, podemos citar os sistemas de geoprocessamento, aplicativos 3D e simuladores. Posteriormente, os métodos de acessos multidimensionais também apresentaram-se como uma importante ferramenta no projeto de classificadores, principalmente classificadores pelos vizinhos mais próximos. Com isso, expandiu-se o espaço de representação, que antes se limitava no máximo a quatro dimensões, para dimensionalidades superiores a mil. Dentre os vários métodos de acesso multidimensional existentes, destaca-se uma classe de métodos baseados em árvores balanceadas com representação em R^d. Estes métodos constituem evoluções da árvore de acesso unidimenisonal B-tree e herdam várias características deste último. Neste trabalho, apresentamos alguns métodos de acessos dessa classe de forma a ilustrar a idéia central destes algoritmos e propomos e implementamos um novo método de acesso, a PCA-tree. A PCA-tree utiliza uma heurística de quebra de nós baseada na extração da componente principal das amostras a serem divididas. Um hiperplano que possui essa componente principal como seu vetor normal é definido como o elemento que divide o espaço associado ao nó. A partir dessa idéia básica geramos uma estrutura de dados e algoritmos que utilizam gerenciamento de memória secundária como a B-tree. Finalmente, comparamos o desempenho da PCA-tree com o desempenho de alguns outros métodos de acesso da classe citada, e apresentamos os prós e contras deste novo método de acesso através de análise de resultados práticos. / The advent of applications demanding the representation of objects in multi-dimensional spaces fostered the development of efficient multi-dimensional access methods. Among some early applications that required multi-dimensional access methods, we can cite geo-processing systems, 3D applications and simulators. Later on, multi-dimensional access methods also became important tools in the design of classifiers, mainly of those based on nearest neighbors technique. Consequently, the dimensionality of the spaces has increased, from earlier at most four to dimensionality larger than a thousand. Among several multi-dimensional access methods, the class of approaches based on balanced tree structures with data represented in Rd has received a lot of attention. These methods constitute evolues from the B-tree for unidimensional accesses, and inherit several of its characteristics. In this work, we present some of the access methods based on balanced trees in order to illustrate the central idea of these algorithms, and we propose and implement a new multi-dimensional access method, which we call PCA-tree. It uses an heuristic to break nodes based on the principal component of the sample to be divided. A hyperplane, whose normal is the principal component, is defined as the one that will split the space represented by the node. From this basic idea we define the data structure and the algorithms for the PCA-tree employing secondary memory management, as in B-trees. Finally, we compare the performance of the PCA-tree with the performance of other methods in the cited class, and present advantages and disadvantages of the proposed access method through analysis of experimental results.

Com o vislumbramento de aplicações que exigiam representações em espaços multidimensionais, surgiu a necessidade de desenvolvimento de métodos de acessos eficientes a estes dados representados em R^d. Dentre as aplicações precursoras dos métodos de acessos multidimensionais, podemos citar os sistemas de geoprocessamento, aplicativos 3D e simuladores. Posteriormente, os métodos de acessos multidimensionais também apresentaram-se como uma importante ferramenta no projeto de classificadores, principalmente classificadores pelos vizinhos mais próximos. Com isso, expandiu-se o espaço de representação, que antes se limitava no máximo a quatro dimensões, para dimensionalidades superiores a mil. Dentre os vários métodos de acesso multidimensional existentes, destaca-se uma classe de métodos baseados em árvores balanceadas com representação em R^d. Estes métodos constituem evoluções da árvore de acesso unidimenisonal B-tree e herdam várias características deste último. Neste trabalho, apresentamos alguns métodos de acessos dessa classe de forma a ilustrar a idéia central destes algoritmos e propomos e implementamos um novo método de acesso, a PCA-tree. A PCA-tree utiliza uma heurística de quebra de nós baseada na extração da componente principal das amostras a serem divididas. Um hiperplano que possui essa componente principal como seu vetor normal é definido como o elemento que divide o espaço associado ao nó. A partir dessa idéia básica geramos uma estrutura de dados e algoritmos que utilizam gerenciamento de memória secundária como a B-tree. Finalmente, comparamos o desempenho da PCA-tree com o desempenho de alguns outros métodos de acesso da classe citada, e apresentamos os prós e contras deste novo método de acesso através de análise de resultados práticos. / The advent of applications demanding the representation of objects in multi-dimensional spaces fostered the development of efficient multi-dimensional access methods. Among some early applications that required multi-dimensional access methods, we can cite geo-processing systems, 3D applications and simulators. Later on, multi-dimensional access methods also became important tools in the design of classifiers, mainly of those based on nearest neighbors technique. Consequently, the dimensionality of the spaces has increased, from earlier at most four to dimensionality larger than a thousand. Among several multi-dimensional access methods, the class of approaches based on balanced tree structures with data represented in Rd has received a lot of attention. These methods constitute evolues from the B-tree for unidimensional accesses, and inherit several of its characteristics. In this work, we present some of the access methods based on balanced trees in order to illustrate the central idea of these algorithms, and we propose and implement a new multi-dimensional access method, which we call PCA-tree. It uses an heuristic to break nodes based on the principal component of the sample to be divided. A hyperplane, whose normal is the principal component, is defined as the one that will split the space represented by the node. From this basic idea we define the data structure and the algorithms for the PCA-tree employing secondary memory management, as in B-trees. Finally, we compare the performance of the PCA-tree with the performance of other methods in the cited class, and present advantages and disadvantages of the proposed access method through analysis of experimental results.

Spatial database systems widely employ spatial indexing structures to speed up the processing of spatial queries. Many of the proposed spatial indices in the literature, such as the R-tree, assume magnetic disks (i.e., HDDs) as the underlying storage device. They are termed as disk-based spatial indices. On the other hand, several spatial database applications are increasingly using flash-based Solid State Drives (SSDs) and thus, designing spatial indices for these storage devices has gained increasing attention. This is due the fact that, compared to HDDs, SSDs offer smaller size, lighter weight, lower power consumption, better shock resistance, and faster reads and writes. Hence, specific indices for SSDs, termed flash-aware spatial indices, have been proposed in the literature to deal with the intrinsic characteristics of SSDs, such as the asymmetric costs of reads and writes. However, the research to date has not been able to establish a flash-aware spatial index that actually exploits all the benefits of SSDs. This PhD thesis advances on the literature as follows. We firstly define a methodology to create spatial datasets for experimental evaluations. We also propose FESTIval, a versatile framework that provides a common and unique environment to execute experimental evaluations. Such contributions served as a foundation to conduct performance analysis along this PhD work. By using this foundation, we analyze the performance behavior of spatial indices on different storage devices, such as HDDs and SSDs. Further, we discuss the applicability of employing flash simulators on the evaluation of spatial indices. The findings of these experiments contributed to the proposal of eFIND, a generic and efficient framework for flash-aware spatial indexing. eFIND is generic because it can port a wide range of disk-based spatial indices to SSDs. eFIND is also efficient because it is based on a set of design goals that exploits SSD performance. Performance tests showed that, compared to the state of the art, eFIND improved the construction of ported disk-based spatial indices and the execution of spatial queries. For porting the R-tree (i.e., the eFIND R-tree), eFIND showed performance reductions from 43% to 77% to build spatial indices, and from 4% to 23% to execute spatial queries. For porting the xBR+-tree (i.e., the eFIND xBR+-tree), eFIND showed reductions from 28% to 83% to build spatial indices and up to 35% in the spatial query processing. / Sistemas de banco de dados espaciais empregam estruturas de indexação espaciais para acelerar o processamento de consultas espaciais. Muitos dos índices espaciais propostos na literatura, como a R-tree, assumem que os dispositivos de armazenamentos são os discos magnéticos (i.e., HDDs) e são denominados índices espaciais baseados em disco. Por outro lado, várias aplicações de banco de dados espaciais estão cada vez mais usando Solid State Drives (SSDs) baseados em memória flash e, assim, projetar índices espaciais para esses dispositivos tem ganhado cada vez mais atenção. Isso se deve ao fato de que, em comparação com os HDDs, os SSDs oferecem menor tamanho, menor peso, menor consumo de energia, melhor resistência a choques além de leituras e escritas mais rápidas. Assim, índices espaciais para memória flash têm sido propostos na literatura para lidar com as características intrínsecas dos SSDs, como os custos assimétricos de leituras e escritas. No entanto, a pesquisa até o momento não conseguiu estabelecer um índice espacial que realmente explora todos os benefícios dos SSDs. Esta tese de doutorado avança na literatura da seguinte forma. Primeiramente, é definida uma metodologia para criar conjuntos de dados espaciais para avaliações experimentais. Também é proposto FESTIval, um arcabouço versátil que fornece um ambiente comum e único para executar avaliações experimentais. Tais contribuições serviram como base para conduzir análises de desempenho ao longo deste trabalho de doutorado. Usando essa base, o comportamento de desempenho de índices espaciais em diferentes dispositivos de armazenamento, como HDDs e SSDs, é analisado. Além disso, discutese a aplicabilidade de simuladores flash na avaliação experimental de índices espaciais. Os resultados desses experimentos contribuíram para a proposta de eFIND, uma estrutura genérica e eficiente para indexação espacial em memórias flash. eFIND é genérico porque pode portar uma ampla gama de índices espaciais baseados em disco para SSDs. eFIND também é eficiente porque é baseado em um conjunto de objetivos de projeto que exploram o desempenho do SSD. Os testes de desempenho mostraram que, em comparação com o estado da arte, eFIND melhorou a construção de índices espaciais portados e a execução de consultas espaciais. Para portar a R-tree (ou seja, a eFIND R-tree), eFIND mostrou melhorias de desempenho de 43% a 77% para construir índices espaciais e de 4% a 23% para executar consultas espaciais. Para portar a xBR+-tree (ou seja, a eFIND xBR+-tree), eFIND mostrou melhorias de 28% a 83% para construir índices espaciais e de até 35% no processamento de consultas espaciais.