面向动态关联数据的高效稀疏图索引方法

doi:10.11947/j.AGCS.2020.20190287

测绘学报 ›› 2020, Vol. 49 ›› Issue (6): 681-691.doi: 10.11947/j.AGCS.2020.20190287

面向动态关联数据的高效稀疏图索引方法

朱庆¹, 冯斌¹, 李茂粟¹, 陈媚特¹, 徐肇文¹, 谢潇^2,3, 张叶廷⁴, 刘铭崴^1,3, 黄志勤⁵, 冯义从⁵

1. 西南交通大学地球科学与环境工程学院, 四川成都 611756;
2. 浙江中海达空间信息技术有限公司, 浙江湖州 313299;
3. 四川视慧智图空间信息技术有限公司, 四川成都 610036;
4. 武汉大学测绘遥感信息工程国家重点实验室, 湖北武汉 430079;
5. 四川省自然资源厅信息中心, 四川成都 610072

收稿日期:2019-07-08 修回日期:2020-03-12 出版日期:2020-06-20 发布日期:2020-06-28
作者简介:朱庆(1966-),男,博士,长江学者特聘教授,博士生导师,研究方向为虚拟地理环境与三维GIS。E-mail:zhuq66@263.net
基金资助:
国家重点研发计划（2018YFB0505404）；国家自然科学基金（41871314）

An efficient sparse graph index method for dynamic and associated data

ZHU Qing¹, FENG Bin¹, LI Maosu¹, CHEN Meite¹, XU Zhaowen¹, XIE Xiao^2,3, ZHANG Yeting⁴, LIU Mingwei^1,3, HUANG Zhiqin⁵, FENG Yicong⁵

1. Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 611756, China;
2. Zhejiang Hi-Target Spatial Information Technology Co. Ltd., Huzhou 313299, China;
3. Sichuan Smart Map Spatial Information Technology Co. Ltd., Chengdu 610036, China;
4. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
5. Information Center of Department of Nature Resources of Sichuan Province, Chengdu 610072, China

Received:2019-07-08 Revised:2020-03-12 Online:2020-06-20 Published:2020-06-28
Supported by:
The National Key Research and Development Program of China (No. 2018YFB0505404);The National Natural Science Foundation of China (No. 41871314)

摘要/Abstract

摘要： 为了高效组织管理日益增加的智能感知和关联关系数据，满足多层次任务对多模态场景数据多维特征计算和关联挖掘的需求，针对现有树结构外存索引方法存在的磁盘I/O密集、处理效率低、对关联关系支持弱的瓶颈问题，提出了一种时空关系稀疏图索引方法。设计了一种基于内存图模型的时空索引结构，将多模态场景数据抽象为图的节点和边，支持时间、空间以及关联关系的高效组织，并基于稀疏矩阵进行时空关系图索引的内存表达和存储；以多维树索引为例进行了索引构建以及多模式查询试验。试验结果表明，本文方法在索引生成、时空查询和复杂时空关系查询效率等方面均优于对比方法，支持动态关联的多模态场景数据实时高性能处理和低延迟访问。

关键词: 时空索引, 内存图模型, 稀疏矩阵, 动态关联数据, 场景数据组织

Abstract: In order to efficiently organize and manage the increasing real-time sensor data and associations, and satisfy the requirements of multi-level tasks for multi-dimensional feature calculation and association mining of multi-modal scene data, a spatiotemporal sparse graph index method is proposed for the bottleneck problems of disk I/O-intensive, low processing efficiency and weak support for associations existing in the tree structure based external indexing methods. Firstly, a spatiotemporal index structure based on in-memory graph model is designed, which abstracts multi-modal scene data into nodes and edges of graph and supports efficient organization of time, location and associations of multi-modal scene data. Then, a sparse matrix based method of in-memory representation and storage for spatiotemporal graph index is presented. Finally, taking the multi-dimensional tree index as an example, the index construction and multi-model query experiments are carried out. The experimental results show that the method is superior to the contrast method in several aspects, such as generation efficiency, query performance, and then supports real-time high-performance processing of dynamic and associated multi-modal scene data with low latency access.

Key words: spatiotemporal index, in-memory graph model, sparse matrix, dynamic and associated data, scene data organization

中图分类号:

P208

