Atualmente, a Onion-tree [Carélo et al., 2009] é o método de acesso métrico baseado em memória primária mais eficiente para pesquisa por similaridade disponível na literatura. Ela indexa dados complexos por meio da divisão do espaço métrico em regiões (ou seja, subespaços) disjuntas, usando para isso dois pivôs por nó. Para prover uma boa divisão do espaço métrico, a Onion-tree introduz as seguintes características principais: (i) procedimento de expansão, o qual inclui um método de particionamento que controla o número de subespaços disjuntos gerados em cada nó; (ii) técnica de substituição, a qual pode alterar os pivôs de um nó durante operações de inserção baseado em uma política de substituição que garante uma melhor divisão do espaço métrico, independente da ordem de inserção dos elementos; e (iii) algoritmos para a execução de consultas por abrangência e aos k-vizinhos mais próximos, de forma que esses tipos de consulta possam explorar eficientemente o método de particionamento da Onion-tree. Entretanto, a Onion-tree apenas oferece funcionalidades voltadas à inserção dos dados um-a-um em sua estrutura. Ela não oferece, portanto, uma operação de bulk-loading que construa o índice considerando todos os elementos do conjunto de dados de uma única vez. A principal vantagem dessa operação é analisar os dados antecipadamente para garantir melhor particionamento possível do espaço métrico. Com isto, a carga inicial de grandes volumes de dados pode ser melhor realizada usando a operação de bulk-loading. Este projeto de mestrado visa suprir a falta da operação de bulk-loading para a Onion-tree, por meio da proposta de algoritmos que exploram as características intrínsecas desse método de acesso métrico. No total, são propostos três algoritmos de bulk-loading, denominados GreedyBL, SampleBL e HeightBL, os quais utilizam respectivamente as seguintes abordagens: gulosa, amostragem e de estimativa da altura do índice. Testes experimentais realizados sobre conjuntos de dados com volume variando de 2.536 a 102.240 imagens e com dimensionalidade variando de 32 a 117 dimensões mostraram que os algoritmos propostos introduziram vantagens em relação à estrutura criada pelo algoritmo de inserção um-a-um da Onion-tree. Comparado com a inserção um-a-um, o tamanho do índice foi reduzido de 9% até 88%. Em consultas por abrangência, houve redução de 16% até 99% no número de cálculos de distância e de 9% a 99% no tempo gasto em relação à inserção. Em consultas aos k-vizinhos mais próximos, houve redução de 13% a 86% em número de cálculos de distância e de 9% até 63% no tempo gasto / The main-memory Onion-tree [Carélo et al., 2009] is the most efficient metric access method to date. It indexes complex data by dividing the metric space into several disjoint regions (i.e. subspaces) by using two pivots per node. To provide a good division of the metric space, the Onion-tree introduces the following characteristics: (i) expansion procedure, which provides a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) replacement technique, which can replace the pivots of a leaf node during insert operations based on a replacement policy that ensures a better division of the metric space, regardless of the insertion order of the elements; and (iii) algorithms for processing range and k-NN queries, so that these types of query can efficiently use the partitioning method of the Onion-tree. However, the Onion-tree only performs element-by-element insertions into its structure. Another important issue is the mass loading technique, called bulk-loading, which builds the index considering all elements of the dataset at once. This technique is very useful in the case of reconstructing the index or inserting a large number of elements simultaneously. Despite the importance of this technique, to the best of our knowledge, there are not in the literature bulk-loading algorithms for the Onion-tree. In this masters thesis, we fill this gap. We propose three algorithms for bulk-loading Onion-trees: the GreedyBL algorithm, the SampleBL algorithm and the HeightBL algorithm. These algorithms are based on the following approaches, respectively: greedy, sampling and estime height of the index. Performance tests with real-world data with different volumes (ranging from 2,536 to 102,240 images) and different dimensionalities (ranging from 32 to 117 dimensions) showed that the indices produced by the proposed algorithms are very compact. Compared with the element-by-element insertion, the size of the index reduced from 9% up to 88%. The proposed algorithms also provided a great improvement in query processing. They required from 16% up to 99% less distance calculations and were from 9% up to 99% faster than the element-by-element insertion to process range queries. Also, they required from 13% up to 86% less distance calculations and were from 9% up to 63% faster than the element-by-element insertion to process k-NN queries

