基于预计算的连续k近邻查询处理的性能优化

摘要

现有的路网中连续k近邻(Continuous k-nearest neighbor,CkNN)查询方法一般分为两类:一类是利用某种数据结构监控查询q的kNN可能存在的区域;另一类是基于预计算的.基于预计算的CkNN查询处理方法不容易扩展到大路网结构,这是因为大路网的大量预计算信息不得不存储在外存,由此引发的内外存之间的大量的信息交换会大大地降低查询算法的性能.为了克服这个问题,本文提出了一种有效的优化技术,以减少查询处理时的内外存交换次数、提高查询处理的效率.实验证明所提出的优化方法的有效性,而且优化技术的采用使得查询处理算法具有更好的可扩展性.%The existing continuous k-nearest neighbor (CkNN) query processing methods in road networks are generally divided into two classes:(1) The methods using a data structure to monitor the area where the kNNs of the query could exist; (2) The methods based on pre-caleulation.People always consider that CkNN query methods based on pre-computation cannot easily be extended to handle CkNN queries in large road networks.This is because that pre-computed information of a large road network always has a too large size to be stored in memory,thus lots of data swapping between the main memory and the auxiliary storage will greatly degrade the performance of query methods.In order to overcome this shortcoming,an efficient optimization technique is proposed to greatly reduce data swapping between the main memory and the auxiliary storage in query processing and improve the efficiency of query processing.Experimental result shows the efficiency of the technique.Moreover,the use of optimization technique could improve the scalability of the query processing methods.