Parallel Selectivity Estimation for Optimizing Multidimensional Spatial Join Processing on GPUs

Jianting Zhang, Simin You, Le Gruenwald
Dept. of Computer Science, City College of New York, New York City, NY, 10031
City College of New York, Technical report, 2013


   title={Parallel Selectivity Estimation for Optimizing Multidimensional Spatial Join Processing on GPUs},

   author={Zhang, Jianting and You, Simin and Gruenwald, Le},



Download Download (PDF)   View View   Source Source   



Managing large-scale data is typically memory intensive. The current generation of GPUs has much lower memory capacity than CPUs which is often a limiting factor in processing large data. It is desirable to reduce memory footprint in spatially joining large-scale datasets through query optimization. In this study, we present a technique of selectivity estimation for optimizing spatial join processing on GPUs. By seamlessly integrating multi-dimensional cumulative histograms and the summed-area-table algorithm, our technique can be efficiently realized on GPUs with good portability. Our experiments on spatially joining two sets of Minimum Bounding Boxes (MBBs) derived from real point and polygon data, each with about one million MBBs, have shown that computing the total numbers of MBB pairs at four grid levels took only about 3/4 second. By using the best grid resolution, our technique saves 38.4% memory for the spatial join. When histograms are materialized, it only took a few tens of milliseconds to search for the best grid level for the spatial join.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: