摘要
为了丰富现有学习多维索引的功能并提高索引效率,提出了可以保留数据分布特征的动态数据分段算法DDSA,并结合四叉树和Z顺序曲线构建了混合空间索引(QML),在此基础上分别设计范围查询算法和KNN查询算法。这种保留数据分布特征的索引可以灵活实现快速查询和更新。实验结果表明,QML索引在实现丰富功能的前提下优化了检索效率,数据更新的时间复杂度为O(1)。与R^(*)-tree相比,QML索引存储减少约33%,更新效率提升40%~80%。查询效率与最优树形索引相近。
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.
作者
崔栋
温巧燕
张华
王华伟
CUI Dong;WEN Qiaoyan;ZHANG Hua;WANG Huawei(The State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China)
出处
《通信学报》
EI
CSCD
北大核心
2021年第12期1-16,共16页
Journal on Communications
基金
国家自然科学基金资助项目(No.62072051,No.61976024,No.61972048)
中央高校基本科研业务费专项资金资助项目(No.2019XD-A01)
中华人民共和国教育部区块链重点项目计划基金资助项目(No.2020KJ010802)。