PAGE: Parallel Scalable Regionalization Framework
PAGE: Parallel Scalable Regionalization Framework
复制标题
DOI：
10.1145/3611011
复制
发表时间：
2023-07
影响因子：
1.9
通讯作者：
Hussah Alrashid;Yongyi Liu;A. Magdy
中科院分区：
文献类型：
--
作者：
Hussah Alrashid;Yongyi Liu;A. Magdy
区域化技术将空间区域分组为一组均匀区域，以分析空间现象并得出结论。最近的区域化问题称为 MP 区域，它通过在区域级别强制执行用户定义的约束来对空间区域进行分组，以产生最大数量的区域。 MP 区域问题是 NP 困难的。现有的 MP 区域近似算法由于其高计算成本和固有的集中式数据处理方法而无法扩展到大型数据集。本文介绍了一个并行可扩展区域化框架 (PAGE)，以支持大型数据集上的 MP 区域。拟议的框架分两个阶段运行。第一阶段通过随机搜索找到初始解决方案，第二阶段通过高效的启发式搜索改进该解决方案。为了有效地构建初始解决方案，我们扩展了传统的空间分区技术，以在不违反空间约束的情况下实现并行区域构建。此外，我们通过调整随机区域选择来权衡运行时间和区域同质性，从而优化区域构建效率和质量。实验评估表明，与最先进的技术相比，我们的框架在有效支持更大数量级的数据集方面具有优越性，同时还能生成高质量的解决方案。
Regionalization techniques group spatial areas into a set of homogeneous regions to analyze and draw conclusions about spatial phenomena. A recent regionalization problem, called MP-regions, groups spatial areas to produce a maximum number of regions by enforcing a user-defined constraint at the regional level. The MP-regions problem is NP-hard. Existing approximate algorithms for MP-regions do not scale for large datasets due to their high computational cost and inherently centralized approaches to process data. This article introduces a parallel scalable regionalization framework (PAGE) to support MP-regions on large datasets. The proposed framework works in two stages. The first stage finds an initial solution through randomized search, and the second stage improves this solution through efficient heuristic search. To build an initial solution efficiently, we extend traditional spatial partitioning techniques to enable parallelized region building without violating the spatial constraints. Furthermore, we optimize the region building efficiency and quality by tuning the randomized area selection to trade off runtime with region homogeneity. The experimental evaluation shows the superiority of our framework to support an order of magnitude larger datasets efficiently compared to the state-of-the-art techniques while producing high-quality solutions.