Ver registro no DEDALUS
Exportar registro bibliográfico

Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni (2003)

  • Authors:
  • USP affiliated authors: SANTOS FILHO, ROBERTO FIGUEIRA - ICMC
  • USP Schools: ICMC
  • Sigla do Departamento: SCE
  • Subjects: BANCO DE DADOS (GERENCIAMENTO); ESPAÇOS MÉTRICOS; ESPAÇOS VETORIAIS
  • Language: Português
  • Abstract: A necessidade de representar o conhecimento humano em meio computacional tem provocado o surgimento de novos tipos de dados que, e, geral, têm sua estrutura interna composta por vários subtipos e requerem qrandes quantidades de bytes de memória. Esses novos tipos são conhecidos como tipos de dados complexos. O Grupo de Base de Dados e Imagens do ICMC/USP vem pesquisando técnicas para a manipulação de tipos de dados complexos em Sistema de Gerenciamento de Base de Dados (SGBD), visando a recuperação e a indexação de dados em ambientes com alto grau de dinamismo. Objetos de tipos complexos são pesquisados pelas consultas por similaridade, destinadas à procura dos similares a um objeto oferecido como referência. Avalia-se a similaridade através de funções de dissimilaridade (distância) métricas. Consultas por similaridade envolvendo grandes conjuntos de objetos são agilizadas através de Métodos de Acesso Métricos (MAM) dinâmicos capazes de gerenciar armazenamento secundário. A complexidade das métricas usadas no processo de avaliação de similaridade e o tamanho dos objetos afetam diretamente o desempenho destes métodos e, conseqüentemente, o das consultas. Este trabalho introduz a Técnica Omni, que usa representativos globais (pontos focais) como objetos de referência para todo o conjunto, equivalendo a fazer a imersão do espaço métrico original M=(S, d) em um espaço vetorial V=('R POT.E', 'L IND.INFINITO'). A técnica Omni pode ser combinada commétodos de acesso existentes para gerar novos e mais eficientes MAMs. As consultas são feitas em duas etapas: filtragem e refinamento. Durante a filtragem, a região de busca (definida pelo objeto e pelo raio de busca) é, também, mapeada para o espaço V e usada para comparar e filtrar os objetos mapeados. Durante o refinamento, os objetos não filtrados são comparados diretamente com a região de busca original, descartando os alarmes falsos. Mostra-se que o número adequado de focos está relacionado com a dimensão intrínseca do conjunto indexado. O uso de múltiplos focos (representativos) reduz o número de comparações entre objetos durante as consultas. Em complemento à técnica, são apresentados: a) um algorítmo para obter os focos; b) a prova formal de que a técnica não gera descartes falsos; c) como integrar métodos de acesso existentes com a técnica Omni e os respectivos algorítmos para os dois mais comuns de consultas por similaridade (por abrangência e aos k-vizinhos mais próximos); e d) três membros da Família Omni: a Omni-Sequential, a OmniB-Forest e a OmniR-Tree. Testes experimentais com conjuntos de dados sintéticos e reais mostram que os métodos da Família Omni superam os demais métodos. Em média, são 15 vezes mais rápidos e apresentam uma redução de até 17 vezes no número de comparações entre objetos e de até 10 vezes no número de acessos a disco, quando comparados aos outros métodos tradicionais. Os resultados (tempo total e números de acessos a disco ede comparações entre objetos) indicam que os métodos Omni não degradam com a inserção de novos objetos (são escaláveis). Diante de sua simplicidade e das melhorias comentadas, a Técnica Omni oferece condições de ser facilmente implementada sobre outros métodos de acesso métricos existentes, como por exemplo, sobre a Slim-Tree, gerando a DF-Tree (Distance Fields Tree); e em SGBDs comerciais, estendendo os recursos oferecidos para dar suporte a consultas por similaridade em dados complexos
  • Imprenta:
  • Data da defesa: 16.05.2003

  • Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    ICMC30300031177T S237ma e.1
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SANTOS FILHO, Roberto Figueira; TRAINA, Agma Juci Machado. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003.Universidade de São Paulo, São Carlos, 2003.
    • APA

      Santos Filho, R. F., & Traina, A. J. M. (2003). Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. Universidade de São Paulo, São Carlos.
    • NLM

      Santos Filho RF, Traina AJM. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003 ;
    • Vancouver

      Santos Filho RF, Traina AJM. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: