• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
10.11606/D.55.2007.tde-25042008-102856
Document
Author
Full name
Thiago Galbiatti Vespa
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2007
Supervisor
Committee
Traina Junior, Caetano (President)
Brayner, Angelo Roncalli Alencar
Ciferri, Cristina Dutra de Aguiar
Title in Portuguese
Operação de carga-rápida (bulk-loading) em métodos de acesso métricos
Keywords in Portuguese
Base de dados
Estruturas de indexação
Métodos de acesso métricos
Operação de carga-rápida
Abstract in Portuguese
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
Title in English
Bulk-loading Dynamic Metric Acess Methods
Keywords in English
Bulk-loading
Database
Indexing structures
Metric access methods
Abstract in English
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
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2008-05-07
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • Vespa, Thiago G., Traina Jr, Caetano, and Traina, Agma J. Efficient bulk-loading on dynamic metric access methods [doi:10.1016/j.is.2009.07.002]. Information Systems (Oxford) [online], 2010, vol. 35, p. 557-569.
  • Vespa, T. G., and Traina Jr., C.. Bulk-loading Dynamic Metric Access Methods. In 22 Simpósio Brasileiro de Bases de Dados (SBBD 07), João Pessoa, 2007. Anais do SBBD 2007.Porto Alegre : Sociedade Brasileira de Computação, 2007.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.