Buscas por similaridade com diversificação de resultados apoiadas por índices métricos
Resumo
A diversificação de resultados enriquece consultas k-NN ao recuperar objetos diferentes entre si. Nossa primeira contribuição, o algoritmo diversity browsing, estende a rotina k-NN incremental distance browsing, garantindo a diversificação de resultados por meio de critérios de Influência. Nossa segunda contribuição analisa o método diversity browsing em espaços de alta dimensionalidade da perspectiva da Dimensionalidade Intrínseca Local (LID). Uma extensa investigação revelou que (i) a diversificação é limitada tanto pela LID quanto pelo particionamento por Influência, (ii) o diversity browsing gera espaços amostrais por consulta com menor concentração de distâncias em comparação aos dados originais, (iii) índices ajustados aceleram o diversity browsing em trechos de baixas/médias LID, e (iv) a diferença de desempenho entre k-NN com e sem diversificação de resultados diminui com a LID.
Palavras-chave:
Busca por similaridade, Diversificação de resultados, Espaços métricos, Dimensionalidade intrínseca local, Concentração de distâncias
Referências
Amsaleg, L., Chelly, O., Furon, T., Girard, S., Houle, M., Kawarabayashi, K., and Nett, M. (2015). Estimating local intrinsic dimensionality. Special Interest Group on Knowledge Discovery and Data Mining (SIGKDD), pages 29–38. ACM.
Amsaleg, L., Chelly, O., Houle, M., Kawarabayashi, K.-I., Radovanovic, M., and Treeratanajaru, W. (2019). Intrinsic dimensionality estimation within tight localities. International Conference on Data Mining (SDM), pages 181–189. SIAM.
Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999). When is “nearest neighbor” meaningful? International Conference on Database Theory (ICDT), pages 217– 235. Springer.
Chávez, E., Navarro, G., Baeza-Yates, R., and Marroquín, J. (2001). Searching in metric spaces. Computing Surveys, volume 33, pages 273–321. ACM.
Drosou, M., Jagadish, H., Pitoura, E., and Stoyanovich, J. (2017). Diversity in big data: A review. Big data, 5(2):73–84.
Francois, D., Wertz, V., and Verleysen, M. (2007). The concentration of fractional distances. Transactions on Knowledge and Data Engineering (TKDE), volume 19, pages 873–886. IEEE.
Hetland, M. L. (2009). The basic principles of metric indexing. Swarm intelligence for multi-objective problems in data mining, pages 199–232. Springer.
Hjaltason, G. and Samet, H. (2003). Index-driven similarity search in metric spaces. Transactions on Database Systems (TODS), 28(4):517–580.
Jasbick, D., Santos, L., Azevedo-Marques, P. M., Traina, A. J., de Oliveira, D., and Bedo, M. (2023). Pushing diversity into higher dimensions: The lid effect on diversified similarity searching. Information Systems, 114:102166.
Jasbick, D., Santos, L., de Oliveira, D., and Bedo, M. (2020). Some branches may bear rotten fruits: Diversity browsing vp-trees. Similarity Search and Applications (SISAP), pages 140–154. Springer.
Kucuktunc, O. and Ferhatosmanoglu, H. (2011). λ-diverse nearest neighbors browsing for multidimensional data. Transactions on Knowledge and Data Engineering (TKDE), volume 25, pages 481–493. IEEE.
Lopes, C., Santos, L., Jasbick, D., de Oliveira, D., and Bedo, M. (2021). An empirical assessment of quality metrics for diversified similarity searching. Journal of Information and Data Management (JIDM), 12(3).
Pestov, V. (2013). Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions. Algorithmica, 66(2):310–328.
Santos, L., Blanco, G., Oliveira, D., Traina, A., Traina Jr, C., and Bedo, M. (2018). Exploring Diversified Similarity with Kundaha. Conference on Information and Knowledge Management (CIKM), pages 1903–1906. ACM.
Santos, L., Oliveira, W., Ferreira, M., Traina, A., and Traina Jr, C. (2013). Parameter-free and domain-independent similarity search with diversity. International Conference on Scientific and Statistical Database Management (SSDBM), pages 1–12.
Vieira, M., Razente, H., Barioni, M., Hadjieleftheriou, M., Srivastava, D., Traina Jr., C., and Tsotras, V. (2011). On query result diversification. International Conference on Data Engineering (ICDE), pages 1163–1174. IEEE.
Amsaleg, L., Chelly, O., Houle, M., Kawarabayashi, K.-I., Radovanovic, M., and Treeratanajaru, W. (2019). Intrinsic dimensionality estimation within tight localities. International Conference on Data Mining (SDM), pages 181–189. SIAM.
Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999). When is “nearest neighbor” meaningful? International Conference on Database Theory (ICDT), pages 217– 235. Springer.
Chávez, E., Navarro, G., Baeza-Yates, R., and Marroquín, J. (2001). Searching in metric spaces. Computing Surveys, volume 33, pages 273–321. ACM.
Drosou, M., Jagadish, H., Pitoura, E., and Stoyanovich, J. (2017). Diversity in big data: A review. Big data, 5(2):73–84.
Francois, D., Wertz, V., and Verleysen, M. (2007). The concentration of fractional distances. Transactions on Knowledge and Data Engineering (TKDE), volume 19, pages 873–886. IEEE.
Hetland, M. L. (2009). The basic principles of metric indexing. Swarm intelligence for multi-objective problems in data mining, pages 199–232. Springer.
Hjaltason, G. and Samet, H. (2003). Index-driven similarity search in metric spaces. Transactions on Database Systems (TODS), 28(4):517–580.
Jasbick, D., Santos, L., Azevedo-Marques, P. M., Traina, A. J., de Oliveira, D., and Bedo, M. (2023). Pushing diversity into higher dimensions: The lid effect on diversified similarity searching. Information Systems, 114:102166.
Jasbick, D., Santos, L., de Oliveira, D., and Bedo, M. (2020). Some branches may bear rotten fruits: Diversity browsing vp-trees. Similarity Search and Applications (SISAP), pages 140–154. Springer.
Kucuktunc, O. and Ferhatosmanoglu, H. (2011). λ-diverse nearest neighbors browsing for multidimensional data. Transactions on Knowledge and Data Engineering (TKDE), volume 25, pages 481–493. IEEE.
Lopes, C., Santos, L., Jasbick, D., de Oliveira, D., and Bedo, M. (2021). An empirical assessment of quality metrics for diversified similarity searching. Journal of Information and Data Management (JIDM), 12(3).
Pestov, V. (2013). Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions. Algorithmica, 66(2):310–328.
Santos, L., Blanco, G., Oliveira, D., Traina, A., Traina Jr, C., and Bedo, M. (2018). Exploring Diversified Similarity with Kundaha. Conference on Information and Knowledge Management (CIKM), pages 1903–1906. ACM.
Santos, L., Oliveira, W., Ferreira, M., Traina, A., and Traina Jr, C. (2013). Parameter-free and domain-independent similarity search with diversity. International Conference on Scientific and Statistical Database Management (SSDBM), pages 1–12.
Vieira, M., Razente, H., Barioni, M., Hadjieleftheriou, M., Srivastava, D., Traina Jr., C., and Tsotras, V. (2011). On query result diversification. International Conference on Data Engineering (ICDE), pages 1163–1174. IEEE.
Publicado
25/09/2023
Como Citar
JASBICK, Daniel L.; DE OLIVEIRA, Daniel; BEDO, Marcos V. N..
Buscas por similaridade com diversificação de resultados apoiadas por índices métricos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTDBD) - SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 38. , 2023, Belo Horizonte/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 198-212.
DOI: https://doi.org/10.5753/sbbd_estendido.2023.231573.
