Skip to Main content Skip to Navigation
Conference papers

Point Pattern Search in Big Data

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 m i, j > 1 such that (f × m i, 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01819290
Contributor : Patrick Valduriez <>
Submitted on : Wednesday, June 20, 2018 - 11:23:56 AM
Last modification on : Tuesday, March 17, 2020 - 2:49:13 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 9:59:38 AM

File

point-pattern-search-porto.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Fabio Porto, Joao Rittmeyer, Eduardo Ogasawara, Alberto Krone-Martins, Patrick Valduriez, et al.. Point Pattern Search in Big Data. SSDBM: Scientific and Statistical Database Management, Jul 2018, Bozen-Bolzano, Italy. pp.#21, ⟨10.1145/3221269.3221294⟩. ⟨lirmm-01819290⟩

Share

Metrics

Record views

1636

Files downloads

428