Efficient Distributed RNN Query Processing with Caching

Abstract:

Reverse Nearest Neighbour (RNN) queries play an important role in applications such as internet of vehicles, decision support systems, profile based marketing and so on. Recently, more attention has been paid to the problem of efficient distributed RNN computation in mobile cloud computing environment. A major downside of the existing RNN is its inherent sequential nature and using in-memory algorithm, which limits its applicability to massive data. In this paper, we propose a novel distributed caching based method to efficiently improve the performance of the RNN calculation in a distributed environment. Extensive experiments using both real and synthetic datasets demonstrated that our proposed methods are the state-of-the-art algorithms in scalable RNN queries.

• Periodical: Applied Mechanics and Materials (Volumes 556-562)
• Pages: 5352-5355
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.556-562.5352
• Online since: May 2014
• Authors: Yin Bo Shao, Jing Wei Xie, Yuan Quan Li, Sun Ying Gao, Chang Qing Ji*
• Keywords: Distributed Cache, Reverse Nearest Neighbour, Spatial Databases

References

[1] Korn, Flip, and S. Muthukrishnan. Influence sets based on reverse nearest neighbor queries., ACM SIGMOD Record 29, no. 2 (2000): 201-212.

DOI: 10.1145/335191.335415

[2] Tao, Yufei, Dimitris Papadias, and Xiang Lian. Reverse kNN search in arbitrary dimensionality., In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pp.744-755. VLDB Endowment, (2004).

DOI: 10.1016/b978-012088469-8.50066-8

[3] Lin, Xin, Lingchen Zhou, Peng Chen, and Junzhong Gu. Privacy Preserving Reverse Nearest-Neighbor Queries Processing on Road Network., In Web-Age Information Management, pp.19-28. Springer Berlin Heidelberg, (2012).

DOI: 10.1007/978-3-642-33050-6_3

[4] Yang, Congyun, and King-Ip Lin. An index structure for efficient reverse nearest neighbor queries., In Data Engineering, 2001. Proceedings. 17th International Conference on, pp.485-492. IEEE, (2001).

DOI: 10.1109/icde.2001.914862

[5] Akdogan, Afsin, Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. Voronoi-based geospatial query processing with mapreduce., InCloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on, pp.9-16. IEEE, (2010).

DOI: 10.1109/cloudcom.2010.92

[6] Andreasen, Troels, Henning Christiansen, and Henrik Legind Larsen, eds. Flexible query answering systems. Norwell, MA: Kluwer Academic Publishers, (1997).

[7] Changqing Ji, et al. Efficient Multi-dimensional Spatial RkNN Query Processing with MapReduce., ChinaGrid Annual Conference (ChinaGrid), 2013 8th. IEEE, (2013).

DOI: 10.1109/chinagrid.2013.17

[8] Comap, the consortium for mathematics and its applications, http: /www. comap. com.