PMkSK：一种空间关键字移动近邻查询并行处理方法

摘要：

为了提高空间关键字移动 k 近邻查询处理效率，提出关键字影响集的概念，并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法。该方法包含一种并行查询算法和一种并行验证算法。首先，采用并行查询算法计算近邻结果；然后，确定查询区域，并在区域内查找包含的关键字影响集；最后，在查询者移动时不断通过并行验证算法验证影响集，以实现空间关键字移动近邻查询处理。实验结果表明：这2种算法的时间复杂度分别为 O（（log D ＋k）／k）和 O（logk），均为现有对应算法的 O（1／k），其中 D 为空间对象数目。在多核系统上，这2种算法的运行时间均比现有算法低一个数量级。基于影响集的并行查询处理方法避免了基于安全区域的移动 k 近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点，可以高效地处理关键字移动 k 近邻查询。

关键词：空间、k 近邻、影响集、空间移动查询、安全区域

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61300021;中央高校基本科研业务费专项基金资助项目N140404008．

在线出版日期：2015-10-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：840-844