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

PMk SK: a parallel processing method for moving top spatial keyword query

作　　者：李传文[1] 谷峪[1] 张统 于戈[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004 [2]国家电网大连供电公司,大连116000

出　　处：《东南大学学报（自然科学版）》2015年第5期840-844,共5页Journal of Southeast University：Natural Science Edition

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

摘　　要：为了提高空间关键字移动k近邻查询处理效率,提出关键字影响集的概念,并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法.该方法包含一种并行查询算法和一种并行验证算法.首先,采用并行查询算法计算近邻结果;然后,确定查询区域,并在区域内查找包含的关键字影响集;最后,在查询者移动时不断通过并行验证算法验证影响集,以实现空间关键字移动近邻查询处理.实验结果表明:这2种算法的时间复杂度分别为O((log D+k)/k)和O(logk),均为现有对应算法的O(1/k),其中D为空间对象数目.在多核系统上,这2种算法的运行时间均比现有算法低一个数量级.基于影响集的并行查询处理方法避免了基于安全区域的移动k近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点,可以高效地处理关键字移动k近邻查询.In order to improve the processing efficiency of moving top-k spatial keyword queries,the concept of the keyword influential set is proposed,based on which a parallel processing method is designed.The method is composed of a parallel querying algorithm and a parallel verifying algo-rithm.First,the nearest neighbor set is calculated by using the parallel query algorithm.Then,the query region is obtained,and the nearest neighbor set is found in the region.Finally,the moving top-spatial keyword query is realized by verifying the influential set with the movement of the queri-er.The experimental results show that the time complexities of these two algorithms are O（（log D＋k）/k）and O（logk）,respectively,which are O（1 /k）times over those of the corresponding state-of-the-art methods.Here, D is the number of the spatial objects.On multi-core systems,the processing times of the two proposed algorithms are one order of magnitude lower than those of the corresponding state-of-the-art methods.The influential-setbased parallel query processing method can avoid the shortcoming of the safe-region-based methods that the update cost and update frequency cannot be optimized simultaneously,and can process moving top-k spatial keyword queries efficiently.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]