Paper Information | SBC BOOKS

Fill in your paper information

Language (*)

Title (*)

Keywords (*)

Abstract (*)

A geometrical pattern is a set of points with all pairwise distances (or, more generally, relative distances) specified. Finding matches to such patterns has applications to spatial data in seismic, astronomical, and transportation contexts. Finding geometric patterns is a challenging problem as the potential number of sets of elements that compose shapes is exponentially large in the size of the dataset and the pattern. In this paper, we propose algorithms to find patterns in large data applications. Our methods combine quadtrees, matrix multiplication, and bucket join processing to discover sets of points that match a geometric pattern within some additive factor on the pairwise distances. Our distributed experiments show that the choice of composition algorithm (matrix multiplication or nested loops) depends on the freedom introduced in the query geometry through the distance additive factor. Three clearly identified blocks of threshold values guide the choice of the best composition algorithm

Pages (*)

File Link

English Information

Title

Keywords

Abstract

(*) To change the order drag the item to the new position.

Authors

#	Name
1	Fabio Porto(Fporto@lncc.br)
2	Amir Khatibi(amir.khatibi.m@gmail.com)
3	Joao Rittmeyer(joaonr@lncc.br)
4	Eduardo Ogasawara(eogasawara@ieee.org)
5	Patrick Valduriez(Patrick.Valduriez@inria.fr)
6	Dennis Shasha(shasha@courant.nyu.edu)

(*) To change the order drag the item to the new position.

Reference

#	Reference
1	Bishop, C. M. (2006). Pattern recognition and machine learning. Springer, page 7.
2	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.
3	Einstein, A. (2015). Relativity: The special and the general theory.
4	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.
5	Jolion, J. (2001). Graph matching : what are we really talking about. Proceedings of the 3rd IAPR Workshop on Graph-Based Representations in Pattern Recognition.
6	Overbye, D. (2015). Astronomers observe supernova and find they’re watching reruns. New York Times, USA.
7	R. Bank, C. D. (1993). Sparse matrix multiplication package (smmp). Advances in Computational Mathematics, 1:127–137.
8	Samet, H. (1990). The Design and Analysis of Spatial Data Structures. Addison-Wesley.
9	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.
10	U. Zwick, R. Y. (2005). Fast sparse matrix multiplication. ACM Transactions on Algorithms (TALG), 1:2–13.
11	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.
12	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

Paper Registration

Fill in your paper information

English Information

Authors

Reference