QML：一种混合空间索引结构

崔栋; 温巧燕; 张华; 王华伟

doi:10.11959/j.issn.1000-436x.2021229

您当前的位置：

首页 >

文章列表页 >

QML：一种混合空间索引结构

学术论文 | 更新时间：2024-06-05

- QML：一种混合空间索引结构
- QML: a hybrid spatial index structure
- 通信学报 2021年42卷第12期页码：1-16
- 作者机构：
  
  北京邮电大学网络与交换技术国家重点实验室，北京 100876
- 作者简介：
  
  [ "崔栋（1991- ），男，山东潍坊人，北京邮电大学博士生，主要研究方向为学习索引、移动互联网安全" ]
  [ "温巧燕（1959- ），女，陕西户县人，博士，北京邮电大学教授、博士生导师，主要研究方向为现代密码理论、量子密码与量子信息、网络安全技术等" ]
  [ "张华（1978- ），女，吉林四平人，博士，北京邮电大学副教授、博士生导师，主要研究方向为网络安全、隐私保护等" ]
  [ "王华伟（1989- ），男，河南驻马店人，博士，北京邮电大学在站博士后，主要研究方向为区块链安全、去中心化的身份安全认证技术" ]
- 基金信息：
  
  国家自然科学基金资助项目(62072051);国家自然科学基金资助项目(61976024);国家自然科学基金资助项目(61972048);中央高校基本科研业务费专项资金资助项目(2019XD-A01);教育部区场链核心计划基金资助项目(2020KJ010802)
- DOI：10.11959/j.issn.1000-436x.2021229
  中图分类号： TP392
- 网络出版日期：2021-12，
  
  纸质出版日期：2021-12-25
- 稿件说明：
移动端阅览
崔栋, 温巧燕, 张华, 等. QML：一种混合空间索引结构[J]. 通信学报, 2021,42(12):1-16.

Dong CUI, Qiaoyan WEN, Hua ZHANG, et al. QML: a hybrid spatial index structure[J]. Journal on communications, 2021, 42(12): 1-16.
崔栋, 温巧燕, 张华, 等. QML：一种混合空间索引结构[J]. 通信学报, 2021,42(12):1-16. DOI： 10.11959/j.issn.1000-436x.2021229.

Dong CUI, Qiaoyan WEN, Hua ZHANG, et al. QML: a hybrid spatial index structure[J]. Journal on communications, 2021, 42(12): 1-16. DOI： 10.11959/j.issn.1000-436x.2021229.

摘要

为了丰富现有学习多维索引的功能并提高索引效率，提出了可以保留数据分布特征的动态数据分段算法DDSA，并结合四叉树和Z顺序曲线构建了混合空间索引（QML），在此基础上分别设计范围查询算法和KNN查询算法。这种保留数据分布特征的索引可以灵活实现快速查询和更新。实验结果表明，QML 索引在实现丰富功能的前提下优化了检索效率，数据更新的时间复杂度为O（1）。与R*-tree相比，QML索引存储减少约33%，更新效率提升40%～80%。查询效率与最优树形索引相近。

Abstract

In order to enrich the functionalities of existing learned multidimensional indexes and improve the efficiency， the dynamic data segmentation algorithm DDSA was proposed， which could preserve the data distribution characteristics.A hybrid spatial index was constructed by combining the QuadTree and Z-order curve （QML）.The range query algorithm were designed and KNN query algorithm respectively.The proposed index allowed flexible fast queries and updates with preserving the characteristics of data distribution.Experimental results show that QML optimizes the query efficiency on the premise of achieving rich functionalities， and the time complexity of data update is O（1）.Compared with R*-tree， the storage consumption of QML is reduced by about 33%， and the update efficiency is improved by 40%～80% .The query efficiency is similar to the optimal tree Index.

关键词

Keywords

references

KRASKA T , BEUTEL A , CHI E H , et al . The case for learned index structures [C ] // Proceedings of the 2018 International Conference on Management of Data . New York:ACM Press , 2018 : 489 - 504 .

ZHANG H C , ANDERSEN D G , PAVLO A , et al . Reducing the storage overhead of main-memory OLTP databases with hybrid indexes [C ] // Proceedings of the 2016 International Conference on Management of Data . New York:ACM Press , 2016 : 1567 - 1581 .

GALAKATOS A , MARKOVITCH M , BINNIG C , et al . FITing-tree:a data-aware index structure [C ] // Proceedings of the 2019 International Conference on Management of Data . New York:ACM Press , 2019 : 1189 - 1206 .

