Pre-processing and indexing techniques for constellation queries in big data

Amir Khatibi, Fabio Porto, Joao Guilherme Rittmeyer, Eduardo Ogasawara, Patrick Valduriez, Dennis Shasha

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


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 refered 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 dimensionality 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.

Original languageEnglish (US)
Title of host publicationBig Data Analytics and Knowledge Discovery - 19th International Conference, DaWaK 2017, Proceedings
EditorsLadjel Bellatreche, Sharma Chakravarthy
PublisherSpringer Verlag
Number of pages9
ISBN (Print)9783319642826
StatePublished - 2017
Event19th International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2017 - Lyon, France
Duration: Aug 28 2017Aug 31 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10440 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2017


  • Constellation queries
  • Dataset pre-processing
  • Geometric shapes
  • PH-tree indexing
  • Query pre-processing
  • SQL extension

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Pre-processing and indexing techniques for constellation queries in big data'. Together they form a unique fingerprint.

Cite this