Desempenho de operações distribuídas de agrupamento por similaridade em dados de alta dimensionalidade por meio da VP-Tree

• Ana Paula C. A. Silva Universidade Federal de Uberlândia
• Humberto Razente Universidade Federal de Uberlândia

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

Resumo

As organizações contemporâneas enfrentam o desafio de analisar volumes significativos de dados complexos, utilizando técnicas como análise de agrupamentos. Pesquisas antecedentes introduziram o DSG (Distributed Similarity Grouping), uma solução desenvolvida sob a estratégia MapReduce no Apache Hadoop/Spark, caracterizada pelo paralelismo na identificação de grupos similares em conjuntos de dados massivos. Este trabalho introduz uma evolução desse método, denominado DSG-VPTREE (Distributed Similarity Grouping with Vp-Tree), que incorpora a Vantage Point Tree (VP-Tree) para otimizar o particionamento de dados e melhorar as operações de agrupamento por similaridade. O novo algoritmo permite a otimização tanto do particionamento quanto da análise das janelas de sobreposição das partições. Os resultados dos experimentos demonstram que o DSG-VPTree supera o DSG, apresentando uma redução significativa no tempo de execução e melhor escalabilidade em dados de alta dimensionalidade.

Palavras-chave: Agrupamento por similaridade distribuído, Map/Reduce, Particionamento de dados, Espaços métricos

Referências

Bozkaya, T. and Özsoyoglu, Z. M. (1999). Indexing large metric spaces for similarity search queries. ACM Transactions on Database Systems (TODS), 24(3):361–404. DOI: 10.1145/328939.328959.

Dean, J. and Ghemawat, S. (2004). Mapreduce: Simplified data processing on large clusters. In Brewer, E. A. and Chen, P., editors, Symposium on Operating System Design and Implementation (OSDI), pages 137–150. USENIX. [link].

Fu, A. W., Chan, P. M., Cheung, Y., and Moon, Y. S. (2000). Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances. VLDB J., 9(2):154–173. DOI: 10.1007/PL00010672.

Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart, D., Venkatrao, M., Pellow, F., and Pirahesh, H. (1997). Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub totals. Data Min. Knowl. Discov., 1(1):29–53. DOI: 10.1023/A:1009726021843.

Iqbal, M., Lissandrini, M., and Pedersen, T. B. (2022). A foundation for spatio-textual-temporal cube analytics. Inf. Syst., 108:102009. DOI: 10.1016/j.is.2022.102009.

Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognit. Lett., 31(8):651–666. DOI: 10.1016/J.PATREC.2009.09.011.

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

Silva, Y. N., Sandoval, M., Prado, D., Wallace, X., and Rong, C. (2019). Similarity grouping in big data systems. In Intl Conf. Similarity Search and Applications (SISAP), volume 11807 of LNCS, pages 212–220. Springer. DOI: 10.1007/978-3-030-32047-8_19.

Tang, M., Tahboub, R. Y., Aref, W. G., Atallah, M. J., Malluhi, Q. M., Ouzzani, M., and Silva, Y. N. (2016). Similarity group-by operators for multi-dimensional relational data. IEEE Trans. Knowl. Data Eng., 28(2):510–523. DOI: 10.1109/TKDE.2015.2480400.

Traina-Jr., C., Traina, A. J. M., Faloutsos, C., and Seeger, B. (2002). Fast indexing and visualization of metric data sets using slim-trees. IEEE Trans. Knowl. Data Eng., 14(2):244–260. DOI: 10.1109/69.991715.

Yianilos, P. N. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. In ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pages 311–321. ACM/SIAM. [link].

Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., Ghodsi, A., Gonzalez, J., Shenker, S., and Stoica, I. (2016). Apache spark: a unified engine for big data processing. Commun. ACM, 59(11):56–65. DOI: 10.1145/2934664.