基于NoSQL的分布式R*树索引构建与应用研究  

Research on Construction and Application of Distributed R*-Tree Index Based on NoSQL Database

作　　者：孙乐乐 金宝轩 SUN Le-le;JIN Bao-xuan(Faculty of Geography,Yunnan Normal University,Kunming 650500;Department of Natural Resources of Yunnan Province,Kunming 650224,China)

机构地区：[1]云南师范大学地理学部,云南昆明650500 [2]云南省自然资源厅,云南昆明650224

出　　处：《地理与地理信息科学》2021年第5期9-15,22,共8页Geography and Geo-Information Science

基　　金：国家自然科学基金地区科学基金项目“顾及时空计算复杂度的云资源动态扩展和负载均衡研究”(41661086)。

摘　　要：针对当前空间填充曲线(Space-Filling Curve,SFC)类NoSQL空间索引对复杂几何索引支持较差、字典序映射成本较高等问题,该文提出一种基于NoSQL的分布式R*树空间索引。基于NoSQL的分区存储模式,通过优化后的STR(Sort Tile Recursive)均衡策略配置分布式R*树,借助R*树路径实现索引、数据的编码存储,并提出批处理模式的索引并行构建方法;借助NoSQL的SSPT(Server-Side Scripts)计算框架构建查询、应用并行处理机制。选用土地利用、规划数据进行对比实验,结果表明:该索引的平均构建耗时为GeoMesa的30.0%,500万量级下耗时仅为GeoMesa的18.6%;执行MBR查询、多边形几何查询、最邻近查询的平均耗时分别为GeoMesa的26.5%、53.4%、52.3%;执行自然资源开发项目合规性审查应用的平均耗时分别为ArcGIS、GeoMesa的10.6%、72.7%。该索引在构建性能、空间查询性能以及应用性能方面均具有优越性,能为基于NoSQL的海量空间数据高性能存储、检索与应用提供一种优良解决方案。Currently,the shortcomings of SFC-based NoSQL spatial indexes such as high cost in lexicographic order mapping and poor support for complex geometry(polyline and polygon)index can degrade the spatial query and application performance.To solve this problem,a NoSQL distributed R*-tree index is presented in this paper.Based on the NoSQL′s partition storage,this paper proposes an improved STR data allocation algorithm to configure distributed R*-trees,designs a R*-tree path based spatial encoding scheme for R*-trees and spatial objects storage,and implements a parallel distributed R*-tree building method in batch mode.Meanwhile,SSPT-based spatial query and application parallel processing mechanism are realized for low-latency,elastic server-side processing.Using land-use and planning data,comparison experiments are conducted and the results show that the average building time for the proposed index is 30.0%of the GeoMesa,and this ratio decreases to 18.6%as data volume reaches 5 million;the average execution time for MBR,polygon range query and nearest neighbor query with the proposed index respectively accounts for 26.5%,53.4%and 52.3%of the GeoMesa;the average time cost for compliance review of natural resource development application with the proposed index is 10.6%,72.7%of ArcGIS and GeoMesa respectively.These indicate the superiority of the proposed distributed R*-tree index in index construction,spatial query and application performance,which provides a feasible and high-efficiency solution for NoSQL to store index spatial objects and support various spatial applications.

关 键 词：NOSQL R*树 空间索引 内存式索引 空间查询 STR 

分 类 号：P208[天文地球—地图制图学与地理信息工程]