一個反向鄰近點查詢(Reverse Nearest Neighbor query, RNN) 是取得一組資料點，而這組資料點的條件為它們最近的鄰近點是查詢點。接續RNN的延伸，也就是反向前k近鄰近點查詢(Reverse k Nearest Neighbor query, RkNN)，此查詢取得一組資料點，而這組資料點的條件為它們的k個鄰近點中包含著查詢點。近年來，有許多RkNN查詢被提出在許多運用上，像是在基於數據的市場營銷、資源分配、決策支援系統等等。對於RkNN查詢來說，查詢點和資料點之間有一個基於反向的影響程度關係，也就是說當查詢點為某一資料點的最近鄰近點時，查詢點對此資料點的影響程度最大。在本文章中，提出一個前n項反向最鄰近點查詢(Top-n Reverse Nearest Neighbor query, TnRNN)問題，此查詢需找出前n項最受到查詢點影響的一組資料點。利用一個六角搜尋技巧來處理此查詢，此方法不需做任何的預先處理，而且利用六角特性來限定範圍找尋前n項最被查詢點影響的一組資料點，避免造成不必要的搜尋花費。實驗結果顯示出當執行大量資料點進行查詢運算時，六角搜尋演算法會明顯地優於現階段目前對於TnRNN問題的解決技巧。

A Reverse Nearest Neighbor query (RNN) retrieves data points at which the query point is their nearest neighbor. A generalization of RNN is the Reverse k Nearest Neighbor query (RkNN) that retrieves data points at which the query point is within their k nearest neighbors. Recently, many applications of RkNN are proposed, such as profile-based marketing, resource allocation, decision support systems, etc. For RkNN query, there is a degree of influence for the reverse relation between query point q and data point p. That is, when q is the nearest neighbor of p, it can be said that p is the most influenced by q. In this paper, a study of the Top-n Reverse Nearest Neighbor (TnRNN) query problem is proposed, where the retrieved n data points are the most influenced points of the query point. An efficient algorithm called Hexangular Search for TnRNN processing. This approach does not need to do any pre-processing, it applies the Hexangular property of RkNN, which restricts the searching range of the query, and iteratively searches the data points until n most influenced data points are found. Experiments are conducted to show that the Hexangular Search algorithm outperforms previous techniques on TnRNN query when the amount of data is large.

