Algoritmos de bulk-loading para o método de acesso métrico Onion-tree (2013)
- Authors:
- Autor USP: CAROSIA, ARTHUR EMANUEL DE OLIVEIRA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: BANCO DE DADOS DISTRIBUÍDOS; COMPUTAÇÃO EM NUVEM; SISTEMAS DE INFORMAÇÃO; ESPAÇOS MÉTRICOS
- Keywords: Bulk-loading; Bulk-loading; Consultas por similaridade; Método de acesso métrico; Metric access method; Onion-tree; Onion-tree; Similarity search
- Language: Português
- Abstract: 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 usandoa 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
- Imprenta:
- Publisher place: São Carlos
- Date published: 2013
- Data da defesa: 27.05.2013
-
ABNT
CAROSIA, Arthur Emanuel de Oliveira. Algoritmos de bulk-loading para o método de acesso métrico Onion-tree. 2013. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-10122013-164130/. Acesso em: 21 maio 2024. -
APA
Carosia, A. E. de O. (2013). Algoritmos de bulk-loading para o método de acesso métrico Onion-tree (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-10122013-164130/ -
NLM
Carosia AE de O. Algoritmos de bulk-loading para o método de acesso métrico Onion-tree [Internet]. 2013 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-10122013-164130/ -
Vancouver
Carosia AE de O. Algoritmos de bulk-loading para o método de acesso métrico Onion-tree [Internet]. 2013 ;[citado 2024 maio 21 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-10122013-164130/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
