通过考虑拓扑关系来组织信息，实现流域划分的并行算法

《Environmental Modelling & Software》：Parallel algorithm of watershed delineation by considering the topological relationship into information organisation

提出一种基于数据分区的并行流域划分算法，通过改进SFR编码规则和数据组织策略，显著降低内存占用（6.13%-59.68%），在澳大利亚大规模数据测试中效率优于Hiep-Thuan算法11.84%。

　　在地球科学和地理信息系统的研究中，流域边界识别是一个关键环节。流域不仅决定了地表水的流动路径，还与地形、地质和气候等因素密切相关，影响着整个区域的水文过程和地貌演变。随着遥感技术的不断进步，高分辨率的数字高程模型（DEM）被广泛应用于流域分析，从而产生了更大规模和更精确的数据集。然而，这些数据集的体积也随之迅速增长，使得传统的流域划分方法在处理大规模数据时面临严峻的挑战。尤其是在计算机内存容量有限的情况下，如何在不牺牲计算效率的前提下，实现对大规模数据的高效处理，成为当前研究的重要方向。

当前，许多流域划分算法主要依赖于流方向矩阵（Flow Direction Matrix, FDM）来构建流域结构。例如，D8算法是一种经典方法，它通过计算每个栅格单元的水流方向，逐步构建流域边界。然而，随着数据分辨率的提高，流方向矩阵的体积也在不断膨胀，这使得传统的算法在处理大规模数据时，容易受到内存限制的影响。为了应对这一问题，近年来出现了一些基于数据分区的并行流域划分方法，如WDG、MESHED和Hiep-Thuan算法。这些方法通过将数据集划分为多个小块，以降低内存占用并提高计算效率。然而，这些方法在实际应用中仍存在一定的局限性，例如在数据分区过程中可能导致上游和下游信息的分离，从而增加算法复杂度和任务执行时间。

针对这一问题，本文提出了一种新的并行流域划分方法。该方法通过改进子第一轮（Sub-First-Round, SFR）流域编码规则，并采用了一种新的数据组织策略，有效降低了内存使用量，同时提升了计算效率。在传统的SFR流域划分方法中，每个数据块内的流域ID通常是独立存储的，这可能导致不必要的内存消耗。此外，由于每个数据块内的流域结果是以离散的栅格结构存储的，当需要为最终流域ID进行分配时，可能会产生冗余的查询，从而影响计算效率。因此，本文通过将SFR流域ID与数据块ID进行关联，并确保所有数据块内的流域ID从同一起点开始，从而减少了内存使用，同时提高了数据处理的效率。

在实验过程中，我们使用了澳大利亚大陆的高分辨率流方向矩阵数据，并将其划分为多个子块。每个子块的大小为6,000×6,000，整个矩阵被分割为7×9共63个子块。所有子块按照从左到右、从上到下的顺序进行编号，并依次处理。通过对这些子块进行处理，我们提取了982,436个SFR流域，并将其合并为773,809个最终流域。实验结果表明，与传统的WDG和MESHED算法相比，本文提出的方法在内存使用上显著减少，分别降低了6.13%至59.68%。虽然在计算速度上略慢于WDG和MESHED，但这种速度上的牺牲是必要的，因为数据分区有助于克服内存限制。

此外，本文还探讨了不同数据块大小对算法性能的影响。我们进行了五组实验，分别使用了500×500、1,000×1,000、2,000×2,000、3,000×3,000和6,000×6,000的数据块大小。结果显示，随着数据块大小的增加，算法的计算效率有所提高，但内存使用量也随之增加。因此，我们需要在数据块大小的选择上找到一个平衡点，既能够降低内存使用，又能够保证计算效率。在本文的实验中，我们选择了6,000×6,000的数据块大小，因为它能够提供较高的计算效率，同时避免了内存的过度占用。

为了验证本文提出的方法的有效性，我们使用了MERIT_Basins数据集作为参考数据。该数据集包含了全球范围内的流域信息，是当前较为权威的流域划分数据源之一。通过对本文方法和MERIT_Basins数据集的对比分析，我们发现，本文提出的方法在流域划分的准确性上与MERIT_Basins数据集相当，甚至在某些方面表现更优。此外，本文方法在计算效率和内存使用方面也具有显著优势，能够更好地适应大规模数据处理的需求。

总的来说，本文提出的方法在处理大规模流域划分任务时，具有较高的计算效率和较低的内存使用量。通过改进SFR流域编码规则和数据组织策略，该方法能够在不牺牲精度的前提下，有效应对大规模数据带来的计算挑战。随着遥感技术的不断进步和高分辨率DEM数据的广泛应用，流域划分任务的规模和复杂度将持续增加。因此，开发更加高效、内存友好的并行流域划分方法，将有助于推动地球科学和地理信息系统的研究发展。本文的研究成果为相关领域的研究提供了新的思路和方法，同时也为未来的流域划分任务提供了技术支持和实践参考。