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

doi:10.11772/j.issn.1001-9081.2018040749

计算机应用 ›› 2018, Vol. 38 ›› Issue (10): 2869-2874.DOI: 10.11772/j.issn.1001-9081.2018040749

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

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

1. 新疆大学软件学院, 乌鲁木齐 830008;
2. 新疆大学电气工程学科博士后流动站, 乌鲁木齐 830046;
3. 新疆大学信息科学与工程学院, 乌鲁木齐 830046

收稿日期:2018-04-12 修回日期:2018-07-08 出版日期:2018-10-10 发布日期:2018-10-13
通讯作者: 钱育蓉
作者简介:侯海耀(1990-),男,山西汾阳人,硕士研究生,主要研究方向:时空数据库索引、遥感图像处理;钱育蓉(1980-),女,山东武城人,教授,博士,CCF高级会员,主要研究方向:网络计算、遥感图像处理;英昌甜(1989-),女,新疆乌鲁木齐人,博士,主要研究方向:图像处理、内存计算;张晗(1987-),男,辽宁本溪人,硕士研究生,主要研究方向:图像处理、模式识别;卢学远(1992-),男,浙江温州人,硕士研究生,CCF会员,主要研究方向:图像处理、机器学习;赵燚(1993-),女,新疆克拉玛依人,硕士研究生,主要研究方向:时空数据库索引、遥感图像处理。
基金资助:
国家自然科学基金资助项目（61562086，61462079）；新疆维吾尔自治区教育厅项目（XJEDU2016S035）；新疆大学博士科研启动基金资助项目（BS150257）；新疆维吾尔自治区教育厅创新团队项目（XJEDU2017T002）。

Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index

HOU Haiyao¹, QIAN Yurong¹, YING Changtian^1,2, ZHANG Han¹, LU Xueyuan¹, ZHAO Yi³

1. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;
2. Postdoctoral Research Station of Electrical Engineering, Xinjiang University, Urumqi Xinjiang 830046, China;
3. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China

Received:2018-04-12 Revised:2018-07-08 Online:2018-10-10 Published:2018-10-13
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61562086, 61462079), the Education Department Project of Xinjiang Uygur Autonomous Region (XJEDU2016S035), the Doctoral Research Startup Fund of Xinjiang University (BS150257), the Funds for Creative Research Groups of Higher Education of Xinjiang Uygur Autonomous Region (XJEDU 2017T002).

摘要/Abstract

摘要： 针对树形空间索引中多路查询及未考虑时间维索引的问题，提出一种结合时间和聚类结果的Hilbert-R树索引构建策略。首先，按照数据采集的周期划分时空数据集，并在此基础上建立时间索引，通过Hilbert曲线对空间数据进行分割编码，将空间坐标映射到一维区间；其次，依据数据要素在空间中的分布，采用动态确定K值的聚类算法，结合聚类结果构建高效的Hilbert-R树空间索引；最后，基于Redis几种常见的键值数据结构，对时空数据的时间属性和聚类结果构建分级索引。在时空范围及目标矢量对象查询的实验中，与缓存敏感R+树（CCR+）相比，所提算法可有效减少时间开销，查询时间平均缩短约25%，对不同密集型数据具有良好的适应性，可更好地支持Redis应用于海量时空数据查询。

关键词: 时空数据, Redis数据库, 聚类算法, Hilbert-R树, 分级索引, 时空范围查询

Abstract: Aiming at the problem of multi-path query in tree-spatial index and not considering temporal index, A Hilbert-R tree index construction scheme combining time and clustering results was proposed. Firstly, according to the periodicity of data collection, the spatial-temporal dataset was divided, and on this basis, a time index was established. The spatial data was partitioned and encoded by the Hilbert curve, and the spatial coordinates were mapped to one-dimensional intervals. Secondly, according to the distribution of the feature object in space, a clustering algorithm using dynamic determination of K value was adopted, to build an efficient Hilbert-R tree spatial index. Finally, based on several common key-value data structures of Redis, the hierarchical indexing mechanism of time attributes and clustering results was built. Compared with the Cache Conscious R+tree (CCR+), the proposed algorithm can effectively reduce the time overhead, and the query time is shortened by about 25% on average in the experiment of spatial-temporal range and target vector object query. It has good adaptability to different intensive data and can better support Redis for massive spatio-temporal data queries.

