Learned Index Baseado na Predição de Vértices iniciais em Grafos de Proximidade

• Matheus B. Bastos Universidade Estadual de Londrina (UEL)
• Daniel S. Kaster Universidade Estadual de Londrina (UEL)

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

Resumo

Buscas por similaridade em dados complexos utilizam métodos para acelerar consultas, como a aproximação espacial em grafos de proximidade, que sofre com o problema da escolha do vértice inicial. Recentemente, learned indexes surgiram utilizando aprendizado de máquina para modelar a distribuição de dados e outras características, apresentando resultados promissores. Este artigo apresenta um learned index eficiente sobre métodos baseados em grafos para buscas por similaridade. O método proposto aplica aprendizado supervisionado para predição dos vértices iniciais de busca. O método reduziu o número de computações de distância necessárias para alcançar uma alta taxa de recall em vários conjuntos de dados avaliados.

Palavras-chave: Learned Indexes, Grafos de proximidade, Buscas por Similaridade

Referências

Antol, M., Ol’ha, J., Slanináková, T., and Dohnal, V. (2021). Learned metric index-proposition of learned indexing for unstructured data. Information Systems, 100:101774.

Bolettieri, P., Esuli, A., Falchi, F., Lucchese, C., Perego, R., Piccioli, T., and Rabitti, F. (2009). CoPhIR: a test collection for content-based image retrieval. arXiv preprint arXiv:0905.4627.

Boytsov, L. and Naidan, B. (2013). Engineering efficient and effective non-metric space library. In International Conference on Similarity Search and Applications, pages 280-293.

Cutler, A., Cutler, D. R., and Stevens, J. R. (2012). Random forests. In Ensemble machine learning, pages 157-175.

Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., and Zhang, H. (2011). Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Twenty-Second International Joint Conference on Artificial Intelligence.

Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. (2018). The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504.

Navarro, G. (2002). Searching in metric spaces by spatial approximation. The VLDB Journal, 11(1):28-46.

Novak, D., Batko, M., and Zezula, P. (2011). Metric index: An efficient and scalable solution for precise and approximate similarity search. Information Systems, 36(4):721-733.

Ocsa, A., Bedregal, C., and Cuadros-Vargas, E. (2007). A new approach for similarity queries using neighborhood graphs. In SBBD, pages 131-142.

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. (2011). Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830.

Shimomura, L. C. and Kaster, D. S. (2019). Hgraph: a connected-partition approach to proximity graphs for similarity search. In International Conference on Database and Expert Systems Applications, pages 106-121.