APP下载

基于Hilbert-R树分级索引的时空查询算法

2018-11-22侯海耀钱育蓉英昌甜卢学远

计算机应用 2018年10期

侯海耀,钱育蓉,英昌甜,2,张 晗,卢学远,赵 燚

(1.新疆大学 软件学院,乌鲁木齐830008; 2.新疆大学 电气工程学科博士后流动站,乌鲁木齐 830046;3.新疆大学 信息科学与工程学院, 乌鲁木齐 830046)(*通信作者电子邮箱qyr@xju.edu.cn)

0 引言

矢量时空数据高效组织管理是空间数据应用的关键技术,空间索引是实现矢量时空数据高效检索的关键[1-3]。空间、时间、属性作为时空大数据的三个基本特征[4],如何描述和表达空间实体及其相互关系的时空变化,成为亟待解决的热点问题。

近年来,树形空间索引技术结合聚类技术来探讨空间索引技术的研究成为热门,对空间数据集进行有效聚类,其结果对构造高效的空间索引具有很大帮助[5],但从时空查询角度出发,同时考虑所查询数据的时间维特征及各空间要素合理组织的研究较少,还不能很好地满足时空应用中对时空高效查询的需求。文献[6-8]侧重从空间数据分布的特点出发,采用聚类算法与R树结合构建索引,提高了空间查找效率;文献[9]提出基于Redis的缓存敏感R+树(Cache Conscious R+Tree,CCR+),其查询效率较Oracle 10g的管理系统有较大的提升,但这些研究均未考虑对时间维建立索引。

基于以上问题,本文利用Hilbert曲线较为稳定的离散度分布特点[10],分割并编码空间要素;利用动态确定K值的聚类算法,将聚类结果参与到Hilbert-R树构建当中,对矢量时空数据采用Redis丰富的数据结构进行分层组织存储;结合时间和聚类结果分层结构建立分级索引机制。在此基础上,进行数据密集型测试、时空范围查询及目标矢量对象查询,在真实数据集上进行,结果表明,提出的时间结合聚类分层组织存储及分级索引机制在时空查询性能方面较CCR+树有显著提升。……

登录APP查看全文