朱庆, 冯斌, 李茂粟, 陈媚特, 徐肇文, 谢潇, 张叶廷, 刘铭崴, 黄志勤, 冯义从. 面向动态关联数据的高效稀疏图索引方法[J]. 测绘学报, 2020, 49(6): 681-691.

ZHU Qing, FENG Bin, LI Maosu, CHEN Meite, XU Zhaowen, XIE Xiao, ZHANG Yeting, LIU Mingwei, HUANG Zhiqin, FENG Yicong. An efficient sparse graph index method for dynamic and associated data[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 681-691.

参考文献 29

[1]	FENG Bin, ZHU Qing, LIU Mingwei, et al. An efficient graph-based spatio-temporal indexing method for task-oriented multi-modal scene data organization[J]. ISPRS International Journal of Geo-Information, 2018, 7(9):371.
[2]	朱庆, 付萧. 多模态时空大数据可视分析方法综述[J]. 测绘学报, 2017, 46(10):1672-1677. DOI:10.11947/j.AGCS.2017.20170286. ZHU Qing, FU Xiao. The review of visual analysis methods of multi-modal spatio-temporal big data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1672-1677. DOI:10.11947/j.AGCS.2017.20170286.
[3]	刘铭崴, 朱庆, 朱军, 等. 多模态时空数据多层次可视化任务模型[J]. 测绘学报, 2018, 47(8):1098-1104. DOI:10.11947/j.AGCS.2018.20180104. LIU Mingwei, ZHU Qing, ZHU Jun, et al. The multi-level visualization task model for multi-modal spatio-temporal data[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(8):1098-1104. DOI:10.11947/j.AGCS.2018.20180104.
[4]	CHEN C L P, ZHANG Chunyang. Data-intensive applications, challenges, techniques and technologies:a survey on big data[J]. Information Sciences, 2014, 275:314-347.
[5]	陆锋, 周成虎. 一种基于Hilbert排列码的GIS空间索引方法[J]. 计算机辅助设计与图形学学报, 2001, 13(5):424-429. LU Feng, ZHOU Chenghu. A GIS spatial indexing approach based on Hilbert ordering code[J]. Journal of Computer-Aided Design & Computer Graphics, 2001, 13(5):424-429.
[6]	REZGUI A, MALIK Z, XIA Jizhe, et al. Data-intensive spatial indexing on the clouds[J]. Procedia Computer Science, 2013, 18:2615-2618.
[7]	华一新. 全空间信息系统的核心问题和关键技术[J]. 测绘科学技术学报, 2016, 33(4):331-335. HUA Yixin. The core problems and key technologies of pan-spatial information system[J]. Journal of Geomatics Science and Technology, 2016, 33(4):331-335.
[8]	龚俊, 柯胜男, 朱庆, 等. 一种集成R树、哈希表和B树的高效轨迹数据索引方法[J]. 测绘学报, 2015, 44(5):570-577. DOI:10.11947/j.AGCS.2015.20130520. GONG Jun, KE Shengnan, ZHU Qing, et al. An efficient trajectory data index integrating R-tree, hash and B-tree[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5):570-577. DOI:10.11947/j.AGCS.2015.20130520.
[9]	MA Youzhong, RAO Jia, HU Weisong, et al. An efficient index for massive IOT data in cloud environment[C]//CIKM'12 Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Bellevue, WA:ACM, 2012.
[10]	YU Jia, WU Jinxuan, SARWAT M. GeoSpark:a cluster computing framework for processing large-scale spatial data[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Bellevue, WA:ACM, 2015.
[11]	AJI A, WANG Fusheng, VO H, et al. Hadoop-GIS:a high performance spatial data warehousing system over mapreduce[J]. Proceedings of the VLDB Endowment, 2013, 6(11):1009-1120.
[12]	AZQUETA-ALZÚAZ A, PATIÑO-MARTINEZ M, BRONDINO I, et al. Massive data load on distributed database systems over HBase[C]//Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). Madrid, Spain:IEEE, 2017.
[13]	NISHIMURA S, DAS S, AGRAWAL D, et al. MD-HBase:a scalable multi-dimensional data infrastructure for location aware services[C]//Proceedings of 2011 IEEE International Conference on Mobile Data Management. Lulea, Sweden:IEEE, 2011.
[14]	ELDAWY A, ALARABI L, MOKBEL M F. Spatial partitioning techniques in SpatialHadoop[J]. Proceedings of the VLDB Endowment, 2015, 8(12):1602-1605.
[15]	MOKBEL M F, GHANEM T M, AREF W G. Spatio-temporal access methods[J]. IEEE Data Engineering Bulletin, 2003, 26(2):40-49.
[16]	NGUYEN-DINH L V, AREF W G, MOKBEL M. Spatio-temporal access methods:part 2(2003-2010)[J]. IEEE Data Engineering Bulletin, 2010, 33(1):46-55.
[17]	LI Shen, HU Shaohan, GANTI R, et al. Pyro:a spatial-temporal big-data storage system[C]//Proceedings of the USENIX Annual Technical Conference. Bellevue, WA:ACM, 2015.
[18]	KILIMCI P, KALIPSIZ O. Indexing of spatiotemporal data:a comparison between sweep and Z-order space filling curves[C]//International Conference on Information Society (i-Society 2011). London, UK:IEEE, 2011.
[19]	LIZARDO L E O, DAVIS JR C A. A PostGIS extension to support advanced spatial data types and integrity constraints[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Bellevue, WA:ACM, 2017.
[20]	丁治明, 高需. 面向物联网海量传感器采样数据管理的数据库集群系统框架[J]. 计算机学报, 2012, 35(6):1175-1191. DING Zhiming, GAO Xu. A database cluster system framework for managing massive sensor sampling data in the internet of things[J]. Chinese Journal of Computers, 2012, 35(6):1175-1191.
[21]	FERNANDES D, BERNARDINO J. Graph databases comparison:AllegroGraph, ArangoDB, InfiniteGraph, Neo4J, and OrientDB[C]//Proceedings of the 7th International Conference on Data Science, Technology and Applications. Bellevue, WA:ACM, 2018.
[22]	VUKOTIC A, WATT N. Neo4J in action[M]. Shelter Island, NY:Manning Publications Co., 2015.
[23]	ELBATTAH M, ROUSHDY M, AREF M, et al. Large-scale ontology storage and query using graph database-oriented approach:the case of Freebase[C]//Proceedings of 2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS). Cairo, Egypt:IEEE, 2016.
[24]	XIAO Zhuoling, WEN Hongkai, MARKHAM A, et al. Indoor tracking using undirected graphical models[J]. IEEE Transactions on Mobile Computing, 2015, 14(11):2286-2301.
[25]	ZHANG Xiaomin, SONG Wei, LIU Liming. An implementation approach to store GIS spatial data on NoSQL database[C]//Proceedings of the 22nd International Conference on Geoinformatics. Kaohsiung, Taiwan:IEEE, 2014.
[26]	XU Xiaofeng, XIONG Li, SUNDERAM V. D-grid:an in-memory dual space grid index for moving object databases[C]//Proceedings of the 17th IEEE International Conference on Mobile Data Management (MDM). Porto, Portugal:IEEE, 2016.
[27]	ANGLES R. A comparison of current graph database models[C]//Proceedings of the 28th IEEE International Conference on Data Engineering Workshops. Arlington, VA:IEEE, 2012.
[28]	华一新, 周成虎. 面向全空间信息系统的多粒度时空对象数据模型描述框架[J]. 地球信息科学学报, 2017, 19(9):1142-1149. HUA Yixin, ZHOU Chenghu. Description frame of data model of multi-granularity spatio-temporal object for pan-spatial information system[J]. Journal of Geo-information Science, 2017, 19(9):1142-1149.
[29]	周成虎. 全空间地理信息系统展望[J]. 地理科学进展, 2015, 34(2):129-131. ZHOU Chenghu. Prospects on pan-spatial information system[J]. Progress in Geography, 2015, 34(2):129-131.

面向动态关联数据的高效稀疏图索引方法

An efficient sparse graph index method for dynamic and associated data

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 29

相关文章 3

编辑推荐

Metrics

本文评价

[1]	吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379.
[2]	郑茂腾, 张永军, 朱俊峰, 熊小东, 周顺平. 一种快速有效的大数据区域网平差方法[J]. 测绘学报, 2017, 46(2): 188-197.
[3]	龚俊, 柯胜男, 朱庆, 张叶廷. 一种集成R树、哈希表和B^*树的高效轨迹数据索引方法[J]. 测绘学报, 2015, 44(5): 570-577.