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 .
0
浏览量
1060
下载量
0
CSCD
- 网络PDF下载
- XML下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
AI问答- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
- 总访问量：583619 今日访问量：1435