Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (1): 142-150    DOI: 10.3785/j.issn.1008-973X.2018.01.019
Automatic Technology     
Multi-threading based continuous k-nearest neighbor queries for uncertain moving objects
QI Jian-peng1, YU Yan-wei1, WANG Chuang-cun1, CAO Lei2, SONG Peng1
1. School of Computer and Control Engineering, Yantai University, Yantai 264005, China;
2. CSAIL, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
Download:   PDF(1323KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

An efficient multi-core and multi-threading based framework was proposed for searching k-NNs of large-scale queries with uncertain locations based on the continuous k-NN query method called Rate for uncertain moving objects. The velocities and locations of different query objects were used to judge whether employing query reuse and give the bound of reuse distance. The density grid based multi-threaded data partition method was proposed to resolve the problem of load balance, and neighboring queries were grouped into the same thread to improve the reusability. The obtained predicted areas of moving objects can be reused by building shared memory over multi-core and multi-threading. The experiments conducted on large scale datasets demonstrated the effectiveness and efficiency of the proposed methods, and the proposed optimized parallel method reached about 37 speed-up compared with Rate.

Received: 12 May 2017      Published: 15 December 2017
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

QI Jian-peng, YU Yan-wei, WANG Chuang-cun, CAO Lei, SONG Peng. Multi-threading based continuous k-nearest neighbor queries for uncertain moving objects. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(1): 142-150.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2018.01.019     OR     http://www.zjujournals.com/eng/Y2018/V52/I1/142


基于多线程的不确定移动对象连续k近邻查询

针对不确定数据下的大规模连续k近邻查询请求，基于不确定移动对象连续k近邻查询的Rate方法，提出高效的基于多核多线程的并行查询处理框架.根据查询对象的运动速度与相对位置确定查询请求间是否采用查询复用，确定查询复用时的距离边界.提出密度网格扩展的多线程数据分发方法，解决了负载均衡问题，将空间位置相邻的查询请求划分到同一线程，提高查询复用率.通过多线程间的内存共享机制，对计算过的移动对象的预测区域实现计算复用.在大规模交通数据集上验证了所提算法的有效性与查询性能，相比传统的Rate方法，所提并行算法的加速比可达37.

[1] ZHENG Y, CAPRA L, WOLFSON O, et al. Urban computing:concepts, methodologies, and applications[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(3):38.
[2] 周傲英, 杨彬, 金澈清, 等. 基于位置的服务:架构与进展[J]. 计算机学报, 2011, 34(7):1155-1171. ZHOU Ao-ying, YANG Bin, JIN Che-qing, et al. Location-based services:architecture and progress[J]. Chinese Journal of Computers, 2011, 34(7):1155-1171.
[3] TAO Y, PAPADIAS D, SHEN Q. Continuous nearest neighbor search[C]//International Conference on Very Large Data Bases. Hong Kong:VLDB Endowment, 2002:287-298.
[4] ZHENG Yu. Trajectorydata mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):1-41.
[5] 于彦伟, 齐建鹏, 宋鹏, 等. 面向不确定移动对象的连续K近邻查询算法[J]. 模式识别与人工智能, 2016, 29(11):1048-1056. YU Yan-wei, QI Jian-peng, SONG Peng, et al. Continuous K-nearest neighbor queries for uncertain moving objects[J]. Pattern Recognition and Artificial Intelligence, 2016, 29(11):1048-1056.
[6] KOLAHDOUZAN M R, SHAHABI C. Alternativesolutions for continuous K nearest neighbor queries in spatial network databases[J]. Geoinformatica, 2005, 9(4):321-341.
[7] YU X, PU K Q, KOUDAS N. Monitoring k-nearest neighbor queries over moving objects[C]//IEEE International Conference on Data Engineering (ICDE). Tokyo, Japan:IEEE, 2005:631-642.
[8] XIONG X, MOKBEL M F, AREF W G. SEA-CNN:scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases[C]//IEEE International Conference on Data Engineering (ICDE). Tokyo:IEEE, 2005:643-654.
[9] 郝兴, 王凌, 孟小峰. 一种道路网络中移动对象的k近邻多查询处理算法[C]//中国数据库学术会议. 海口:中国计算机学会, 2007:113-118. HAO Xing, WANG Ling, MENG Xiao-feng. Multiple KNN queries processing for moving objects in road networks[C]//National Database Conference. Haikou:CCF, 2007:113-118.
[10] 孙圣力, 林硕. 一个高效的连续k近邻查询改进算法[J]. 计算机研究与发展, 2013(增1):80-89. SUN Sheng-li, LIN Shuo. A improved algorithm for efficient continuous KNN queries[J]//Journal of Computer Research and Development, 2013(supple.1):80-89.
[11] MOURATIDIS K, YIU M L, PAPADIAS D, et al. Continuousnearest neighbor monitoring in road networks[C]//Proceedings of the 32nd Very Large Data Bases Conference (VLDB). Seoul:VLDB, 2006:43-54.
[12] HUANG Y K, CHEN Z W, LEE C. Continuous K-nearest neighbor query over moving objects in road networks[C]//Advances in Data and Web Management, Joint International Conferences. Suzhou:[s.n.], 2009:27-38.
[13] 廖巍, 吴晓平, 严承华, 等. 多用户连续k近邻查询多线程处理技术研究[J]. 计算机应用, 2009, 29(7):1861-1864. LIAO Wei, WU Xiao-ping, YAN Cheng-hua, et al. Research on multi-threading processing of concurrent multiple continuous k-nearest neighbor queries[J]. Journal of Computer Applications, 2009, 29(7):1861-1864.
[14] 赵亮, 陈荦, 景宁, 等. 道路网中的移动对象连续K近邻查询[J]. 计算机学报, 2010, 33(8):1396-1404. ZHAO Liang, CHEN Luo, JING Ning, et al. Continuous K nearest neighbor queries of moving objects in road networks[J]. Chinese Journal of Computers, 2010, 33(8):1396-1404.
[15] 赵亮, 景宁, 陈荦, 等. 面向多核多线程的移动对象连续K近邻查询[J]. 软件学报, 2011, 22(8):1805-1815. ZHAO Liang, JING Ning, CHEN Luo, et al. Continuous K nearest neighbor queries over moving objects based on multi-core and multi-threading[J]. Journal of Software, 2011, 22(8):1805-1815.
[16] HUANG Y K, CHEN C C, LEE C. Continuous K-nearest neighbor query for moving objects with uncertain velocity[J]. Geoinformatica, 2009, 13(1):1-25.
[17] 王艳秋, 徐传飞, 于戈, 等. 一种面向不确定对象的可见k近邻查询算法[J]. 计算机学报, 2010, 33(10):1943-1952. WANG Yan-qiu, XU Chuan-fei, YU Ge, et al. Visible k nearest neighbor queries over uncertain data[J]. Chinese Journal of Computers, 2010, 33(10):1943-1952.
[18] 陈子军, 任彩平, 刘文远. 路网中查询点速度不确定的连续k近邻查询方法[J]. 小型微型计算机系统, 2011, 32(3):430-434. CHEN Zi-jun, REN Cai-ping, LIU Wen-yuan. Continuous K-nearest neighbor query for query points with uncertain velocity[J]. Journal of Chinese Computer Systems, 2011, 32(3):430-434.
[19] 王宝文, 胡云, 陈子军, 等. 路网中速度不确定移动对象的k近邻查询[J]. 小型微型计算机系统, 2012, 33(8):1756-1760. WANG Bao-wen, HU Yun, CHEN Zi-jun, et al. k-nearest neighbor query for moving objects with uncertain velocity in road network[J]. Journal of Chinese Computer Systems, 2012, 33(8):1756-1760.
[20] LI G, LI Y, SHU L C, et al. CkNNquery processing over moving objects with uncertain speeds in road networks[C]//Proceedings of the 13th Asia-Pacific Web Conference on Web Technologies and Applications. Beijing, China:Springer, 2011:65-76.
[21] FAN P, LI G, YUAN L, et al. Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks[J]. Information Systems, 2012, 37(1):13-32.
[22] SISTLA A P, WOLFSON O, XU B. Continuous nearest-neighbor queries with location uncertainty[J]. VLDB Journal, 2015, 24(1):25-50.
[23] BRINKHOFF T. Generatingnetwork-based moving objects[C]//International Conference on Scientific and Statistical Database Management. Washington, DC:IEEE, 2000:253-255.
[24] ARGE L, BERG M D, HAVERKORT H, et al. The priority R-tree:a practically efficient and worst-case optimal R-tree[J]. ACM Transactions on Algorithms, 2008, 4(1):9.
[1] HAN Yong, NING Lian-ju, ZHENG Xiao-lin, LIN Wei-hua, SUN Zhong-yuan. Matrix factorization recommendation based on social information and item exposure[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(1): 89-98.
[2] ZHENG Zhou, ZHANG Xue-chang, ZHENG Si-ming, SHI Yue-ding. Liver segmentation in CT images based on region-growing and unified level set method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2382-2396.
[3] ZHAO Li-ke, ZHENG Shun-yi, WANG Xiao-nan, HUANG Xia. Rigid object position and orientation measurement based on monocular sequence[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2372-2381.
[4] HE Jie-guang, PENG Zhi-ping, CUI De-long, LI Qi-rui. Teaching-learning-based optimization algorithm with local dimension improvement[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2159-2170.
[5] LI Zhi, SHAN Hong, MA Tao, HUANG Jun. Group discovery of mobile terminal users based on reverse-label propagation algorithm[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2171-2179.
[6] WANG Shuo-peng, YANG Peng, SUN Hao. Construction process optimization of fingerprint database for auditory localization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(10): 1973-1979.
[7] WEI Xiao-feng, CHENG Cheng-qi, CHEN Bo, WANG Hai-yan. Chain code based on independent edge number[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1686-1693.
[8] CHEN Rong-hua, WANG Ying-han, BU Jia-jun, YU Zhi, GAO Fei. Website accessibility sampling evaluation based on KNN and local regression[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1702-1708.
[9] ZHANG Cheng-zhi, FENG Hua-jun, XU Zhi-hai, LI Qi, CHEN Yue-ting. Piecewise noise variance estimation of images based on wavelet transform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1804-1810.
[10] LIU Zhou-zhou, LI Shi-ning, LI Bin, WANG Hao, ZHANG Qian-yun, ZHENG Ran. New elastic collision optimization algorithm and its application in sensor cloud resource scheduling[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1431-1443.
[11] WANG Yong-chao, ZHU Kai-lin, WU Qi-xuan, LU Dong-ming. Adaptive display technology of high precision model based on local rendering[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1461-1466.
[12] SUN Nian, LI Yu-qiang, LIU Ai-hua, LIU Chun, LI Wei-wei. Microblog sentiment analysis based on collaborative learning under loose conditions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1452-1460.
[13] ZHENG Shou-guo, CUI Yan-min, WANG Qing, YANG Fei, CHENG Liang. Design of field data acquisition platform for aircraft assembly[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1526-1534.
[14] BI Xiao-jun, WANG Chao. Many-objective evolutionary algorithm based on hyperplane projection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1284-1293.
[15] ZHANG Ting-rong, TENG Qi-zhi, LI Zheng-ji, QING Lin-bo, HE Xiao-hai. Super-resolution reconstruction for three-dimensional core CT image[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1294-1301.