Scholarlink

<p>Depression detection in digital terrain analysis is crucial for surface process modelling. High-resolution satellite imagery has led to an increasing demand for processing ultra-large-scale digital elevation models (DEMs) with billions of grid cells, which has exposed the computational inefficiencies of traditional priority-flood algorithms based on priority queues. While existing research has primarily focused on reducing the data volume in priority-flood’s priority queues, few studies have focused on optimizing the sorting mechanism within these queues. In this paper, we propose a hybrid Hash Red Black Tree (HRBTree) data structure, integrating the efficient insertion capability of hash tables with the ordered key-value maintenance of the RBTree, thereby reconstructing the priority queue architecture of the priority-flood algorithm. Using multi-scale DEM datasets ranging from millions to 1.6&#xa0;billion grid cells, we systematically evaluated the computational efficiency of the enhanced priority-flood algorithm across varying data scales. The experimental results demonstrate that the proposed HRBTree structure exhibits superior adaptability, particularly in ultra-large-scale datasets (&gt; 1&#xa0;billion nodes), achieving a maximum speedup of 49% compared with traditional priority queue structures, which validates the effectiveness of heterogeneous data structure fusion. After modifying three classic priority-flood variants (Wang &amp; Liu, Barnes, and Zhou), the HRBTree demonstrates strong generalizability. Specifically, on billion-scale datasets, the HRBTree-optimized Wang &amp; Liu algorithm achieves a 45.6% speedup (average 35.1%), the Barnes algorithm improves by up to 37.6%, and the Zhou algorithm reaches a 28.2% speedup, confirming the structure’s compatibility with diverse algorithmic frameworks. This study provides critical insights for the engineering application of terrain analysis algorithms and lays the foundation for next-generation high-performance, scalable computing paradigms in terrain analysis systems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Depression detection in billion-scale DEM grids in digital terrain analysis using HRBTree

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月12日

查看全文
  • Lejun Ma,
  • Yue Yuan,
  • Huan Wang,
  • Xingnan Zhang,
  • Yanan Liu,
  • Wei Hu

摘要

Depression detection in digital terrain analysis is crucial for surface process modelling. High-resolution satellite imagery has led to an increasing demand for processing ultra-large-scale digital elevation models (DEMs) with billions of grid cells, which has exposed the computational inefficiencies of traditional priority-flood algorithms based on priority queues. While existing research has primarily focused on reducing the data volume in priority-flood’s priority queues, few studies have focused on optimizing the sorting mechanism within these queues. In this paper, we propose a hybrid Hash Red Black Tree (HRBTree) data structure, integrating the efficient insertion capability of hash tables with the ordered key-value maintenance of the RBTree, thereby reconstructing the priority queue architecture of the priority-flood algorithm. Using multi-scale DEM datasets ranging from millions to 1.6 billion grid cells, we systematically evaluated the computational efficiency of the enhanced priority-flood algorithm across varying data scales. The experimental results demonstrate that the proposed HRBTree structure exhibits superior adaptability, particularly in ultra-large-scale datasets (> 1 billion nodes), achieving a maximum speedup of 49% compared with traditional priority queue structures, which validates the effectiveness of heterogeneous data structure fusion. After modifying three classic priority-flood variants (Wang & Liu, Barnes, and Zhou), the HRBTree demonstrates strong generalizability. Specifically, on billion-scale datasets, the HRBTree-optimized Wang & Liu algorithm achieves a 45.6% speedup (average 35.1%), the Barnes algorithm improves by up to 37.6%, and the Zhou algorithm reaches a 28.2% speedup, confirming the structure’s compatibility with diverse algorithmic frameworks. This study provides critical insights for the engineering application of terrain analysis algorithms and lays the foundation for next-generation high-performance, scalable computing paradigms in terrain analysis systems.