Constellation Queries over Big Data - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2018

Constellation Queries over Big Data

Résumé

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.
Um padra ̃o geome ́trico e ́ definido por um conjunto de pontos e todos os pares de distaˆncias entre estes pontos. Encontrar casamentos de padro ̃es geome ́tricos em datasets tem aplicac ̧o ̃es na astronomia, na pesquisa s ́ısmica e no desenho de a ́reas urbanas. A soluc ̧a ̃o do problema impo ̃e um grande desafio, considerando-se o nu ́mero exponencial de candidatos, potencialmente func ̧a ̃o do nu ́mero de elementos no dataset e nu ́mero de pontos na forma geome ́trica. O me ́todo aqui apresentado inclui: quadtrees,multiplicac ̧a ̃o de matrizes e junc ̧o ̃es espaciais para encontrar conjuntos de pontos que se aproximem do padra ̃o fornecido, com um erro admiss ́ıvel. Apresentamos uma implementac ̧a ̃o dis- tribu ́ıda reveladora de que a escolha do algoritmo (multiplicac ̧a ̃o de matrizes ou junc ̧o ̃es espaciais) depende da liberdade introduzida por um fator de erro adi- tivo na geometria do padra ̃o. Identificamos treˆs regio ̃es baseadas nos valores de erro tolerados que determinam a escolha do algoritmo.

Mots clés

Fichier principal
Vignette du fichier
085-sbbd_2018-fp.pdf (393.16 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01867833 , version 1 (04-09-2018)

Identifiants

Citer

Fábio Porto, Amir Khatibi, Joao Guilherme 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⟩
189 Consultations
137 Téléchargements

Altmetric

Partager

More