一种格网树与KD树组合的水深数据索引方法

A Data Retrieve Method Based on Grid Tree and K-Dimension Tree

针对当前构建高精度数字水深模型中常用的格网数据索引方法,在海量数据管理中存在因树的规模限制而导致检索效率低的问题,提出了一种格网树与 KD 树( K-Dimension,KD)组合的水深数据索引方法。首先,利用格网将水深源数据分割为网状的数据块,构建出数据块的格网树;其次,构建各数据块的 KD 树,实现对数据块中任意数据的快速索引;最后,通过快速定位数据块,查找其所在 KD 树的位置,实现对海量数据的快速检索。实验结果表明:①与格网树相比,本文所提组合检索方法的检索效率随检索树规模的变化不明显;②在相同的数据量下,组合树的检索效率要普遍高于格网树方法。

To solve the problem that the retrieve method of grid tree which is widely used in high precision DDM construction is inefficient when the data mass is huge,a data retrieve method combined with gird tree and k-dimension tree ( KD) is presented.Firstly,the source data is divided into data blocks,and the data blocks are stored in the grid tree. Then,each of the data blocks is organized by KD Trees to achieve a high retrieve efficiency.Finally,each water depth can be retrieved efficiently by finding data block and searching the KD Tree. Results show that: the changes of the retrieve efficiency of this method are not obvious;the combined tree proposed in the article is more efficient than grid tree with same grid scale.