Improving the efficiency of k-medoids algorithms using metric access methods (2024)
- Authors:
- Autor USP: TEIXEIRA, LARISSA ROBERTA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- DOI: 10.11606/D.55.2024.tde-27082024-144742
- Subjects: PROCESSAMENTO DE DADOS; ANÁLISE DE DADOS; BANCO DE DADOS
- Keywords: Agrupamento; Clustering; Dados dimensionais; Dimensional data; Indexação; Indexing; k-medoids; k-medoids; Métodos de acesso métrico; Metric access method
- Language: Inglês
- Abstract: Inicialmente, as técnicas e ferramentas de processamento de dados foram desenvolvidas para lidar com tipos de dados escalares. Contudo, com o avanço tecnológico, houve um crescimento significativo na quantidade e complexidade dos dados. Assim, tornou-se necessário o desenvolvimento de técnicas que permitam a manipulação eficiente de tipos de dados complexos. Consideramos aqui como complexos os dados que não contam com uma definição predefinida sobre como devem ser comparados, como é o caso de comparações envolvendo similaridade. Entre as estratégias existentes na literatura, destaca-se a detecção de agrupamento que busca encontrar padrões nos dados através da criação de grupos. Na literatura, os algoritmos de agrupamento baseados em k-medoids destacam-se como uma das abordagens mais utilizadas. Entretanto, esses métodos possuem alto custo computacional quando aplicados em grandes conjuntos de dados. Embora muitos trabalhos na literatura busquem otimizar os algoritmos k-medoids, eles ainda enfrentam limitações quando aplicados a grandes conjuntos de dados, especialmente quando esses dados são complexos, uma vez que exigem o cálculo e armazenamento de uma matriz de distância em memória. Isso os torna inviáveis para lidar com tais conjuntos de dados. Nesta dissertação de mestrado, foi proposto um novo algoritmo que melhora a eficiência computacional da etapa de dos algoritmos k-medoids. O KluSIM utiliza Métodos de Acesso para podar o espaço de busca, acelerando a etapa detroca. Além disso, o KluSIM elimina a necessidade de manter uma matriz de distância em memória principal, superando efetivamente as limitações de memória encontradas nas metodologias existentes. No geral, os experimentos realizados mostram que o KluSIM contribui de maneira efetiva na otimização da etapa de troca dos algoritmos k-medoids, reduzindo significativamente o número de cálculos de distância necessárias durante o processo de agrupamento. O KluSIM pode ser aplicado em tarefas de big data, uma vez que mostrou-se ser escalável e eficaz para o agrupamento nos conjunto de dados nos testes executados.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2024
- Data da defesa: 03.07.2024
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
TEIXEIRA, Larissa Roberta. Improving the efficiency of k-medoids algorithms using metric access methods. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27082024-144742/. Acesso em: 30 dez. 2025. -
APA
Teixeira, L. R. (2024). Improving the efficiency of k-medoids algorithms using metric access methods (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27082024-144742/ -
NLM
Teixeira LR. Improving the efficiency of k-medoids algorithms using metric access methods [Internet]. 2024 ;[citado 2025 dez. 30 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27082024-144742/ -
Vancouver
Teixeira LR. Improving the efficiency of k-medoids algorithms using metric access methods [Internet]. 2024 ;[citado 2025 dez. 30 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-27082024-144742/ - MIGUE-Sim: speeding up similarity queries with native RDBMS resources
- Similarity-slim extension: reducing financial and computational costs of similarity queries in document collections in NoSQL databases
- KluSIM: speeding up k-medoids clustering over dimensional data with metric access method
- A novel approach to reduce the financial and computational costs of similarity queries over document collections in NoSQL databases
- Analysis of expenses from Brazilian Federal Deputies between 2015 and 2018
- Cosim-Gres: towards similarity queries optimization inside RDBMS
Informações sobre o DOI: 10.11606/D.55.2024.tde-27082024-144742 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
