Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni (2003)
- Authors:
- Autor USP: SANTOS FILHO, ROBERTO FIGUEIRA - ICMC
- Unidade: 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:
- Publisher place: São Carlos
- Date published: 2003
- Data da defesa: 16.05.2003
-
ABNT
SANTOS FILHO, Roberto Figueira. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2003. . Acesso em: 06 fev. 2026. -
APA
Santos Filho, R. F. (2003). Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni (Tese (Doutorado). Universidade de São Paulo, São Carlos. -
NLM
Santos Filho RF. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003 ;[citado 2026 fev. 06 ] -
Vancouver
Santos Filho RF. Métodos de acesso métricos para suporte a consultas por similaridade: apresentação da Técnica Omni. 2003 ;[citado 2026 fev. 06 ]
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
