Pre-processing and Indexing techniques for Constellation Queries in Big Data

Abstract : Geometric patterns are defined by a spatial distribution of a set of objects. They can be found in many spatial datasets as in seismic, astronomy , and transportation. A particular interesting geometric pattern is exhibited by the Einstein cross, which is an astronomical phenomenon in which a single quasar is observed as four distinct sky objects when captured by earth telescopes. Finding such crosses, as well as other geometric patterns, collectively referred to as constellation queries, 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 query pattern. In this paper we propose algorithms to optimize the computation of constellation queries. Our techniques involve pre-processing the query to reduce its di-mensionality as well as indexing the data to fasten stars neighboring computation using a PH-tree. We have implemented our techniques in Spark and evaluated our techniques by a series of experiments. The PH-tree indexing showed very good results and guarantees query answer completeness.
Type de document :
Communication dans un congrès
DaWaK 2017: 19th International Conference on Big Data Analytics and Knowledge Discovery, Aug 2017, Lyon, France. Springer, LNCS, pp.74-87, 2017, Big Data Analytics and Knowledge Discovery. 〈http://www.dexa.org/dawak2017〉
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01620398
Contributeur : Patrick Valduriez <>
Soumis le : vendredi 20 octobre 2017 - 15:04:19
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : dimanche 21 janvier 2018 - 13:23:30

Fichier

ConstellationQuery_Dexa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01620398, version 1

Collections

Citation

Amir Khatibi, Fabio Porto, Joao Rittmeyer, Eduardo Ogasawara, Patrick Valduriez, et al.. Pre-processing and Indexing techniques for Constellation Queries in Big Data. DaWaK 2017: 19th International Conference on Big Data Analytics and Knowledge Discovery, Aug 2017, Lyon, France. Springer, LNCS, pp.74-87, 2017, Big Data Analytics and Knowledge Discovery. 〈http://www.dexa.org/dawak2017〉. 〈lirmm-01620398〉

Partager

Métriques

Consultations de la notice

1494

Téléchargements de fichiers

98