[1] K. Lee, B. Zheng, and W.-C. Lee, ``Ranked reverse nearest neighbor search,'' IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 7, pp. 894--910, 2008.
[2] I. Stanoi, D. Agrawal, and A. E. Abbadi, ``Reverse nearest neighbor queries for dynamic databases,'' in Proc. ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 44--53, 2000.
[3] F. Korn and S. Muthukrishnan, ``Influence sets based on reverse nearest neighbor queries,'' in Proc. the 2000 ACM SIGMOD international conference on Management of data, pp. 201--212, ACM, 2000.
[4] H.-P. Kriegel, P. Kroger, M. Renz, A. Zufle, and A. Katzdobler, ``Incremental reverse nearest neighbor ranking,'' in Proc. IEEE International Conference on Data Engineering (ICDE), pp. 1560--1567, 2009.
[5] J. Kang, M. Mokbel, S. Shekhar, T. Xia, and D. Zhang, ``Incremental and general evaluation of reverse nearest neighbors,'' IEEE Transactions on Knowledge and Data Engineering, vol. 22, no. 7, pp. 983--999, 2010.
[6] X. Ma, C. Zhang, S. Shekhar, Y. Huang, and H. Xiong, ``On multi-type reverse nearest neighbor search,'' Data & Knowledge Engineering, vol. 70, pp. 955--983, Nov. 2011.
[7] A. Singh, H. Ferhatosmanoglu, and A. c. Tosun, ``High dimensional reverse nearest neighbor queries,'' in Proc. the twelfth international conference on Information and knowledge management(CIKM), pp. 91--98, 2003.
[8] C. Yang and K.-I. Lin, ``An index structure for efficient reverse nearest neighbor queries,'' in Proc. 17th International Conference on Data Engineering (ICDE), pp. 485--492, 2001.
[9] C. Xia, W. Hsu, and M. L. Lee, ``Erknn: efficient reverse k-nearest neighbors retrieval with local knn-distance estimation,'' in Proc. the 14th ACM international conference on Information and knowledge management(CIKM), pp. 533--540, 2005.
[10] Y. Tao, D. Papadias, and X. Lian, ``Reverse knn search in arbitrary dimensionality,'' in Proc. the Thirtieth international conference on Very large data bases, pp. 744--755, VLDB Endowment, 2004.
[11] W. Wu, F. Yang, C.-Y. Chan, and K.-L. Tan, ``Finch: evaluating reverse k-nearestneighbor queries on location data,'' Proc. VLDB Endow., vol. 1, pp. 1056--1067, Aug. 2008.
[12] M. Cheema, X. Lin, W. Zhang, and Y. Zhang, ``Influence zone: Efficiently processing reverse k nearest neighbors queries,'' in Proc. IEEE 27th International Conference on Data Engineering (ICDE), pp. 577--588, 2011.
[13] K. C. K. Lee, M. Ye, and W.-C. Lee, ``Reverse ranking query over imprecise spatial data,'' in Proc. 1st International Conference and Exhibition on Computing for Geospatial Research & Application, pp. 17:1--17:8, ACM, 2010.
[14] Y. Gao, B. Zheng, G. Chen, W.-C. Lee, K. Lee, and Q. Li, ``Visible reverse k-nearest neighbor query processing in spatial databases,'' IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 9, pp. 1314--1327, 2009.
[15] R. C.-W. Wong, M. T. Ozsu, P. S. Yu, A. W.-C. Fu, and L. Liu, ``Efficient method for maximizing bichromatic reverse nearest neighbor,'' Proc. VLDB Endow., vol. 2, pp. 1126--1137, Aug. 2009.
[16] Z. Zhou, W. Wu, X. Li, M. L. Lee, and W. Hsu, ``Maxfirst for maxbrknn,'' in Proc. IEEE 27th International Conference on Data Engineering (ICDE), pp. 828--839, 2011.
[17] T. Xia and D. Zhang, ``Continuous reverse nearest neighbor monitoring,'' in Proc. the 22nd International Conference on Data Engineering (ICDE), pp. 77--77, 2006.
[18] W. Wu, F. Yang, C.-Y. Chan, and K.-L. Tan, ``Continuous reverse k-nearestneighbor monitoring,'' in Proc. International Conference on Mobile Data Management (MDM), pp. 132--139, 2008.
[19] J. Kang, M. Mokbel, S. Shekhar, T. Xia, and D. Zhang, ``Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors,'' in Proc. IEEE 23rd International Conference on Data Engineering (ICDE), pp. 806--815, 2007.
[20] R. Benetis, S. Jensen, G. Karĉiauskas, and S. Ŝaltenis, ``Nearest and reverse nearest neighbor queries for moving objects,'' The VLDB Journal, vol. 15, pp. 229--249, Sept. 2006.
[21] M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li, ``Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks,'' The VLDB Journal, vol. 21, pp. 69--95, Feb. 2012.
[22] B. Yao, F. Li, and P. Kumar, ``Reverse furthest neighbors in spatial databases,'' in Proc. IEEE 25th International Conference on Data Engineering (ICDE), pp. 664--675, 2009.
[23] M. L. Yiu, D. Papadias, N. Mamoulis, and Y. Tao, ``Reverse nearest neighbors in large graphs,'' IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 4, pp. 540--553, 2006.
[24] Y. Tao, M. L. Yiu, and N. Mamoulis, ``Reverse nearest neighbor search in metric spaces,'' IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 9, pp. 1239--1252, 2006.
[25] E. Achtert, C. Bohm, P. Kroger, P. Kunath, A. Pryakhin, and M. Renz, ``Efficient reverse k-nearest neighbor search in arbitrary metric spaces,'' in Proc. the 2006 ACM SIGMOD international conference on Management of data, pp. 515--526, 2006.
[26] M. L. Yiu and N. Mamoulis, ``Reverse nearest neighbors search in ad hoc subspaces,'' IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 3, pp. 412--426, 2007.
[27] X. Lian and L. Chen, ``Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data,'' The VLDB Journal, vol. 18, pp. 787--808, June 2009.
[28] T. Bernecker, T. Emrich, H.-P. Kriegel, M. Renz, S. Zankl, and A. Zufle, ``Efficient probabilistic reverse nearest neighbor query processing on uncertain data,'' Proc. VLDB Endow., vol. 4, pp. 669--680, July 2011.