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
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．
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), 2016, 50(7): 1330-1337.
［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.
YE Xia, XIN Yuan, LIU Yong, LIU Peng. Stream Prefetcher based on MediaDSP[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2014, 48(2): 268-278.