Atualmente, a Onion-tree [Carélo et al., 2009] é o método de acesso métrico baseado em memória primária mais eficiente para pesquisa por similaridade disponível na literatura. Ela indexa dados complexos por meio da divisão do espaço métrico em regiões (ou seja, subespaços) disjuntas, usando para isso dois pivôs por nó. Para prover uma boa divisão do espaço métrico, a Onion-tree introduz as seguintes características principais: (i) procedimento de expansão, o qual inclui um método de particionamento que controla o número de subespaços disjuntos gerados em cada nó; (ii) técnica de substituição, a qual pode alterar os pivôs de um nó durante operações de inserção baseado em uma política de substituição que garante uma melhor divisão do espaço métrico, independente da ordem de inserção dos elementos; e (iii) algoritmos para a execução de consultas por abrangência e aos k-vizinhos mais próximos, de forma que esses tipos de consulta possam explorar eficientemente o método de particionamento da Onion-tree. Entretanto, a Onion-tree apenas oferece funcionalidades voltadas à inserção dos dados um-a-um em sua estrutura. Ela não oferece, portanto, uma operação de bulk-loading que construa o índice considerando todos os elementos do conjunto de dados de uma única vez. A principal vantagem dessa operação é analisar os dados antecipadamente para garantir melhor particionamento possível do espaço métrico. Com isto, a carga inicial de grandes volumes de dados pode ser melhor realizada usando a operação de bulk-loading. Este projeto de mestrado visa suprir a falta da operação de bulk-loading para a Onion-tree, por meio da proposta de algoritmos que exploram as características intrínsecas desse método de acesso métrico. No total, são propostos três algoritmos de bulk-loading, denominados GreedyBL, SampleBL e HeightBL, os quais utilizam respectivamente as seguintes abordagens: gulosa, amostragem e de estimativa da altura do índice. Testes experimentais realizados sobre conjuntos de dados com volume variando de 2.536 a 102.240 imagens e com dimensionalidade variando de 32 a 117 dimensões mostraram que os algoritmos propostos introduziram vantagens em relação à estrutura criada pelo algoritmo de inserção um-a-um da Onion-tree. Comparado com a inserção um-a-um, o tamanho do índice foi reduzido de 9% até 88%. Em consultas por abrangência, houve redução de 16% até 99% no número de cálculos de distância e de 9% a 99% no tempo gasto em relação à inserção. Em consultas aos k-vizinhos mais próximos, houve redução de 13% a 86% em número de cálculos de distância e de 9% até 63% no tempo gasto / The main-memory Onion-tree [Carélo et al., 2009] is the most efficient metric access method to date. It indexes complex data by dividing the metric space into several disjoint regions (i.e. subspaces) by using two pivots per node. To provide a good division of the metric space, the Onion-tree introduces the following characteristics: (i) expansion procedure, which provides a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) replacement technique, which can replace the pivots of a leaf node during insert operations based on a replacement policy that ensures a better division of the metric space, regardless of the insertion order of the elements; and (iii) algorithms for processing range and k-NN queries, so that these types of query can efficiently use the partitioning method of the Onion-tree. However, the Onion-tree only performs element-by-element insertions into its structure. Another important issue is the mass loading technique, called bulk-loading, which builds the index considering all elements of the dataset at once. This technique is very useful in the case of reconstructing the index or inserting a large number of elements simultaneously. Despite the importance of this technique, to the best of our knowledge, there are not in the literature bulk-loading algorithms for the Onion-tree. In this masters thesis, we fill this gap. We propose three algorithms for bulk-loading Onion-trees: the GreedyBL algorithm, the SampleBL algorithm and the HeightBL algorithm. These algorithms are based on the following approaches, respectively: greedy, sampling and estime height of the index. Performance tests with real-world data with different volumes (ranging from 2,536 to 102,240 images) and different dimensionalities (ranging from 32 to 117 dimensions) showed that the indices produced by the proposed algorithms are very compact. Compared with the element-by-element insertion, the size of the index reduced from 9% up to 88%. The proposed algorithms also provided a great improvement in query processing. They required from 16% up to 99% less distance calculations and were from 9% up to 99% faster than the element-by-element insertion to process range queries. Also, they required from 13% up to 86% less distance calculations and were from 9% up to 63% faster than the element-by-element insertion to process k-NN queries

