Bulk-loading Dynamic Metric Acess Methods

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 consultasThe 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 querie