基于E2LSH的轨迹KNN查询算法

E2LSH-Based Algorithm for Trajectory KNN Query

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

At present,there is a problem of high computational time complexity in the nearest neighbor query algorithm of massive spatio-temporal trajectory data,so a trajectory KNN query algorithm combining domain POI data and E2LSH algorithm is proposed.Firstly,GeoHash technology is used to encode the geographic space,and then the initial dimensionality reduction of the vector space is realized by combining POI data,and then the vector of each trajectory is constructed according to the residence time.The locality sensitive hashing function is used to establish the track index.Finally,distance is calculated for the similar track set returned by the query,and the nearest K query results are obtained by sorting.For incremental trajectory data,the hash value is calculated by E2LSH algorithm,and the trajectory index is added directly,thus avoiding the complicated calculation process and the impact on the existing trajectory index.The experiment on synthetic data and real dataset shows that the proposed method can effectively improve the algorithm efficiency and process the incremental spatiotemporal trajectory data efficiently and easily,although some accuracy is sacrificed in the neighbor query of massive spatiotemporal trajectory data.