.png){kind=icon}
返回
CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing
.png){kind=icon}
OA
AI
DOI：10.1080/10095020.2025.2510364.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Load-balanced spatial partitioning is crucial for achieving high-efficiency distributed spatial join processing. However, existing spatial partitioning methods focus more on balancing data quantity, and there is much less emphasis on accurately quantifying computational loads and generating partitioning layouts according to the derived loads. To bridge these gaps, we propose a novel partitioning method, i.e. a computational intensity-balanced partitioner (termed CIBPartitioner for short), to enhance the efficiency of distributed spatial join processing by ensuring computational load balance. First, a computational intensity (CI) indicator is defined through theoretical analysis of the time complexity of spatial join processing to quantify the computational loads. Second, a distributed estimation method using grid histograms is introduced to efficiently calculate the distribution ofCI. Finally, inspired by the KDBTree, a CI-balanced partitioning scheme is designed to partition the grid cells in the grid histogram according to theCIdistribution, which minimizes theCIdifferences across partitions to achieve a balancedCIlayout. Extensive experiments on real-world datasets demonstrate that CIBPartitioner significantly improves computational load balancing and enhances the end-to-end efficiency of distributed spatial join processing compared with popular spatial partitioners, including KDBTree. The source code of CIBPartitioner has been released.
Keyword:
Distributed spatial join
spatial partitioning
load balancing
computational intensity
期刊
G
IF:
5.5
论文数:
864
被引数:
2.4K
机构
引用论文
Jiang, W., M. Parvanov, and G. Alonso. 2023. “SwiftSpatial: Spatial Joins on Modern Hardware.” arXiv. https://doi.org/10.48550/ARXIV.2309.16520. (Open in a new window)Google Scholar江, W., M. 帕尔瓦诺夫, 和 G. 阿尔隆索. 2023. "SwiftSpatial: 现代硬件上的空间连接." arXiv. https://doi.org/10.48550/ARXIV.2309.16520. (在新窗口中打开)谷歌学术.png)
IF0
PREAI
分享收藏Papadopoulos, A. N., A. Corral, A. Nanopoulos, and Y. Theodoridis. 2009. “R-Tree (And Family).” In Encyclopedia of Database Systems, edited by L. Liu and M. T. Özsu, 2453–2459. Boston, MA: Springer US. https://doi.org/10.1007/978-0-387-39940-9_300. (Open in a new window)Google Scholar帕帕多普洛斯, A. N., A. 科拉尔, A. 纳诺普洛斯, 和 Y. 西奥多里迪斯. 2009. “R树(及其家族).” 载于《数据库系统百科全书》, L. 刘 和 M. T. 奥兹苏 编, 2453–2459. 波士顿, MA: 施普林格美国. https://doi.org/10.1007/978-0-387-39940-9_300. (在新窗口中打开)谷歌学术
IF0
PREAI
分享收藏Tampakis, P., E. Chondrodima, A. Tritsarolis, A. Pikrakis, Y. Theodoridis, K. Pristouris, H. Nakos, P. Kalampokis, and T. Dalamagas. 2022. “I4sea: A Big Data Platform for Sea Area Monitoring and Analysis of Fishing Vessels Activity.” Geo-Spatial Information Science 25 (2): 132–154. https://doi.org/10.1080/10095020.2021.1971055. (Open in a new window)Web of Science ®(Open in a new window)Google Scholar塔姆帕基斯, P., E. 钦多罗迪玛, A. 特里特萨罗利斯, A. 皮克里克斯, Y. 西奥多里迪斯, K. 普里斯特奥里斯, H. 纳科斯, P. 卡兰波基斯, 和 T. 达拉马加斯. 2022. “I4sea: 用于海区监测和捕捞船活动分析的Big Data平台.” 地理空间信息科学 25 (2): 132–154. https://doi.org/10.1080/10095020.2021.1971055. (在新窗口中打开)Web of Science ®(在新窗口中打开)谷歌学术
IF0
PREAI
分享收藏Vu, T., A. Belussi, S. Migliorini, and A. Eldawy. 2021. “A Learned Query Optimizer for Spatial Join.” In Proceedings of the 29th International Conference on Advances in Geographic Information Systems, 458–467. Beijing China: ACM. https://doi.org/10.1145/3474717.3484217. (Open in a new window)Google ScholarVu, T., A. Belussi, S. Migliorini, and A. Eldawy. 2021. “一种学习型空间连接查询优化器。”载《第29届国际地理信息系统进展会议论文集》，458—467页。中国北京：ACM. https://doi.org/10.1145/3474717.3484217. (在新窗口中打开)Google Scholar
IF0
PREAI
分享收藏Xie, D., F. Li, B. Yao, G. Li, L. Zhou, and M. Guo. 2016. “Simba: Efficient In-Memory Spatial Analytics.” In Proceedings of the 2016 International Conference on Management of Data, 1071–1085. San Francisco California USA: ACM. https://doi.org/10.1145/2882903.2915237. (Open in a new window)Google Scholar谢东, 李方, 姚斌, 李刚, 周磊, 郭明. 2016. “Simba: 高效的内存空间分析.” 见：2016年国际数据管理会议论文集, 第1071–1085页. 美国加利福尼亚州旧金山: ACM. https://doi.org/10.1145/2882903.2915237. (在新窗口中打开)Google Scholar
IF0
PREAI
分享收藏Yue, P., F. Gao, B. Shangguan, and Z. Yan. 2020. “A Machine Learning Approach for Predicting Computational Intensity and Domain Decomposition in Parallel Geoprocessing.” International Journal of Geographical Information Science 34 (11): 2243–2274. https://doi.org/10.1080/13658816.2020.1730850. (Open in a new window)Web of Science ®(Open in a new window)Google ScholarYue, P., 高峰, 上官博, and 严震. 2020. “一种用于预测并行地理处理中计算强度和领域分解的机器学习方法。” 地理信息科学国际期刊 34 (11): 2243–2274. https://doi.org/10.1080/13658816.2020.1730850. (在新窗口中打开)Web of Science ®(在新窗口中打开)谷歌学术
IF0
PREAI
分享收藏Zhou, C., Z. Chen, Y. Liu, F. Li, L. Cheng, A. Zhu, and M. Li. 2015. “Data Decomposition Method for Parallel Polygon Rasterization Considering Load Balancing.” Computers & Geosciences 85:196–209. https://doi.org/10.1016/j.cageo.2015.09.003. (Open in a new window)Web of Science ®(Open in a new window)Google Scholar周，C.，陈，Z.，刘，Y.，李，F.，程，L.，朱，A.，和李，M.。2015年。“考虑负载平衡的并行多边形光栅化数据分解方法。”《计算机与地球科学》85卷：196-209。https://doi.org/10.1016/j.cageo.2015.09.003。（在新窗口中打开）Web of Science ®（在新窗口中打开）谷歌学术。
IF0
PREAI
分享收藏Eldawy, A., and M. F. Mokbel. 2015. “SpatialHadoop: A MapReduce Framework for Spatial Data.” In 2015 IEEE 31st International Conference on Data Engineering, 1352–1363. Seoul, South Korea: IEEE. https://doi.org/10.1109/ICDE.2015.7113382. (Open in a new window)Google Scholar艾尔达维, A., 和 M. F. 莫克布尔. 2015. “SpatialHadoop: 一种用于空间数据的MapReduce框架.” 在 2015年IEEE第31届国际数据工程会议, 1352–1363. 首尔, 韩国: IEEE. https://doi.org/10.1109/ICDE.2015.7113382. (在新窗口中打开)Google Scholar
IF0
PREAI
分享收藏Goodchild, M. F. 1992. “Geographical Information Science.” International Journal of Geographical Information Systems 6 (1): 31–45. https://doi.org/10.1080/02693799208901893. (Open in a new window)Web of Science ®(Open in a new window)Google Scholar古德child, M. F. 1992. “地理信息科学。” 国际地理信息系统杂志 6 (1): 31–45. https://doi.org/10.1080/02693799208901893. (在新窗口中打开) Web of Science ®(在新窗口中打开)谷歌学术
IF0
PREAI
分享收藏Shohdy, S., Y. Su, and G. Agrawal. 2015. “Load Balancing and Accelerating Parallel Spatial Join Operations Using Bitmap Indexing.” In 2015 IEEE 22nd International Conference on High Performance Computing (HiPC), 396–405. Bengaluru, India: IEEE. https://doi.org/10.1109/HiPC.2015.43. (Open in a new window)Google ScholarShohdy, S., Y. Su, and G. Agrawal. 2015. “基于位图索引的负载均衡与并行空间连接操作加速。” 2015年第22届国际高性能计算会议（HiPC），第396-405页。印度班加罗尔：IEEE。https://doi.org/10.1109/HiPC.2015.43. (在新窗口中打开)Google Scholar
IF0
PREAI
分享收藏
查看更多内容