O grau de similaridade entre elementos de dados é o fator primordial para a recuperação de informações em Sistemas Gerenciadores de Bases de Dados que manipulam dados complexos, como seqüências genéticas, séries temporais e dados multimídia (imagens, áudios, vídeos, textos longos). Para responder a essas consultas em um tempo reduzido, faz-se necessário utilizar métodos que usam métricas para avaliar a similaridade entre os elementos. Esses métodos são conhecidos como Métodos de Acesso Métricos. Dentre os mais conhecidos na literatura estão a M-tree e a Slim-tree. Existem duas maneiras de executar as operações de construção de índices em qualquer método de acesso: inserindo elemento a elemento ou usando a operação de carga-rápida (bulk-loading). O primeiro tipo de construção é comum e necessário para todo tipo de método de indexação dinâmico. Já as operações de carga-rápida são utilizadas para conjuntos de dados maiores, como por exemplo, na recuperação de backups em bases de dados ou na criação posterior de índices. Nessas situações, a inserção individual tende a ser mais demorada. Realizar uma carga-rápida possibilita a construção de índices com melhor eficiência e em menor tempo, pois há a disponibilidade de todos os dados no instante da criação da estrutura de índices, possibilitando explorar as propriedades do conjunto como um todo. Os Sistemas Gerenciadores de Base de Dados oferecem operações de carga-rápida dos dados nos métodos tradicionais, as quais devem ser supridas também nos Métodos de Acesso Métricos. Neste trabalho, são apresentadas três abordagens, uma técnica para carga-rápida dos dados em Métodos de Acesso Métricos e foi desenvolvido um algoritmo baseado nessa técnica para construir uma Slim-tree. Este é o primeiro algoritmo de carga-rápida baseada em amostragem que sempre produz uma Slim-tree válida, portanto é o primeiro descrito na literatura que pode ser incluído em um Sistema Gerenciador de Base de Dados. Os experimentos descritos neste trabalho mostram que o algoritmo proposto mantém bom agrupamento dos dados e supera o desempenho dos métodos de inserção seqüencial levando em conta tanto o desempenho de construção quanto à eficiência para realizar consultas / The similarity degree between data elements is the primordial factor for information retrieval in databases that handle complex data, such as genetic sequences, time series and multimedia objects (long images, audio, videos, texts). To answer these queries in a reduced time, it is necessary methods that use metrics to evaluate the similarity between elements. These methods are known as Metric Access Methods. The most known Metric Access Methods in the literature are the M-tree and the Slim-tree. There are two ways to build index in any access method: inserting element one by one or using the bulk-load operation. The first build type is very common and required for all kinds of dynamic access methods. The bulk-load operations are used for bigger datasets, as for example, in the recovery of backups and re-creation of database indexes. In these situations, the individual insertion takes much time. The bulk-load operation makes it possible to construct indexes more efficiently and faster, because it has the availability of the whole data when the index structure are created, and thus, it is possible to explore the properties of the whole set. Database Management Systems offer bulk-load operations for the traditional methods, so it is important that they can be also supplied for Metric Access Methods. This work presents three bulk-loading approaches and it proposes a technique to bulk-load data into Metric Access Methods. An algorithm based on this technique was developed to construct a Slim-tree. This is the first bulk-load algorithm based on sampling that always produces a valid Slim-tree, therefore is the first one described in literature that can be enclosed in a Database Management System. The experiments show that this algorithm keeps good clustering of data and in such a way that it surpasses the performance of sequential insertion, taking into account the construction performance and the efficiency to perform queries