Key words: spatio-temporal data, Redis database, clustering algorithm, Hilbert-R tree, hierarchical index, spatio-temporal range query

中图分类号:

TP311

侯海耀, 钱育蓉, 英昌甜, 张晗, 卢学远, 赵燚. 基于Hilbert-R树分级索引的时空查询算法[J]. 计算机应用, 2018, 38(10): 2869-2874.

HOU Haiyao, QIAN Yurong, YING Changtian, ZHANG Han, LU Xueyuan, ZHAO Yi. Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index[J]. Journal of Computer Applications, 2018, 38(10): 2869-2874.

参考文献

[1] HE Z, KRAAK M J, HUISMAN O, et al. Parallel indexing technique for spatio-temporal data[J]. ISPRS Journal of Photo Grammetry & Remote Sensing, 2013, 78(4):116-128.
[2] HUANG J, WEI P, YU H, et al. A graph based bi-level index for spatio-temporal data analysis with MapReduce[C]//Proceedings of the Sixth International Symposium on Computational Intelligence and Design. Piscataway, NJ:IEEE, 2014:339-342.
[3] DU N, ZHAN J, ZHAO M, et al. Spatio-temporal data index model of moving objects on fixed networks using HBase[C]//Proceedings of the 2015 IEEE International Conference on Computational Intelligence & Communication Technology. Piscataway, NJ:IEEE, 2015:247-251.
[4] ZHENG L, ZHOU L, ZHAO X, et al. The spatio-temporal data modeling and application based on graph database[C]//Proceedings of the 20174th International Conference on Information Science and Control Engineering. Piscataway, NJ:IEEE, 2017:741-746.
[5] 王冲. 基于Chameleon聚类算法的R树索引方法研究[D].哈尔滨:哈尔滨理工大学,2017.(WANG C. Research on R-tree index method based on Chameleon algorithm clustering[D]. Harbin:Harbin University of Science and Techology,2017.
[6] 胡昱璞, 牛保宁.动态确定K值聚类算法的R-树空间索引构建[J]. 计算机科学与探索, 2016, 10(2):173-181. (HU Y P, NIU B N. R-tree spatial index construction based on dynamical K-value clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(2):173-181.)
[7] 李松, 崔环宇, 张丽平, 等.基于CURE聚类算法的静态R树构建方法[J]. 计算机科学, 2015, 42(10):193-197. (LI S, CUI H Y, ZHANG L P, et al. Static R-tree building method based on cure clustering algorithm[J]. Computer Science, 2015, 42(10):193-197.)
[8] 汪璟玢.一种结合空间聚类算法的R树优化算法[J]. 计算机工程与应用, 2014, 50(5):112-115. (WANG J F. Optimization algorithm for R-tree combining with spatial-clusting[J]. Computer Engineering and Applications, 2014, 50(5):112-115.)
[9] 戚将辉, 张丰, 杜震洪, 等.基于内存数据库的矢量数据存储与空间索引研究[J]. 浙江大学学报(理学版), 2015, 42(3):365-370. (QI J H, ZHNAG F, DU Z H, et al. Research of the land use vector data storage and spatial index based on the main memory database[J]. Journal of Zhejiang University (Science Edition), 2015, 42(3):365-370.)
[10] 罗敬宁, 刘立葳.遥感大数据分布式技术研究与实现[J]. 应用气象学报, 2017, 28(5):621-631. (LUO J N, LIU L W. Research and implementation of remote sensing big data distributed technology[J]. Journal of Applied Meteorological Science, 2017, 28(5):621-631.)
[11] 张翀, 陈晓莹, 史宗麟, 等. HBase时空查询算法研究[J]. 小型微型计算机系统, 2016, 37(11):2409-2415. (ZHANG C, CHEN X Y, SHI Z L, et al. Algorithms for spatio-temporal queries in HBase[J]. Journal of Chinese Computer Systems, 2016, 37(11):2409-2415.)
[12] KIM H I, HONG S, CHANG J W. Hilbert curve-based cryptographic transformation scheme for spatial query processing on outsourced private data[J]. Data & Knowledge Engineering, 2016, 104:32-44.
[13] 田丰, 桂小林, 张学军, 等.基于兴趣点分布的外包空间数据隐私保护方法[J]. 计算机学报, 2014, 37(1):123-138. (TIAN F, GUI X L, ZHANG X J, et al. Privacy-preserving approach for out sourced spatial data based on POI distribution[J]. Chinese Journal of Computers.2014, 37(1):123-138.)
[14] KUMAR K M, REDDY A R M. An Efficient k-means clustering filtering algorithm using density based initial cluster centers[J]. Information Sciences, 2017, 418/419:286-301.
[15] 丁建立, 郑峰弓, 李永华, 等. 基于NoSQL的海量航空物流小文件分布式多级存储方法[J]. 计算机应用研究, 2017, 34(5):1433-1436. (DING J L, ZHENG F G, LI Y H, et al. Method of distributed multi-level storage of massive small files of air logistics based on NoSQL[J]. Application Research of Computers, 2017, 34(5):1433-1436.)
[16] 焦健, 李岩.基于Redis的SVG空间信息可视化数据库[J]. 小型微型计算机系统, 2015, 36(6):1193-1198. (JIAO J, LI Y. SVG spatial visualization database based on Redis[J]. Journal of Chinese Computer Systems, 2015, 36(6):1193-1198.)
[17] KABAKUS A T, KARA R. A performance evaluation of in-memory databases[J]. Journal of King Saud University-Computer and Information Sciences, 2016, 29(4):520-525.
[18] 朱进, 胡斌, 邵华, 等.基于内存数据库Redis的轻量级矢量地理数据组织[J]. 地球信息科学学报, 2014, 16(2):165-172. (ZHU J, HU B, SHAO H, et al. Research of lightweight vector geographic data management based on main memory database Redis[J]. Journal of Geo-information Science, 2014, 16(2):165-172.)

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

Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[2]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[3]	刘黎, 胡海波, 杨涛. 探索会展环境时空数据的可视分析系统[J]. 计算机应用, 2020, 40(9): 2719-2727.
[4]	孙建军, 徐岩. 基于加权改进模糊C均值聚类的欠定混合矩阵估计[J]. 计算机应用, 2020, 40(6): 1769-1773.
[5]	黄伟建, 李丹阳, 黄远. 面向空气质量的时空混合预测模型[J]. 计算机应用, 2020, 40(11): 3385-3392.
[6]	郭茂祖, 张彬, 赵玲玲, 张昱. 基于联合特征和XGBoost的活动语义识别方法[J]. 计算机应用, 2020, 40(11): 3159-3165.
[7]	黄永鑫, 唐雪飞. 基于近邻传播聚类和TANE算法的高校数据中函数依赖的发现[J]. 计算机应用, 2020, 40(1): 90-95.
[8]	毛伊敏, 刘银萍, 梁田, 毛丁慧. 基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘[J]. 计算机应用, 2019, 39(4): 1032-1040.
[9]	丁成, 王秋萍, 王晓峰. 基于广义反向学习的磷虾群算法及其在数据聚类中的应用[J]. 计算机应用, 2019, 39(2): 336-342.
[10]	丁景全, 马博, 李晓. 基于融合时空数据的车辆加油行为多视图深度异常检测框架[J]. 计算机应用, 2019, 39(11): 3370-3375.
[11]	刘晓明, 沈明玉, 侯整风. 基于Levy飞行的萤火虫模糊聚类算法[J]. 计算机应用, 2019, 39(11): 3257-3262.
[12]	叶双, 杨晓敏, 严斌宇. 基于自适应锚定邻域回归的图像超分辨率算法[J]. 计算机应用, 2019, 39(10): 3040-3045.
[13]	王雪菲, 丁维龙. 面向高速公路大数据的短时流量预测方法[J]. 计算机应用, 2019, 39(1): 87-92.
[14]	邱保志, 程栾. 基于拉普拉斯中心性和密度峰值的无参数聚类算法[J]. 计算机应用, 2018, 38(9): 2511-2514.
[15]	邵伦, 周新志, 赵成萍, 张旭. 基于多维网格空间的改进K-means聚类算法[J]. 计算机应用, 2018, 38(10): 2850-2855.