Tutorial: Graph-based Methods for Similarity Searches
Abstract
Similarity searches are based on retrieving similar data of one or more data used as reference according to an intrinsic characteristic of the data. Recently, graph-based methods have emerged as a very efficient option to execute similarity queries in metric and non-metric spaces. Graphs model the interconnectivity among data, enabling us to explore relationships and neighbors in an agile way. In this tutorial, we will give an introduction to similarity searches and present graph-based methods for similarity searches, the types of graphs used in such methods, their properties, open challenges, and research opportunities.
Keywords:
Similarity Searches, Graph-based Methods, Proximity Graphs, Metric Spaces
References
Amagata, D., Onizuka, M., and Hara, T. (2022). Fast, exact, and parallel-friendly outlier detection algorithms with proximity graph in metric spaces. The VLDB Journal, pages 1–25.
Fu, C., Xiang, C., Wang, C., and Cai, D. (2019). Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow., 12(5):461–474.
Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., and Zhang, H. (2011). Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Int’l Joint Conf. on Artificial Intelligence IJCAI, pages 1312–1317.
Malkov, Y. A. and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836.
Navarro, G. (2002). Searching in metric spaces by spatial approximation. The VLDB Journal The Int’l Journal on Very Large Data Bases, 11(1):28–46.
Oyamada, R. S., Shimomura, L. C., Junior, S. B., and Kaster, D. S. (2020). Towards proximity graph auto-configuration: An approach based on meta-learning. In Darmont, J., Novikov, B., and Wrembel, R., editors, Advances in Databases and Information Systems, pages 93–107, Cham. Springer International Publishing.
Paredes, R., Chávez, E., Figueroa, K., and Navarro, G. (2006). Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces, pages 85–97. Springer Berlin Heidelberg.
Shimomura, L. C., Oyamada, R. S., Vieira, M. R., and Kaster, D. S. (2021). A survey on graph-based methods for similarity searches in metric spaces. Information Systems, 95:101507.
Wang, M., Xu, X., Yue, Q., and Wang, Y. (2021). A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow., 14(11):1964–1978.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2010). Similarity Search: The Metric Space Approach. Springer, 1st edition.
Fu, C., Xiang, C., Wang, C., and Cai, D. (2019). Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow., 12(5):461–474.
Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., and Zhang, H. (2011). Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Int’l Joint Conf. on Artificial Intelligence IJCAI, pages 1312–1317.
Malkov, Y. A. and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836.
Navarro, G. (2002). Searching in metric spaces by spatial approximation. The VLDB Journal The Int’l Journal on Very Large Data Bases, 11(1):28–46.
Oyamada, R. S., Shimomura, L. C., Junior, S. B., and Kaster, D. S. (2020). Towards proximity graph auto-configuration: An approach based on meta-learning. In Darmont, J., Novikov, B., and Wrembel, R., editors, Advances in Databases and Information Systems, pages 93–107, Cham. Springer International Publishing.
Paredes, R., Chávez, E., Figueroa, K., and Navarro, G. (2006). Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces, pages 85–97. Springer Berlin Heidelberg.
Shimomura, L. C., Oyamada, R. S., Vieira, M. R., and Kaster, D. S. (2021). A survey on graph-based methods for similarity searches in metric spaces. Information Systems, 95:101507.
Wang, M., Xu, X., Yue, Q., and Wang, Y. (2021). A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow., 14(11):1964–1978.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. (2010). Similarity Search: The Metric Space Approach. Springer, 1st edition.
Published
2023-09-25
How to Cite
SHIMOMURA, Larissa C.; KASTER, Daniel S..
Tutorial: Graph-based Methods for Similarity Searches. In: TUTORIALS - BRAZILIAN SYMPOSIUM ON DATABASES (SBBD), 38. , 2023, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 189-193.
DOI: https://doi.org/10.5753/sbbd_estendido.2023.25635.