O grau de similaridade entre elementos de dados é o fator primordial para a recuperação de informações em Sistemas Gerenciadores de Bases de Dados que manipulam dados complexos, como seqüências genéticas, séries temporais e dados multimídia (imagens, áudios, vídeos, textos longos). Para responder a essas consultas em um tempo reduzido, faz-se necessário utilizar métodos que usam métricas para avaliar a similaridade entre os elementos. Esses métodos são conhecidos como Métodos de Acesso Métricos. Dentre os mais conhecidos na literatura estão a M-tree e a Slim-tree. Existem duas maneiras de executar as operações de construção de índices em qualquer método de acesso: inserindo elemento a elemento ou usando a operação de carga-rápida (bulk-loading). O primeiro tipo de construção é comum e necessário para todo tipo de método de indexação dinâmico. Já as operações de carga-rápida são utilizadas para conjuntos de dados maiores, como por exemplo, na recuperação de backups em bases de dados ou na criação posterior de índices. Nessas situações, a inserção individual tende a ser mais demorada. Realizar uma carga-rápida possibilita a construção de índices com melhor eficiência e em menor tempo, pois há a disponibilidade de todos os dados no instante da criação da estrutura de índices, possibilitando explorar as propriedades do conjunto como um todo. Os Sistemas Gerenciadores de Base de Dados oferecem operações de carga-rápida dos dados nos métodos tradicionais, as quais devem ser supridas também nos Métodos de Acesso Métricos. Neste trabalho, são apresentadas três abordagens, uma técnica para carga-rápida dos dados em Métodos de Acesso Métricos e foi desenvolvido um algoritmo baseado nessa técnica para construir uma Slim-tree. Este é o primeiro algoritmo de carga-rápida baseada em amostragem que sempre produz uma Slim-tree válida, portanto é o primeiro descrito na literatura que pode ser incluído em um Sistema Gerenciador de Base de Dados. Os experimentos descritos neste trabalho mostram que o algoritmo proposto mantém bom agrupamento dos dados e supera o desempenho dos métodos de inserção seqüencial levando em conta tanto o desempenho de construção quanto à eficiência para realizar consultas / The similarity degree between data elements is the primordial factor for information retrieval in databases that handle complex data, such as genetic sequences, time series and multimedia objects (long images, audio, videos, texts). To answer these queries in a reduced time, it is necessary methods that use metrics to evaluate the similarity between elements. These methods are known as Metric Access Methods. The most known Metric Access Methods in the literature are the M-tree and the Slim-tree. There are two ways to build index in any access method: inserting element one by one or using the bulk-load operation. The first build type is very common and required for all kinds of dynamic access methods. The bulk-load operations are used for bigger datasets, as for example, in the recovery of backups and re-creation of database indexes. In these situations, the individual insertion takes much time. The bulk-load operation makes it possible to construct indexes more efficiently and faster, because it has the availability of the whole data when the index structure are created, and thus, it is possible to explore the properties of the whole set. Database Management Systems offer bulk-load operations for the traditional methods, so it is important that they can be also supplied for Metric Access Methods. This work presents three bulk-loading approaches and it proposes a technique to bulk-load data into Metric Access Methods. An algorithm based on this technique was developed to construct a Slim-tree. This is the first bulk-load algorithm based on sampling that always produces a valid Slim-tree, therefore is the first one described in literature that can be enclosed in a Database Management System. The experiments show that this algorithm keeps good clustering of data and in such a way that it surpasses the performance of sequential insertion, taking into account the construction performance and the efficiency to perform queries