近年來，隨著全球定位系統與無線通訊技術的進步，以位置為基礎的服務已成為行動計算領域最為流行的服務之一。
排序型反向最近鄰居查詢(Ranked Reverse Nearest Neighbor, RRNN)是一種新興起的空間查詢，在RRNN查詢中，會回傳被查詢點影響最多的t個節點，基本的概念是，依序回傳查詢點之R1NN、R2NN...的結果，直到所得到的節點數滿足t個為止。由於RRNN可依照被查詢點影響的程度，依序回傳t個被查詢點影響最多的節點，因此相較於RkNN查詢，RRNN查詢增強了功能與實用性，
為了有效率地解決RRNN查詢問題，我們提出了一種結合現有RkNN查詢之方法，首先，對每個節點使用kmin來記錄節點被影響程度之下界，其次，在驗證步驟中，我們發現一些特性，能更新節點之kmin，並證明此特性是可行並且可靠的，最後將與現有的方法做比較，證明我們的方法能有效地減少計算量，減輕伺服器的負擔，並提升系統效能。

In recent years, due to the advancement of the positioning system and wireless communication technologies, the location based service has been one of the most popular services in mobile computing systems.
Ranked Reverse Nearest Neighbor (RRNN) query is a new issue in spatial query. RRNN is extended from Reverse k Nearest Neighbor (RkNN) query. In RRNN problem, it has to retrieves t data points that are most influenced by query point. The basic idea is it first acquire the R1NN result, and then R2NN result ... and so on as the required number t achieved. It is functionally more powerful and more informative than RkNN as it can report the top t most influenced data points with their degrees of influence.
To answer this RRNN query more efficiently, we propose a solution combining the advantages of the existing method in RkNN. First, for every data point, we use kmin to record the lower bound of influence degree of corresponding query point. Second, in verification step, we discover some characteristics that can be used to update data points’ kmin. We have also proved that our approach is feasible and reliable. Last, we show that our method can reduce computing cost and performs more efficiently compared with existing solutions.

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, vol. 40, no. 8, pp. 102-114, 2002.
[2] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles,”Proc. ACM SIGMOD, pp. 322-331, May 1990.
[3] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis, "Nearest neighbor and reverse nearest neighbor queries for moving objects," in Proc. International Database Engineering and Applications Symposium, 2002, pp. 44-53.
[4] M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang, "Continuous Monitoring of Distance-Based Range Queries," IEEE Transactions on Knowledge and Data Engineering, vol. 23, pp. 1182-1199, 2011.
[5] M. A. Cheema, W. Zhang, X. Lin, and Y. Zhang, "Efficiently processing snapshot and continuous reverse k nearest neighbors queries," The VLDB Journal, pp. 1-26, 2012.
[6] 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, 2012.
[7] Y. Congyun and L. King-Ip, "An index structure for efficient reverse nearest neighbor queries," in Proc. IEEE 17th International Conference on Data Engineering, 2001, pp. 485-492.
[8] A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," in Proc. ACM International Conference on Management of Data (SIGMOD), 1984, pp. 47-57.
[9] N. Hoong Kee, L. Hon Wai, and H. Ngai Lam, "Efficient algorithm for path-based range query in spatial databases," in Proc. International Database Engineering and Applications Symposium, 2004, pp. 334-343.
[10] J. M. Kang, M. F. Mokbel, S. Shekhar, X. Tian, and Z. Donghui, "Incremental and General Evaluation of Reverse Nearest Neighbors," IEEE Transactions on Knowledge and Data Engineering, vol. 22, pp. 983-999, 2010.
[11] R. Katz, E. Brewer, E. Amir, H. Balakrishnan, A. Fox, S. Gribble, T. Hodes, D. Jiang, G. Nguyen, and V. Padmanabhan, "The Bay Area Research Wireless Access Network (BARWAN)," in Proc. Technologies for the Information Superhighway Digest of Papers (Compcon'96), 1996, pp. 15-20.
[12] I. Lazaridis and S. Mehrotra, “Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure,” Proc. ACM SIGMOD ’01, pp. 401-412, May 2001.
[13] K.C.K. Lee, B. Zheng, and W.C. Lee, “Ranked Reverse Nearest Neighbor Search,”IEEE Trans. Knowledge and Data Eng., vol. 20, no. 7, pp. 894-910, July 2008.
[14] B. Rao and L. Minakakis, "Evolution of Mobile Location-based Services," Communications of the ACM, vol. 46, p. 65, 2003.
[15] Nick Roussopoulos, Stephen Kelley, and Frederic Vincent. Nearest neighbor queries. In Procs. of ACM SIGMOD Conference on Management of Data, pages 71–79, 1995
[16] D. A. I. Stanoi, 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, 2000, pp. 44-53.
[17] Y. Tao, D. Papadias, and X. Lian, "Reverse kNN search in arbitrary dimensionality," in Proc. the Thirtieth international conference on Very large data bases - Volume 30, 2004, pp. 744-755.
[18] X. Tian and Z. Donghui, "Continuous Reverse Nearest Neighbor Monitoring," in Proc. IEEE 22nd International Conference on Data Engineering, 2006, pp. 77-77.
[19] W. Wei, Y. Fei, C. Chee Yong, and T. Kian-Lee, "Continuous Reverse k-Nearest-Neighbor Monitoring," in Proc. IEEE 9th International Conference on Mobile Data Management, 2008, pp. 132-139.
[20] W. Wu, F. Yang, C.-Y. Chan, and K.-L. Tan, "FINCH: evaluating reverse k-Nearest-Neighbor queries on location data," in Proc. VLDB Endow., 2008, pp. 1056-1067.
[21] T. Xia and D. Zhang, "Continuous reverse nearest neighbor monitoring," in ICDE, p. 77 (2006)
[22] Bluetooth.org, https://www.bluetooth.org/apps/content/
[23] IEEE 802.15 WPAN Task Group 4, http://www.ieee802.org/15/pub/TG4.html
[24] LTE 3GPP homepage, http://www.3gpp.org/article/lte
[25] WiFi Alliance, http://www.wi-fi.org/
[26] WiMAX Forum, http://www.wimaxforum.org/
[27] ZigBee Alliance, http://www.zigbee.org/