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

Cited literature [6 references]  Display  Hide  Download
Contributor : Patrick Valduriez <>
Submitted on : Friday, October 20, 2017 - 3:04:19 PM
Last modification on : Friday, March 15, 2019 - 1:15:10 AM
Long-term archiving on : Sunday, January 21, 2018 - 1:23:30 PM


Files produced by the author(s)




Amir Khatibi, Fabio Porto, Joao Rittmeyer, Eduardo Ogasawara, Patrick Valduriez, et al.. Pre-processing and Indexing techniques for Constellation Queries in Big Data. DaWaK: Data Warehousing and Knowledge Discovery, Aug 2017, Lyon, France. pp.164-172, ⟨10.1007/978-3-319-64283-3_12⟩. ⟨lirmm-01620398⟩



Record views


Files downloads