CAJ | 학술논문

为了提高空间关键字移动 k 近邻查询处理效率，提出关键字影响集的概念，并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法。该方法包含一种并行查询算法和一种并行验证算法。首先，采用并行查询算法计算近邻结果；然后，确定查询区域，并在区域内查找包含的关键字影响集；最后，在查询者移动时不断通过并行验证算法验证影响集，以实现空间关键字移动近邻查询处理。实验结果表明：这2种算法的时间复杂度分别为 O（（log D ＋k）／k）和 O（logk），均为现有对应算法的 O（1／k），其中 D 为空间对象数目。在多核系统上，这2种算法的运行时间均比现有算法低一个数量级。基于影响集的并行查询处理方法避免了基于安全区域的移动 k 近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点，可以高效地处理关键字移动 k 近邻查询。
위료제고공간관건자이동 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-set-based parallel query processing method can avoid the shortcoming of the safe-region-based methods that the update cost and update frequen-cy cannot be optimized simultaneously,and can process moving top-k spatial keyword queries effi-ciently.