| Computer Technology, Information Engineering |
|
|
|
|
| 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 |
|
|
|
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．
|
|
Published: 23 July 2016
|
|
|
移动云计算环境下的双色反近邻查询算法
研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用 PCT 轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大（数据点个数大于2.0×106）时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.
|
|
| ［1］ TAO Yufei, PAPADIAS D, LIAN Xiang. Reverse kNN search in arbitrary dimensionality ［C］∥Proceedings of the 30th International Conference on Very Large Data BasesVolume 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 Knearest neighbor queries on top of MapReduce ［C］∥Proceedings of the 8th Workshop on LargeScale 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 Jianlong, 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 CongJun, 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, BANAEIKASHANI F, et al. Voronoibased geospatial query processing with MapReduce ［C］∥2010 IEEE 2nd International Conference on Cloud Computing Technology and Science (CloudCom). Indianapolis: IEEE, 2010: 916．
［14］ LIU Yubao, WONG R CH, WANG Ke, et al. A new approach for maximizing bichromatic reverse nearest neighbor search KAISnew 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 Changqing, LI Zhiyang, QU Wenyu, 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 Wenguang, CHEN Jun, YAO Yuhui, et al. MapReducebased WordCount achieve in distributed network environment ［J］. Journal of Guizhou Normal University: Natural Sciences, 2015, 33(1): 93-97．
［19］ JI Changqing, QU Wenyu, LI Zhiyang, et al. Scalable multidimensional RNN query processing ［J］. Concurrency and Computation: Practice and Experience, 2015, 27(16): 4156-4171．
［20］ JI Changqing, DONG Tingting, LI Yu,et al. Inverted gridbased kNN query processing with MapReduce ［C］∥ 7th ChinaGrid Annual Conference (ChinaGrid). Beijing: IEEE, 2012: 25-32. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
