• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于地理空间大数据的高效索引与检索算法

赵慧慧, 赵凡, 陈仁海, 冯志勇

赵慧慧, 赵凡, 陈仁海, 冯志勇. 基于地理空间大数据的高效索引与检索算法[J]. 计算机研究与发展, 2020, 57(2): 333-345. DOI: 10.7544/issn1000-1239.2020.20190565
引用本文: 赵慧慧, 赵凡, 陈仁海, 冯志勇. 基于地理空间大数据的高效索引与检索算法[J]. 计算机研究与发展, 2020, 57(2): 333-345. DOI: 10.7544/issn1000-1239.2020.20190565
Zhao Huihui, Zhao Fan, Chen Renhai, Feng Zhiyong. Efficient Index and Query Algorithm Based on Geospatial Big Data[J]. Journal of Computer Research and Development, 2020, 57(2): 333-345. DOI: 10.7544/issn1000-1239.2020.20190565
Citation: Zhao Huihui, Zhao Fan, Chen Renhai, Feng Zhiyong. Efficient Index and Query Algorithm Based on Geospatial Big Data[J]. Journal of Computer Research and Development, 2020, 57(2): 333-345. DOI: 10.7544/issn1000-1239.2020.20190565

基于地理空间大数据的高效索引与检索算法

基金项目: 国家自然科学基金项目(61702357,61672377);深圳市科技创新委员会学科布局项目(JCYJ20170816093943197);天津市自然科学基金项目(18JCQNJC00300);天津大学北洋学者青年骨干教师项目(2019XRG-0004)
详细信息
  • 中图分类号: TP311

Efficient Index and Query Algorithm Based on Geospatial Big Data

