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

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.