Vetor de sufixos métrico compacto

• Frederico R. Rosa Universidade Federal de Uberlândia
• Felipe A. Louza Universidade Federal de Uberlândia https://orcid.org/0000-0003-2931-1470
• Humberto L. Razente Universidade Federal de Uberlândia

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

Resumo

Neste artigo apresentamos uma estrutura de dados compacta para o vetor de sufixos métrico (MSA), um índice baseado em permutações para consultas por similaridade. A estrutura proposta utiliza codificação de inteiros de tamanho variável para armazenar os valores do MSA, os quais são decodificados durante as consultas. A estrutura compacta é construída diretamente dos dados, sem a necessidade de computar o MSA para depois compactá-lo, o que permite a indexação de maiores volumes de dados. Em experimentos com dados de alta dimensionalidade extraídos de 20 milhões de imagens, nossa representação compacta utilizou 33% da memória total do método original, com aumento no tempo das consultas por um fator de 3,4.

Palavras-chave: estrutura de dados compacta, índice baseado em permutações, consultas por similaridade, vetor de sufixos métrico, algoritmos

Referências

Anh, V. N. and Moffat, A. (2005). Inverted index compression using word-aligned binary codes. Inf. Retr., 8(1):151–166. doi:10.1023/B:INRT.0000048490.99518.5c.

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

Chávez, E., Figueroa, K., and Navarro, G. (2008). Effective proximity retrieval by ordering permutations. IEEE Trans. Pattern Anal. Mach. Intell., 30(9):1647–1658.

Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory, 21(2):194–203. doi:10.1109/TIT.1975.1055349.

Fagin, R., Kumar, R., and Sivakumar, D. (2003). Comparing top k lists. SIAM J. Discret. Math., 17(1):134–160. doi:10.1137/S0895480102412856.

Jégou, H., Tavenard, R., Douze, M., and Amsaleg, L. (2011). Searching in one billion vectors: Re-rank with source coding. In IEEE Int’l Conf. Acoustics, Speech, and Signal Processing (ICASSP), pages 861–864, Prague. doi:10.1109/ICASSP.2011.5946540.

Lew, M. S., Sebe, N., Djeraba, C., and Jain, R. C. (2006). Content-based multimedia information retrieval: State of the art and challenges. ACM Trans. Multim. Comput. Commun. Appl., 2(1):1–19. doi:10.1145/1126004.1126005.

Manber, U. and Myers, E. W. (1993). Suffix arrays: A new method for on-line string searches. SIAM J. Comput., 22(5):935–948. doi:10.1137/0222058.

Mohamed, H. and Marchand-Maillet, S. (2013). Metric suffix array for large-scale similarity search. In ACM WSDM 2013 Workshop on Large Scale and Distributed Systems for Information Retrieval, Rome, IT, pages 1–6.

Navarro, G. (2016). Compact Data Structures - A Practical Approach. Cambridge University Press.