QML: a hybrid spatial index structure

Dong CUI; Qiaoyan WEN; Hua ZHANG; Huawei WANG

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

您当前的位置：

首页 >

文章列表页 >

QML: a hybrid spatial index structure

Papers | 更新时间：2024-06-05

- QML: a hybrid spatial index structure
- Journal on Communications Vol. 42, Issue 12, Pages: 1-16(2021)
- 作者机构：
  
  北京邮电大学网络与交换技术国家重点实验室，北京 100876
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62072051);The National Natural Science Foundation of China(61976024);The National Natural Science Foundation of China(61972048);The Fundamental Research Funds for the Central Universities(2019XD-A01);Ministry of Education Blockchain Core Project(2020KJ010802)
- DOI：10.11959/j.issn.1000-436x.2021229
  CLC： TP392
- Online First：2021-12，
  
  Published：25 December 2021
- 稿件说明：
移动端阅览
Dong CUI, Qiaoyan WEN, Hua ZHANG, et al. QML: a hybrid spatial index structure[J]. Journal on Communications, 2021, 42(12): 1-16.
DOI：

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 .

Views

1100

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Design for database access control mechanism based on blockchain

Formal modeling and analyzing method for database security policy

Related Author

Yonggui FU

Jianming ZHU

Rong WANG

Min ZHANG

Deng-guo FENG

Hao LI

Related Institution

School of Information,Shanxi University of Finance and Economics

School of Information, Central University of Finance and Economics

Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences

University of Chinese Academy of Sciences

State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

AI问答

⁰