Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos (2010)
- Authors:
- Autor USP: OLIVEIRA, WILLIAN DENER DE - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: ESPAÇOS MÉTRICOS; PROCESSAMENTO DE IMAGENS (RECUPERAÇÃO); BANCO DE DADOS; MINERAÇÃO DE DADOS; ALGORITMOS PARA IMAGENS
- Language: Português
- Abstract: A complexidade dos dados armazenados em grandes bases de dados aumenta cada vez mais, criando a necessidade de novas operações de consulta. Uma classe de operações que tem apresentado interesse crescente são as chamadas Consultas por Similaridade, sendo as mais conhecidas as consultas por Abrangência ('R IND. q') e por k-Vizinhos mais Proximos (kNN), sendo que esta última obtem quais são os k elementos armazenados mais similares a um dado elemento de referência. Outra consulta que é interessante tanto para consultas diretas quanto como parte de operações de análises mais complexas e a operação de consulta aos k-Vizinhos mais Próximos Reversos (RkNN). Seu objetivo e obter todos os elementos armazenados que têm um dado elemento de referência como um dos seus k elementos mais similares. Devido a complexidade de execução da operação de RkNN, a grande maioria das soluções existentes restringem-se a dados representados em espaços multidimensionais euclidianos (nos quais estão denidas também operações cardinais e topológicas, além de se considerar a similaridade como sendo a distância Euclidiana entre dois elementos), ou então obtém apenas respostas aproximadas, sujeitas a existência de falsos negativos. Várias aplicações de análise de dados científicos, médicos, de engenharia, financeiros, etc. requerem soluções eficientes para o problema da operação de RkNN sobre dados representados em espaços métricos, onde os elementos não podem ser considerados estar em um espaçonem Euclidiano nem multidimensional. Num espaço métrico, além dos próprios elementos armazenados existe apenas uma função de comparação métrica entre pares de objetos. Neste trabalho, são propostas novas podas de espaço de busca e o algoritmo RkNN-MG que utiliza essas novas podas para solucionar o problema de consultas RkNN exatas em espaços métricos sem limitações. Toda a proposta supõe que o conjunto de dados etá em um espaço métrico imerso isometricamente em espaço euclidiano e utiliza propriedades da geometria métrica válida neste espaço para realizar podas eficientes por lei dos cossenos combinada com as podas tradicionais por desigualdade triangular. Os experimentos demonstram comparativamente que as novas podas são mais eficientes que as tradicionais podas por desigualdade triangular, tendo desempenhos equivalente quando comparadas em conjuntos de alta dimensionalidade ou com dimensão fractal alta. Assim, os resultados confirmam as novas podas propostas como soluções alternativas eficientes para o problema de consultas RkNN
- Imprenta:
- Publisher place: São Carlos
- Date published: 2010
- Data da defesa: 19.03.2010
-
ABNT
OLIVEIRA, Willian Dener de. Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos. 2010. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2010. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-163917/. Acesso em: 01 mar. 2026. -
APA
Oliveira, W. D. de. (2010). Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-163917/ -
NLM
Oliveira WD de. Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos [Internet]. 2010 ;[citado 2026 mar. 01 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-163917/ -
Vancouver
Oliveira WD de. Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos [Internet]. 2010 ;[citado 2026 mar. 01 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-163917/ - Similarity grouping by influence: exploring result diversification in similarity group-by operator
- Efficiently indexing multiple repositories of medical image databases
- Embedding k-nearest neighbor queries into relational database management systems
- Involving users in the gestural language definition process for the NInA framework
- A 'wider' concept for similarity joins
- Parameter-free and domain-independent similarity search with diversity
- Combine-and-conquer: improving the diversity in similarity search through influence sampling
- Diversity in similarity joins
- The NinA framework: using gesture to improve interaction and collaboration in geographical information systems
- Self similarity wide-joins for near-duplicate image detection
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
