Desenvolvimento de método de acesso para domínios métricos sensíveis à densidade local

• Processo: 01/11987-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2002
• Data de Término da vigência: 31 de maio de 2004
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Sistemas de Computação
• Pesquisador responsável: Caetano Traina Junior
• Beneficiário: Marcos Rodrigues Vieira
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Consultas por similaridade Indexação (biblioteconomia) Banco de dados Espaços métricos
• Palavra(s)-Chave do Pesquisador: Arvores De Indexacao | Consultas Por Similaridade

Resumo

O objetivo deste projeto é criar uma estrutura de indexação para domínios métricos, procurando obter melhor desempenho no processamento de consultas por similaridade do que as estruturas existentes, fazendo com que a profundidade da árvore seja maior em regiões do domínio de dados onde a densidade de objetos indexados seja maior. Domínios métricos têm a propriedade de ser possível calcular a distância entre pares de objetos. Normalmente procura-se manter as árvores de indexação balanceadas, pois isso ajuda a minimizar a altura da árvore, para diminuir o número de acessos a disco. No entanto, as consultas em árvores métricas têm custo diferente mesmo que elas sejam balanceadas, pois como a propriedade de distância não apresenta relação de ordem total, pode ser necessário avaliar-se mais do que um ramo de cada nó. Nesse caso, a minimização do número de ramos que não podem ser podados na busca pode ser mais importante do que manter a árvore balanceada. Assim, pretende-se usar a densidade local de objetos próximos entre si para controlar o "desbalanceamento" admissível de uma árvore, como um meio de reduzir o número de acessos necessários para responder uma consulta na árvore, procurando um equilíbrio entre número de acessos necessários para avaliar múltiplos ramos e número de acessos necessários para a busca em profundidade em cada ramo. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

ADRIANO S. ARANTES; MARCOS R. VIEIRA; CAETANO TRAINA JR.; AGMA J. M. TRAINA. Efficient algorithms to execute complex similarity queries in RDBMS. Journal of the Brazilian Computer Society, v. 9, n. 3, p. 5-24, 2004-04-00. (01/11987-3, 02/07318-1)

MARCOS R. VIEIRA; CAETANO TRAINA JR.; FABIO J. T. CHINO; AGMA J. M. TRAINA. DBM-Tree: trading height-balancing for performance in metric access methods. Journal of the Brazilian Computer Society, v. 11, n. 3, p. 37-51, 2006-04-00. (01/11987-3, 01/12536-5, 02/07318-1)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

VIEIRA, Marcos Rodrigues. DBM-tree: método de acesso métrico sensível à densidade local. 2004. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.