Constellation Queries over Big Data

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01867833
Contributor : Patrick Valduriez <>
Submitted on : Tuesday, September 4, 2018 - 4:24:14 PM
Last modification on : Wednesday, August 14, 2019 - 10:46:03 AM
Long-term archiving on: Wednesday, December 5, 2018 - 6:11:39 PM

File

085-sbbd_2018-fp.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01867833, version 1

Collections

Citation

Fábio Porto, Amir Khatibi, Joao Rittmeyer, Eduardo Ogasawara, Patrick Valduriez, et al.. Constellation Queries over Big Data. SBBD: Simpósio Brasileiro de Banco de Dados, SBC, Aug 2018, Rio de Janeiro, Brazil. pp.85-96. ⟨lirmm-01867833⟩

Share

Metrics

Record views

1292

Files downloads

63