Please wait a minute...
浙江大学学报(工学版)
计算机技术、信息工程     
移动云计算环境下的双色反近邻查询算法
季长清,余胜,王宝凤,陶帅,汪祖民,王润方
1. 大连大学 物理科学与技术学院,辽宁 大连 116622;
2. 大连大学 信息工程学院,辽宁 大连 116622
Bichromatic reverse nearest neighbor query algorithm in environment of mobile cloud computing
JI Chang qing, YU Sheng, WANG Bao feng, TAO Shuai
1. College of Physical Science and Technology, Dalian University, Dalian 116622, China;
2. College of Information Technology, Dalian University, Dalian 116622, China
 全文: PDF(1489 KB)   HTML
摘要:

研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用 PCT 轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大(数据点个数大于2.0×106)时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.

Abstract:

A new and high-efficiency bichromatic reverse nearest neighbor query algorithm-SILM algorithm was designed based on the inverted grid index structure within the MapReduce framework by the study on max bichromatic reverse nearest neighbor query optimization problem in the environment of mobile cloud computing. For the split data area, PCT round algorithm was applied in the Map function and the weight of circular area or grids intersected with the circle was denoted as 1. Then the split data areas were scanned and merged by grid processing algorithms in the Reduce function, and   the weights of overlapping grids were accumulated. The grid area with the largest weight of the grid space was outputted. SILM algorithm can not only realize the distributed computation on multiple calculation nodes, but also complete the large-scale parallel query requests  in mobile cloud computing environment. The experiment on the high-efficiency of SILM algorithm was conducted. Results show that the efficiency of SILM algorithm is 2 times more than that of the best algorithm on solving the optimal location problem when the number of data points is larger than 2.0×106.

出版日期: 2016-07-23
:  TP 302  
基金资助:

国家自然科学基金资助项目(61370199,61501076);辽宁省教育科研一般项目(L2014492,L2014283);国家、辽宁省大学生创新创业训练资助项目(201611258015,201611258040);辽宁省“十二五”教学改革资助项目(JG14DB037);大连市科技计划资助项目(20150280);大连大学博士启动专项基金资助项目(20151QL022);广东省石化装备故障诊断重点实验室开放基金资助项目(GDUPTKLAB201505);大连市智慧医疗与健康重点实验室资助项目;中国高等教育学会大学素质教育专题研究课题(CALE201610).

作者简介: 季长清(1980-),男,博士,副教授,从事云计算、大数据、空间数据库、物联网、移动计算等研究.ORCID:0000-0003-3473-2018. E-mail: jcqgood@gmail.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

季长清,余胜,王宝凤,陶帅,汪祖民,王润方. 移动云计算环境下的双色反近邻查询算法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2016.07.015.

JI Chang qing, YU Sheng, WANG Bao feng, TAO Shuai . Bichromatic reverse nearest neighbor query algorithm in environment of mobile cloud computing. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2016.07.015.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2016.07.015        http://www.zjujournals.com/eng/CN/Y2016/V50/I7/1330

