[1]李传文,谷峪,张统,等.PMkSK:一种空间关键字移动近邻查询并行处理方法[J].东南大学学报(自然科学版),2015,45(5):840-844.[doi:10.3969/j.issn.1001-0505.2015.05.005]
 Li Chuanwen,Gu Yu,Zhang Tong,et al.PMkSK: a parallel processing method for moving top spatial keyword query[J].Journal of Southeast University (Natural Science Edition),2015,45(5):840-844.[doi:10.3969/j.issn.1001-0505.2015.05.005]
点击复制

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

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
45
期数:
2015年第5期
页码:
840-844
栏目:
计算机科学与工程
出版日期:
2015-09-20

文章信息/Info

Title:
PMkSK: a parallel processing method for moving top spatial keyword query
作者:
李传文1谷峪1张统2于戈1
1东北大学信息科学与工程学院, 沈阳 110004; 2国家电网大连供电公司, 大连 116000
Author(s):
Li Chuanwen1 Gu Yu1 Zhang Tong2 Yu Ge1
1School of Information and Engineering, Northeastern University, Shenyang 110004, China
2State Grid Dalian Electric Power Supply Company, Dalian 116000, China
关键词:
空间关键字 k近邻 影响集 空间移动查询 安全区域
Keywords:
spatial keyword k-nearest-neighbor influential set moving spatial query safe region
分类号:
TP311.13
DOI:
10.3969/j.issn.1001-0505.2015.05.005
摘要:
为了提高空间关键字移动k近邻查询处理效率,提出关键字影响集的概念,并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法.该方法包含一种并行查询算法和一种并行验证算法.首先,采用并行查询算法计算近邻结果;然后,确定查询区域,并在区域内查找包含的关键字影响集;最后,在查询者移动时不断通过并行验证算法验证影响集,以实现空间关键字移动近邻查询处理.实验结果表明:这2种算法的时间复杂度分别为O((logD+k)/k)和O(logk),均为现有对应算法的O(1/k),其中D为空间对象数目.在多核系统上,这2种算法的运行时间均比现有算法低一个数量级.基于影响集的并行查询处理方法避免了基于安全区域的移动k近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点,可以高效地处理关键字移动k近邻查询.
Abstract:
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 algorithm. 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 querier. The experimental results show that the time complexities of these two algorithms are O((logD+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 frequency cannot be optimized simultaneously, and can process moving top-k spatial keyword queries efficiently.

参考文献/References:

[1] Li C W, Gu Y, Li F F, et al. Moving k-nearest neighbor query over obstructed regions [C]//2012 International Asia-Pacific Web Conference. Busan, Korea, 2010: 29-35.
[2] Wu D M, Man L Y, Jensen C S, et al. Efficient continuously moving top-k spatial keyword query processing [C]//2011 IEEE 27th International Conference on Data Engineering. Hannover, Germany, 2011: 541-552.
[3] Huang W H, Li G L, Tan K-L, et al. Efficient safe-region construction for moving top-k spatial keyword queries [C]//21st ACM International Conference on Information and Knowledge Management. Maui, HI, USA, 2012: 932-941.
[4] Li C W, Gu Y, Qi J Z, et al. Processing moving kNN queries using influential neighbor sets [J]. Proceedings of the VLDB Endowment, 2014, 8(2): 113-124.
[5] Salton G, McGill M J. Introduction to modern information retrieval [M]. New York: McGraw-Hill, Inc., 1986: 51-55.
[6] Hjaltason G R, Samet H. Ranking in spatial databases [C]//Proceedings of the 4th International Symposium on Advances in Spatial Databases. Berlin, Germany, 1995: 83-95.
[7] Beckmann N, Kriegel H-P, Schneider R, et al. The R*-tree: an efficient and robust access method for points and rectangles [J]. ACM SIGMOD Record, 1990, 19(2): 322-331.
[8] Okabe A, Boots B, Sugihara K, et al. Spatial tessellations: concepts and applications of voronoi diagrams [M]. 2nd ed. Hoboken, New Jersey, USA: John Wiley & Sons, 2000: 115-117.
[9] Preparata F P, Michael S. Computational geometry: an introduction [M]. Berlin, Germany: Springer Science & Business Media, 1985: 93-95.
[10] 陈国良.并行算法的设计与分析[M].3版.北京:高等教育出版社,1994:201-205.
[11] Cong G, Jensen C S, Wu D M. Efficient retrieval of the top-k most relevant spatial web objects [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 337-348.

备注/Memo

备注/Memo:
收稿日期: 2015-04-02.
作者简介: 李传文(1982—),男,博士,讲师,lichuanwen@ise.neu.edu.cn.
基金项目: 国家自然科学基金资助项目(61300021)、中央高校基本科研业务费专项基金资助项目(N140404008).
引用本文: 李传文,谷峪,张统,等.PMkSK:一种空间关键字移动近邻查询并行处理方法[J].东南大学学报:自然科学版,2015,45(5):840-844. [doi:10.3969/j.issn.1001-0505.2015.05.005]
更新日期/Last Update: 2015-09-20