DING J L , MINHAS U F , YU J , et al . ALEX:an updatable adaptive learned index [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2020 : 969 - 984 .

FERRAGINA P , VINCIGUERRA G . The PGM-index:a fully-dynamic compressed learned index with provable worst-case bounds [C ] // Proceedings of the VLDB Endowment . Cairo:Morgan Kaufmann , 2020 : 1162 - 1175 .

TANG C Z , WANG Y Y , DONG Z Y , et al . XIndex:a scalable learned index for multicore data storage [C ] // Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming . New York:ACM Press , 2020 : 969 - 984 .

高远宁 , 叶金标 , 杨念祖 , 等 . 基于中间层的可扩展学习索引技术 [J ] . 软件学报 , 2020 , 31 ( 3 ): 620 - 633 .

GAO Y N , YE J B , YANG N Z , et al . Middle layer based scalable learned index scheme [J ] . Journal of Software , 2020 , 31 ( 3 ): 620 - 633 .

WANG H X , FU X Y , XU J L , et al . Learned index for spatial queries [C ] // Proceedings of 2019 20th IEEE International Conference on Mobile Data Management (MDM) . Piscataway:IEEE Press , 2019 : 569 - 574 .

DAVITKOVA A , MILCHEVSKI E , MICHEL S . The ML-Index:a multidimensional,learned index for point,range,and nearest-neighbor queries [C ] // Proceedings of the 23rd International Conference on Extending Database Technology (EDBT).Copenhagen:OpenProceedings . org , 2020 : 407 - 410 .

LI P F , LU H , ZHENG Q , et al . LISA:a learned index structure for spatial data [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2020 : 2119 - 2133 .

NATHAN V , DING J L , ALIZADEH M , et al . Learning multi-dimensional indexes [C ] // Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . New York:ACM Press , 2020 : 985 - 1000 .

BECKMANN N , KRIEGEL H P , SCHNEIDER R , et al . The R*-tree:an efficient and robust access method for points and rectangles [J ] . ACM SIGMOD Record , 1990 , 19 ( 2 ): 322 - 331 .

RIGAUX P , SCHOLL M , VOISARD A . An introduction to spatial databases [C ] // Spatial Databases . Amsterdam:Elsevier , 2002 : 1 - 28 .

NIEVERGELT J , HINTERBERGER H , SEVCIK K C . The grid file:an adaptable,symmetric multikey file structure [C ] // ACM Transactions on Database Systems . New York:ACM Press , 1984 : 38 - 71 .

GUTTMAN A , . R-trees:a dynamic index structure for spatial searching [C ] // Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD’84 . New York:ACM Press , 1984 : 47 - 57 .

BAYER R , . The universal B-tree for multidimensional indexing:general concepts [C ] // Lecture Notes in Computer Science . Berlin:Springer , 1997 : 198 - 209 .

RAMSAK F , MARKL V , FENK R , et al . Integrating the UB-tree into a database system kernel [C ] // Proceedings of the 26th International Conference on Very Large Data Bases . Cairo:Morgan Kaufmann , 2000 : 263 - 272 .

张洲 , 金培权 , 谢希科 . 学习索引:现状与研究展望 [J ] . 软件学报 , 2021 , 32 ( 4 ): 1129 - 1150 .

ZHANG Z , JIN P Q , XIE X K . Learned indexes:current situations and research Prospects [J ] . Journal of Software , 2021 , 32 ( 4 ): 1129 - 1150 .

孟小峰 , 马超红 , 杨晨 . 机器学习化数据库系统研究综述 [J ] . 计算机研究与发展 , 2019 , 56 ( 9 ): 1803 - 1820 .

MENG X F , MA C H , YANG C . Survey on machine learning for database Systems [J ] . Journal of Computer Research and Development , 2019 , 56 ( 9 ): 1803 - 1820 .

李国良 , 周煊赫 , 孙佶 , 等 . 基于机器学习的数据库技术综述 [J ] . 计算机学报 , 2020 , 43 ( 11 ): 2019 - 2049 .

LI G L , ZHOU X H , SUN J , et al . A survey of machine learning based database Techniques [J ] . Chinese Journal of Computers , 2020 , 43 ( 11 ): 2019 - 2049 .

柴茗珂 , 范举 , 杜小勇 . 学习式数据库系统:挑战与机遇 [J ] . 软件学报 , 2020 , 31 ( 3 ): 806 - 830 .

CHAI M K , FAN J , DU X Y . Learnable database systems:challenges and Opportunities [J ] . Journal of Software , 2020 , 31 ( 3 ): 806 - 830 .

孙路明 , 张少敏 , 姬涛 , 等 . 人工智能赋能的数据管理技术研究 [J ] . 软件学报 , 2020 , 31 ( 3 ): 600 - 619 .

SUN L M , ZHANG S M , JI T , et al . Survey of data management techniques powered by artificial Intelligence [J ] . Journal of Software , 2020 , 31 ( 3 ): 600 - 619 .

JAGADISH H V , OOI B C , TAN K L , et al . iDistance [J ] . ACM Transactions on Database Systems , 2005 , 30 ( 2 ): 364 - 397 .

GARCIA E K , GUPTA M R . Lattice regression [C ] // Proceedings of the 22nd International Conference on Neural Information Processing Systems (NIPS’09).New York:Curran Associates Inc . , 2009 : 594 - 602 .

GULLO F , PONTI G , TAGARELLI A , et al . A time series representation model for accurate and fast similarity detection [J ] . Pattern Recognition , 2009 , 42 ( 11 ): 2998 - 3014 .

LIU X Y , LIN Z J , WANG H Q . Novel online methods for time series segmentation [J ] . IEEE Transactions on Knowledge and Data Engineering , 2008 , 20 ( 12 ): 1616 - 1626 .

XU Z H , ZHANG R , KOTAGIRI R , et al . An adaptive algorithm for online time series segmentation with error bound guarantee [C ] // Proceedings of the 15th International Conference on Extending Database Technology - EDBT’12 . New York:ACM Press , 2012 : 192 - 203 .

HAKLAY M , WEBER P . OpenStreetMap:user-generated street maps [J ] . IEEE Pervasive Computing , 2008 , 7 ( 4 ): 12 - 18 .

浏览量

618

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于区块链的数据库访问控制机制设计

数据库形式化安全策略模型建模及分析方法