[1] TAO Yufei, PAPADIAS D, LIAN Xiang. Reverse kNN search in arbitrary dimensionality [C]∥Proceedings of the 30th International Conference on Very Large Data BasesVolume 30. Toronto: VLDB Endowment, 2004: 744-755.
[2] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.
[3] SINGH A, GLU H F, ALI S A T. High dimensional reverse nearest neighbor queries [C]∥Proceedings of the 12th International Conference on Information and Knowledge Management. New York: ACM, 2003: 91-98.
[4] KORN F, MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries [C]∥ACM SIGMOD Record. New York: ACM, 2000: 201-212.
[5] STUPAR A, MICHEL S, SCHENKEL R. RankReduce  processing Knearest neighbor queries on top of MapReduce [C]∥Proceedings of the 8th Workshop on LargeScale Distributed Systems for Information Retrieval. Geneva: ACM, 2010: 13-18.
[6] KANG J M, MOKBEL M F, SHEKHAR S, et al. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors [C]∥23rd International Conference on Data Engineering. Istanbul: IEEE, 2007: 806-815.
[7] CONDIE T, CONWAY N, ALVARO P, et al. MapReduce online [C]∥Proceedings of NSDI. San Jose: ACM, 2010, 10(4): 20.
[8] CONDIE T, CONWAY N, ALVARO P, et al. Online aggregation and continuous query support in MapReduce [C]∥Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2010: 1115-1118.
[9] LIU Ting, ROSENBERG C, ROWLEY H A. Clustering billions of images with large scale nearest neighbor search [C]∥IEEE Workshop on Applications of Computer Vision. Austin Texas: IEEE, 2007: 28.
[10] LI Jun, ZHANG Peng, TAN Jianlong, et al. Continuous data stream query in the cloud [C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 2389-2392.
[11] WONG R C W, TAMER ZSU M, YU P S, et al. Efficient method for maximizing bichromatic reverse nearest neighbor [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 1126-1137.
[12] YANG CongJun, LIN K I. An index structure for efficient reverse nearest neighbor queries [C]∥ Proceedings of 17th International Conference on Data Engineering. Heidelberg: IEEE, 2001: 485-492.
[13] AKDOGAN A, DEMIRYUREK U, BANAEIKASHANI F, et al. Voronoibased geospatial query processing with MapReduce [C]∥2010 IEEE 2nd International Conference on Cloud Computing Technology and Science (CloudCom). Indianapolis: IEEE, 2010: 916.
[14] LIU Yubao, WONG R CH, WANG Ke, et al. A new approach for maximizing bichromatic reverse nearest neighbor search KAISnew approach for MaxBRNN [J]. Knowledge and Information Systems, 2012, 36(1): 23-58.
[15] YAN Da, WONG R C H, NG W. Efficient methods for finding influential locations with adaptive grids [C]∥ Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 1475-1484.
[16] CLARKSON K L. Nearest neighbor queries in metric spaces [J]. Discrete and Computational Geometry, 1999, 22 (1): 63-93.
[17] JI Changqing, LI Zhiyang, QU Wenyu, et al. Scalable nearest neighbor query processing based on inverted grid index [J]. Journal of Network and Computer Applications, 2014, 44(1): 172-182.
[18] 张文光,陈俊,姚钰辉,等. 分布式网络环境中基于MapReduce的WordCount实现[J]. 贵州师范大学学报:自然科学版, 2015, 33(1): 93-97.
ZHANG Wenguang, CHEN Jun, YAO Yuhui, et al. MapReducebased WordCount achieve in distributed network environment [J]. Journal of Guizhou Normal University: Natural Sciences, 2015, 33(1): 93-97.
[19] JI Changqing, QU Wenyu, LI Zhiyang, et al. Scalable multidimensional RNN query processing [J]. Concurrency and Computation: Practice and Experience, 2015, 27(16): 4156-4171.
[20] JI Changqing, DONG Tingting, LI Yu,et al. Inverted gridbased kNN query processing with MapReduce [C]∥ 7th ChinaGrid Annual Conference (ChinaGrid). Beijing: IEEE, 2012: 25-32.

[1] 于绩洋,刘鹏,华幸成,马骧,杨建义. 片上光电互连的多核系统仿真方法[J]. 浙江大学学报(工学版), 2015, 49(11): 2214-2222.
[2] 叶霞,辛愿,刘勇,刘鹏. 基于媒体数字信号处理器的流预取机制[J]. J4, 2014, 48(2): 268-278.
[3] 全励, 程爱莲, 潘赟, 丁勇, 严晓浪. 基于旁路通道的片上网络差别型服务实现方法[J]. J4, 2013, 47(6): 957-968.
[4] 苏程, 俞伟斌, 倪广翼, 黄智才, 陶春辉, 章孝灿. 深水多波束测深侧扫声纳显控系统研究[J]. J4, 2013, 47(6): 934-943.
[5] 张振, 李善平. 变频感知的处理器服务时间估算方法[J]. J4, 2012, 46(4): 725-733.
[6] 傅朝阳, 高济, 周尤明. 基于承诺的agent组织描述工具[J]. J4, 2011, 45(4): 627-636.
[7] 曹晓阳, 潘赟, 严晓浪, 宦若虹. 低面积-时间复杂度的离散余弦变换脉动结构[J]. J4, 2011, 45(4): 656-659.
[8] 徐鸿明,孟建熠,严晓浪,葛海通. 基于高速缓存资源共享的TLB设计方法[J]. J4, 2011, 45(3): 462-466.
[9] 龚帅帅,吴晓波,孟建熠,丁永林. 基于历史链接关系的指令高速缓存低功耗方法[J]. J4, 2011, 45(3): 467-471.
[10] 黄雪维,张培勇,吕冬明,郑丹丹,严晓浪. 基于时延搜索的SRAM建立时间快速提取方法[J]. J4, 2011, 45(3): 445-450.
[11] 丁勇, 孙纲德, 严晓浪. 基于运动补偿和自适应插值的混合去隔行方法[J]. J4, 2011, 45(2): 323-329.
[12] 丁勇, 王翔, 严晓浪. 边缘自适应的四点分段抛物线图像缩放[J]. J4, 2010, 44(9): 1637-1642.
[13] 蔡卫光, 姚庆栋, 刘鹏, 等. 基于提前写回策略的数据转发优化方法[J]. J4, 2010, 44(1): 75-80.
[14] 黄江伟, 胡威, 项凌翔, 等. 基于电池模型驱动的软硬件低功耗设计[J]. J4, 2009, 43(12): 2149-2154.