QML: a hybrid spatial index structure - Dong CUI; Qiaoyan WEN; Hua ZHANG; Huawei WANG (Tongxin xuebao)
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.