Exploring the Use of B+trees in Similarity Indexing

• Jéssica N. B. de Farias UFU
• Maria Camila N. Barioni UFU
• Humberto L. Rezende UFU

DOI: https://doi.org/10.5753/sbbd.2019.8817

Abstract

This paper presents a new metric indexing method called GroupSim+ which allows narrowing the minimal cut-regions, when compared with related works. This characteristic of the method contributes to the optimization of similarity queries. The experiments performed with different datasets demonstrate the effectiveness of the approach adopted in the development

Keywords: metric access methods, similarity search

References

Jagadish, H., Ooi, B., Tan, K., Yu, C., and Zhang, R. (2005). iDistance: an adaptive b+tree based indexing method for nearest neighbor search. ACM TODS, 30(2):364–397. DOI: https://doi.org/10.1145/1071610.1071612

Razente, H., Lima, R. B., and Barioni, M. C. (2017). Similarity search through onedimensional embeddings. In ACM SAC, pages 874–879, Marrakech, Marrocos. DOI: https://doi.org/10.1145/3019612.3019674

Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, San Francisco.

Socorro, R., Mico, L., and Oncina, J. (2011). A fast pivot-based indexing algorithm for metric spaces. Pattern Recognition Letters, 32(11):1511–1516. DOI: https://doi.org/10.1016/j.patrec.2011.04.016

Traina-Jr, C., Filho, R. F., Traina, A., Vieira, M. R., and Faloutsos, C. (2007). The omnifamily of all-purpose access methods: A simple and effective way to make similarity search more efficient. The VLDB Journal, 16(4):483–505. DOI: https://doi.org/10.1007/s00778-005-0178-0