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

QML:a hybrid spatial index structure

为了丰富现有学习多维索引的功能并提高索引效率,提出了可以保留数据分布特征的动态数据分段算法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.