Point pattern search in big data

Fabio Porto, Alberto Krone-Martins, João N. Rittmeyer, Patrick Valduriez, Eduardo Ogasawara, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consider a set of points P in space with at least some of the pairwise distances specified. Given this set P, consider the following three kinds of queries against a database D of points: (i) pure constellation query: find all sets S in D of size |P| that exactly match the pairwise distances within P up to an additive error ϵ; (ii) isotropic constellation queries: find all sets S in D of size |P| such that there exists some scale factor f for which the distances between pairs in S exactly match f times the distances between corresponding pairs of P up to an additive ϵ; (iii) non-isotropic constellation queries: find all sets S in D of size |P| such that there exists some scale factor f and for at least some pairs of points, a maximum stretch factor mi , j > 1 such that (f × mi , j ×dist(pi, pj))+ϵ > dist(si,sj) >(f × dist(pi, pj)) - ϵ. Finding matches to such queries has applications to spatial data in astronomical, seismic, and any domain in which (approximate, scale-independent) geometrical matching is required. Answering the isotropic and non-isotropic queries is challenging because scale factors and stretch factors may take any of an infinite number of values. This paper proposes practically efficient sequential and distributed algorithms for pure, isotropic, and non-isotropic constellation queries. As far as we know, this is the first work to address isotropic and non-isotropic queries.

Original languageEnglish (US)
Title of host publicationScientific and Statistical Database Management - 30th International Conference, SSDBM 2018, Proceedings
EditorsMichael Bohlen, Johann Gamper, Peer Kroger, Dimitris Sacharidis
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450365055
DOIs
StatePublished - Jul 9 2018
Event30th International Conference on Scientific and Statistical Database Management, SSDBM 2018 - Bolzano-Bozen, Italy
Duration: Jul 9 2018Jul 11 2018

Publication series

NameACM International Conference Proceeding Series

Other

Other30th International Conference on Scientific and Statistical Database Management, SSDBM 2018
CountryItaly
CityBolzano-Bozen
Period7/9/187/11/18

Keywords

  • Big Data
  • Distance Matching
  • Geometrical Patterns
  • Isotropic
  • Pattern Search
  • Point set Registration
  • Spatial Patterns

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Point pattern search in big data'. Together they form a unique fingerprint.

  • Cite this

    Porto, F., Krone-Martins, A., Rittmeyer, J. N., Valduriez, P., Ogasawara, E., & Shasha, D. (2018). Point pattern search in big data. In M. Bohlen, J. Gamper, P. Kroger, & D. Sacharidis (Eds.), Scientific and Statistical Database Management - 30th International Conference, SSDBM 2018, Proceedings (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3221269.3221294