Métodos de Seleção de Pivôs: Uma avaliação experimental

• João V. S. Leite Universidade Federal Fluminense (UFF)
• Wagner R. Telles Universidade Federal Fluminense (UFF)
• Rodolfo A. Oliveira Universidade Federal Fluminense (UFF) http://orcid.org/0000-0002-8278-8465
• Daniel de Oliveira Universidade Federal Fluminense (UFF) http://orcid.org/0000-0001-9346-7651
• Marcos Bedo Universidade de São Paulo (USP)

DOI: https://doi.org/10.5753/sbbd_estendido.2022.21868

Resumo

Consultas por similaridade em Espaços Métricos apoiam tarefas computacionais que envolvem comparações por distância, e.g., recuperação por conteúdo e classificação. Esse paradigma permite utilizar índices baseados em pivôs para reduzir o número de cálculos de distância e otimizar a execução das consultas. Os índices armazenam as distâncias dos objetos da base de dados para um conjunto de elementos selecionados (i.e., os pivôs) tal que, durante uma busca, esses valores pré-computados são combinados com a desigualdade triangular para descartar objetos da resposta. Portanto, a escolha de pivôs de "boa qualidade" é determinante para o desempenho dessas estruturas. Esse estudo investiga o impacto de oito estratégias distintas de escolha de pivôs (kMEDOIDS,C-HULL, PCA, M-VARIANCE, SELECTION, S-S-SELECTION, GNAT e M-SEPARATED) aplicadas aos índices Omni kd-Tree e VP-Tree. A avaliação experimental sugere que os métodos M-VARIANCE e kMEDOIDS encontram os melhores pivôs, enquanto as estratégias GNAT e C-HULL apresentam as piores escolhas. Os resultados também sugerem que índices diferentes são, potencialmente, melhor ajustados por diferentes métodos de escolha de pivôs.

Palavras-chave: Indíces Métricos, Consultas por Similaridade, Seleção de Pivôs

Referências

Chávez, E., Navarro, G., Baeza-Yates, R., and Marroquín, J. L. (2001). Searching in metric spaces. ACM Computing Surveys, 33(3):273-321.

Chen, L., Gao, Y., Zheng, B., Jensen, C., Yang, H., and Yang, K. (2017). Pivot-based metric indexing. Proceedings of the VLDB Endowment, 10(10):1058-1069.

Hetland, M. (2009). The basic principles of metric indexing. In Swarm Intelligence for Multi-objective Problems in Mining, pages 199-232. Springer.

Hjaltason, G. and Samet, H. (2003). Index-driven similarity search in metric spaces. ACM Transactions on Database Systems, 28(4):517-580.

Mao, R., Zhang, P., Li, X., Liu, X., and Lu, M. (2016). Pivot selection for metric-space indexing. International Journal of Machine Learning and Cybernetics, 7(2):311-323.

Traina Jr, C., Filho, R., Traina, A., Vieira, M., and Faloutsos, C. (2007). The omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient. The VLDB Journal, 16(4):483-505.

Yianilos, P. (1993). Data structures and algorithms for nearest neighbor. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, volume 66, page 311. SIAM.

Zhu, Y., Chen, L., Gao, Y., and Jensen, C. (2022). Pivot selection algorithms in metric spaces: A survey and experimental study. The VLDB Journal, 31(1):23-47.