Constellation Queries over Big Data

• Fabio Porto Laboratório Nacional de Computação Científica
• Amir Khatibi Universidade Federal de Minas Gerais
• João N. Rittmeyer Laboratório Nacional de Computação Científica
• Eduardo Ogasawara Centro Federal de Educação Tecnológica Celso Suckow da Fonseca
• Patrick Valduriez INRIA
• Dennis Shasha New York University

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

Resumo

Um padrão geométrico é definido por um conjunto de pontos e todos os pares de distâncias entre estes pontos. Encontrar casamentos de padrões geométricos em datasets tem aplicações na astronomia, na pesquisa sísmica e no desenho de áreas urbanas. A solução do problema impõe um grande desafio, considerando-se o número exponencial de candidatos, potencialmente função do número de elementos no dataset e número de pontos na forma geométrica. O método aqui apresentado inclui: quadtrees,multiplicação de matrizes e junções espaciais para encontrar conjuntos de pontos que se aproximem do padrão fornecido, com um erro admissível. Apresentamos uma implementação distribuída reveladora de que a escolha do algoritmo (multiplicação de matrizes ou junções espaciais) depende da liberdade introduzida por um fator de erro aditivo na geometria do padrão. Identificamos três regiões baseadas nos valores de erro tolerados que determinam a escolha do algoritmo.

Palavras-chave: Big data, constellation queries, large data patterns, quadtrees, matrix multiplication, bucket join processing

Referências

Bishop, C. M. (2006). Pattern recognition and machine learning. Springer, page 7.

Brucato, M., Beltran, J. F., Abouzied, A., and Meliou, A. (2016). Scalable package queries in relational database systems. Proc. VLDB Endow., 9(7):576–587. 00004.

Einstein, A. (2015). Relativity: The special and the general theory.

Giugno, R. and Shasha, D. (2002). GraphGrep: A fast and universal method for querying graphs. In Proceedings - International Conference on Pattern Recognition, volume 16, pages 112–115. 2 edition. 00125.

Jolion, J. (2001). Graph matching : what are we really talking about. Proceedings of the 3rd IAPR Workshop on Graph-Based Representations in Pattern Recognition.

Overbye, D. (2015). Astronomers observe supernova and find they’re watching reruns. New York Times, USA.

R. Bank, C. D. (1993). Sparse matrix multiplication package (smmp). Advances in Computational Mathematics, 1:127–137.

Samet, H. (1990). The Design and Analysis of Spatial Data Structures. Addison-Wesley.

Singla, P. and Domingos, P. (2005). Object identification with attribute mediated dependences. Proceedings of the 9th European conference on Principles and Practice of Knowledge Discovery in Databases.

U. Zwick, R. Y. (2005). Fast sparse matrix multiplication. ACM Transactions on Algorithms (TALG), 1:2–13.

Zou, L., Chen, L., and Ozsu, M. T. (2009). Distance-join: Pattern Match Query in a Large Graph Database. Proc. VLDB Endow., 2(1):886–897.

Zou, L., Chen, L., Ozsu, M. T., and Zhao, D. (2011). Answering pattern match queries in large graph databases via graph embedding. The VLDB Journal, 21:97-120