Funds: This work was supported by the National Natural Science Foundation of China (61702357, 61672377), the Shenzhen Science and Technology Foundation (JCYJ20170816093943197), the Natural Science Foundation of Tianjin (18JCQNJC00300), and the Beiyang Scholar Foundation of Tianjin University (2019XRG-0004).
  • 摘要: 近年来,随着智能目标识别、电子传感器、协同控制以及计算机网络等先进技术的快速发展,智能交通系统实现了质的飞越,现代智能交通系统可以实现车、路、云端于一体的智能交通运输管理平台.但智能交通系统依赖于每天产生的大量的2维地理空间信息数据,因此,如何对大规模的地理空间数据进行高效的存储和查询对智能交通系统未来的普及和发展具有重要意义.然而,由于城市交通信息的复杂性、数据量大、更新速度快等特征,当前的空间索引技术很难针对2维地理空间信息数据进行高效的检索.为了优化空间大数据下2维地理空间信息数据的存储组织结构、提高检索效率,提出了一种对2维地理空间信息数据进行多层切片递归的空间索引树构造算法(multi-layer slice recursive, MSR).提出的算法首先对地图数据第1维度进行排序划分切片,生成FD(first division)切片;然后对FD切片中的地图数据进行第2维度排序,生成SD(second division)切片,在SD切片中对当前切片和相邻切片划分空间对象;最后对空间对象长度与节点容量比较进行数据聚类操作,通过判断所有切片是否完成聚类操作,自下而上递归生成MSR 树.实验表明,MSR算法构建的2维空间存储结构的查询性能优于现在最具代表性的空间索引技术基于R树的批量加载算法(sort tile recursive, STR)、STR-网格混合算法(str-grid)及高效几何范围查询算法(efficient geometric range query, EGRQ).
    Abstract: In recent years, with the rapid development of advanced technologies such as intelligent target recognition, electronic sensors, collaborative control and computer networks, intelligent transportation systems have achieved qualitative leapfrogging. Modern intelligent transportation systems can realize intelligent transportation of vehicles, roads and clouds management platform. However, the intelligent transportation system relies on a large amount of two-dimensional geospatial information data generated every day. Therefore, how to efficiently store and query large-scale geospatial data is of great significance for the future popularization and development of the intelligent transportation system. However, due to the complexity of urban traffic information, large amount of data, and fast update speed, the current spatial indexing technology is difficult to efficiently search for two-dimensional geospatial information data. In order to optimize the storage organization structure of two-dimensional geospatial information data under spatial big data and improve retrieval efficiency, this paper proposes a spatial index tree construction algorithm for multi-layer slice recursion of two-dimensional geospatial information data (multi-layer slice recursive, MSR). The proposed algorithm first sorts and divides the first dimension of the map data to generate FD slices. Then, the second dimension of the map data in the FD slice is sorted to generate SD slices, and in the SD slice, the current slice and the adjacent slices are divided into spatial objects. Finally, data clustering operation is performed on the comparison between the length of the spatial object and the node capacity, and the MSR Tree is recursively generated from the bottom up by judging whether all the slices complete the clustering operation. Experimental results show that the query performance of the 2-dimensional space storage structure constructed by the MSR algorithm is better than the most representative spatial indexing technology based on the R-tree batch-loading algorithm (sort tile recursive, STR), STR-grid hybrid algorithm (str-grid), and efficient geometric range query (EGRQ).
  • 期刊类型引用(22)

    1. 李鹏,林显,曾旭川. 基于智能索引算法的集控设备事故辅助预警方法研究. 电子设计工程. 2024(05): 131-135 . 百度学术
    2. 何远景,李光龙. 基于多级索引表的金融业务数据库精准查询方法. 安阳工学院学报. 2024(02): 60-64 . 百度学术
    3. 苏蕊,王亚婷,闫润珍,王悦. 基于近似匹配模型的电网多模态数据检索研究. 电子设计工程. 2024(07): 153-157 . 百度学术
    4. 蓝晓东,赵敏彤,黄欣,肖勇. 基于H型指数的AI多维知识地图信息检索研究. 自动化技术与应用. 2024(06): 112-115 . 百度学术
    5. 窦雪倩,王文兵,刘美琪. 面向电磁态势的空间网格处理方法研究. 舰船电子对抗. 2024(05): 70-74 . 百度学术
    6. 王永志,李逸清,康念坤,王宝娟,杨梦茜,陈健. 基于GIS的农地权属公示图自动生成方法. 苏州科技大学学报(自然科学版). 2024(04): 114-119 . 百度学术
    7. 赖欣,梁昌盛,朱美玲. 基于时空数据模型的障碍物数据集数据查询与应用研究. 航空工程进展. 2023(01): 165-174 . 百度学术
    8. 马芳平,李林,郭金婷,柳玉兰,徐镭梦. 基于粒子群算法的科技创新数据检索系统设计. 电子设计工程. 2023(15): 66-69+74 . 百度学术
    9. 孙妍,张俊超,薛峪峰. 基于流量检测的目标大数据快速检索系统设计. 电子设计工程. 2023(17): 182-186 . 百度学术
    10. 余豪东,陈玉明,吴克寿,韩锋钢. 决策粒K均值聚类算法. 闽南师范大学学报(自然科学版). 2023(03): 1-13 . 百度学术
    11. 李雪琛,张齐. 开源网络空间大数据暴力破解攻击识别算法设计. 吉林大学学报(信息科学版). 2023(06): 1086-1092 . 百度学术
    12. 胡媛媛,江春然,甘杜芬. 基于群体智能算法的大数据分布式存储方法. 计算机仿真. 2023(11): 447-451 . 百度学术
    13. 方圆,王丽珍,王晓璇,杨培忠. 基于空间占有度的主导并置模式挖掘. 计算机研究与发展. 2022(02): 264-281 . 本站查看
    14. 蒋贞慧. 基于多层感知学习的工程档案大数据检索系统设计. 自动化与仪器仪表. 2022(02): 69-72 . 百度学术
    15. 焦洋洋,刘平芝,熊顺,徐道柱. 基于自然格网索引的多尺度面实体增量级联更新方法. 地球信息科学学报. 2022(05): 851-863 . 百度学术
    16. 王丹,王玫. 一种适用于内部信息统筹与服务对像信息快速检索仿真设计. 粘接. 2022(11): 169-173 . 百度学术
    17. 杨凤丽,李娜,刘仁芬. 基于多级索引的高维数据近似最近邻搜索. 计算机仿真. 2022(11): 398-401 . 百度学术
    18. 朱小龙,谢忠. 基于机器学习的地理空间数据抽取算法. 吉林大学学报(工学版). 2021(03): 1011-1016 . 百度学术
    19. 陶建平,曹霞. 云环境下多核仿真平台虚拟任务数据索引. 计算机仿真. 2021(11): 389-393 . 百度学术
    20. 李盼盼,赵浩,林慧恩. 基于相似树查询的隐私大数据定向检索算法. 计算机仿真. 2021(11): 429-432+437 . 百度学术
    21. 陈伊玲. 基于地理空间大数据的复合空间索引. 测绘通报. 2021(S2): 276-279+284 . 百度学术
    22. 廖芳芳,裴春营,李永峰. 基于最高层级的影像分布式切片技术研究. 计算机产品与流通. 2020(10): 38-39 . 百度学术

    其他类型引用(12)

计量
  • 文章访问数:  1202
  • HTML全文浏览量:  6
  • PDF下载量:  797
  • 被引次数: 34
出版历程
  • 发布日期:  2020-01-31

目录

    /

    返回文章
    返回