Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2018, Vol. 52 Issue (1): 142-150    DOI: 10.3785/j.issn.1008-973X.2018.01.019
自动化技术     
基于多线程的不确定移动对象连续k近邻查询
齐建鹏1, 于彦伟1, 王创存1, 曹磊2, 宋鹏1
1. 烟台大学 计算机与控制工程学院, 山东 烟台 264005;
2. 麻省理工学院 计算机科学与人工智能实验室, 马萨诸塞州 剑桥 02139
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
 全文: PDF(1323 KB)   HTML
摘要：

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

国家自然科学基金资助项目（61403328，61572419，61773331，61703360）；山东省重点研发计划资助项目（2015GSF115009）；山东省自然科学基金资助项目（ZR2014FQ016）；山东省高等学校科技计划项目（J17KA091）；烟台大学研究生科技创新基金资助项目（YDZD1712）.
通讯作者: 于彦伟,男,博士,讲师.orcid.org/0000-0001-6941-2132.     E-mail: yuyanwei@ytu.edu.cn
作者简介: 齐建鹏(1992-),男,硕士生,从事数据挖掘并行计算研究.orcid.org/0000-0001-6150-9773.E-mail:jianpengqi@126.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　

引用本文:

齐建鹏, 于彦伟, 王创存, 曹磊, 宋鹏. 基于多线程的不确定移动对象连续k近邻查询[J]. 浙江大学学报(工学版), 2018, 52(1): 142-150.

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.

链接本文:

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

[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] 韩勇, 宁连举, 郑小林, 林炜华, 孙中原. 基于社交信息和物品曝光度的矩阵分解推荐[J]. 浙江大学学报(工学版), 2019, 53(1): 89-98.
[2] 郑洲, 张学昌, 郑四鸣, 施岳定. 基于区域增长与统一化水平集的CT肝脏图像分割[J]. 浙江大学学报(工学版), 2018, 52(12): 2382-2396.
[3] 赵丽科, 郑顺义, 王晓南, 黄霞. 单目序列的刚体目标位姿测量[J]. 浙江大学学报(工学版), 2018, 52(12): 2372-2381.
[4] 何杰光, 彭志平, 崔得龙, 李启锐. 局部维度改进的教与学优化算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2159-2170.
[5] 李志, 单洪, 马涛, 黄郡. 基于反向标签传播的移动终端用户群体发现[J]. 浙江大学学报(工学版), 2018, 52(11): 2171-2179.
[6] 王硕朋, 杨鹏, 孙昊. 听觉定位数据库构建过程优化[J]. 浙江大学学报(工学版), 2018, 52(10): 1973-1979.
[7] 魏小峰, 程承旗, 陈波, 王海岩. 基于独立边数的链码方法[J]. 浙江大学学报(工学版), 2018, 52(9): 1686-1693.
[8] 陈荣华, 王鹰汉, 卜佳俊, 于智, 高斐. 基于KNN算法与局部回归的网站无障碍采样评估[J]. 浙江大学学报(工学版), 2018, 52(9): 1702-1708.
[9] 张承志, 冯华君, 徐之海, 李奇, 陈跃庭. 图像噪声方差分段估计法[J]. 浙江大学学报(工学版), 2018, 52(9): 1804-1810.
[10] 刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.
[11] 王勇超, 祝凯林, 吴奇轩, 鲁东明. 基于局部渲染的高精度模型自适应展示技术[J]. 浙江大学学报(工学版), 2018, 52(8): 1461-1466.
[12] 孙念, 李玉强, 刘爱华, 刘春, 黎威威. 基于松散条件下协同学习的中文微博情感分析[J]. 浙江大学学报(工学版), 2018, 52(8): 1452-1460.
[13] 郑守国, 崔雁民, 王青, 杨飞, 程亮. 飞机装配现场数据采集平台设计[J]. 浙江大学学报(工学版), 2018, 52(8): 1526-1534.
[14] 毕晓君, 王朝. 基于超平面投影的高维多目标进化算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1284-1293.
[15] 张廷蓉, 滕奇志, 李征骥, 卿粼波, 何小海. 岩心三维CT图像超分辨率重建[J]. 浙江大学学报(工学版), 2018, 52(7): 1294-1301.