A top-k spatial join querying processing algorithm based on spark. (January 2020)

• Record Type: Journal Article
• Authors: Qiao, Baiyou; Hu, Bing; Zhu, Junhai; Wu, Gang; Giraud-Carrier, Christophe; Wang, Guoren
• Is Part Of: Information systems. Volume 87(2019)
• Publication Date: 2020-01
• Subjects: Cloud computing -- Spark platform -- Top-k spatial join query -- Plane sweeping algorithm; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2019.101419
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Aiming at the problem of top- k spatial join query processing in cloud computing systems, a Spark-based top- k spatial join (STKSJ) query processing algorithm is proposed. In this algorithm, the whole data space is divided into grid cells of the same size by a grid partitioning method, and each spatial object in one data set is projected into a grid cell. The Minimum Bounding Rectangle (MBR) of all spatial objects in each grid cell is computed. The spatial objects overlapping with these MBRs in another spatial data set are replicated to the corresponding grid cells, thereby filtering out spatial objects for which there are no join results, thus reducing the cost of subsequent spatial join processing. An improved plane sweeping algorithm is also proposed that speeds up the scanning mode and applies threshold filtering, thus greatly reducing the communication and computation costs of intermediate join results in subsequent top- k aggregation operations. Experimental results on synthetic and real data sets show that the proposed algorithm has clear advantages, and better performance than existing top- k spatial join query processing algorithms. Highlights: To the best of our knowledge, STKSJ algorithm is the first implementation in Spark. Grid partitioning and Z-order methods are used to partition and encode spatial data. Two efficient operations are presented to project and replicate spatial objects. An improved plane sweeping algorithm is proposed to improve the performance of STKSJ. Experimental results show that STKSJ performs better than the other algorithms.