双粒度空间存储位置调整的历史轨迹索引

摘要

为了支持历史轨迹数据的查询，通过学习型索引取代传统索引以减小索引存储代价和提升查询效率受到广泛关注.时空轨迹数据的分布不均匀，单粒度的模型不能兼容疏密不一致的轨迹数据；如果为每个周期数据分别构建一个模型，模型总存储大小线性增长；如果只维护一个模型，模型性能通常会随着历史轨迹的增多而恶化.因此，提出一种双粒度空间存储位置调整的历史轨迹索引，包括嵌入空间识别、初始周期模型构建和后期存储位置调整3个阶段：首先，利用密度峰值聚类算法将所有轨迹数据根据其稀疏性划分到粗细粒度层，在每个粒度层上，利用希尔伯特曲线获取轨迹点的一维排序，保证时空邻近的轨迹点排序值也接近；接着，在初始周期数据上构建分段线性模型；最后，后期数据利用初始周期构建的分段线性模型预测存储位置，采用Kuhn-Munkres算法解决模型预测存储位置产生位置冲突的问题.模拟和真实数据集上的实验表明，与其它的学习型索引相比，不仅提升了查询性能，而且显著降低了索引大小和模型维护成本，有效地支持以读为主的历史轨迹数据查询.

关键词

学习型索引 / 密度峰值聚类 / 希尔伯特 / Kuhn-Munkres算法