基于 E2LSH 的轨迹 KNN 查询算法

来源：计算机技术与发展杂志2020年第03期北京时间：

作者：邱磊;吴志兵

摘要：目前海量时空轨迹数据近邻查询算法中存在计算时间复杂度较高的问题,因此提出了一种结合领域POI数据和 E2LSH算法的轨迹KNN查询算法。 首先利用GeoHash技术对地理空间进行编码,然后结合POI数据实现向量空间的初步 降维,进而根据停留时间构建每条轨迹的向量,采用局部敏感哈希函数运算结果建立轨迹索引,最后对查询返回的相似轨 迹集合分别进行距离计算,经过排序得到距离最近的K个查询结果。 对于增量的轨迹数据,利用E2LSH算法计算哈希值, 直接添加轨迹索引,从而避免了复杂的计算过程以及对现有轨迹索引的影响。 基于合成数据及真实数据集的实验结果表 明,该方法在海量时空轨迹数据的近邻查询中,虽然牺牲了一定的准确率,但有效提升了算法效率,并能够高效简便地处 理增量的时空轨迹数据。

关键词：海量轨迹大数据;近邻查询;地理空间编码;局部敏感哈希;轨迹索引