|
Published Articles >> Table of Contents >> Abstract
September 2006 (Vol. 18, No. 9)
pp. 1239-1252
Reverse Nearest Neighbor Search in Metric Spaces
Yufei Tao
Man Lung Yiu
Nikos Mamoulis
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TKDE.2006.148
Send link to a friend
| Abstract |
|
Given a set {\cal D} of objects, a reverse nearest neighbor (RNN) query returns the objects o in {\cal D} such that o is closer to a query object q than to any other object in {\cal D}, according to a certain similarity metric. The existing RNN solutions are not sufficient because they either 1) rely on precomputed information that is expensive to maintain in the presence of updates or 2) are applicable only when the data consists of "Euclidean objects” and similarity is measured using the L_2 norm. In this paper, we present the first algorithms for efficient RNN search in generic metric spaces. Our techniques require no detailed representations of objects, and can be applied as long as their mutual distances can be computed and the distance metric satisfies the triangle inequality. We confirm the effectiveness of the proposed methods with extensive experiments.
|
 References
|
[1] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles, ” Proc. SIGMOD Conf., pp. 322-331, 1990.
[2] R. Benetis, C.S. Jensen, G. Karciauskas, and S. Saltenis, “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects,” Proc. Int'l Database Eng. and Applications Symp. (IDEAS), pp. 44-53, 2002.
[3] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Springer, 2000.
[4] M.M. Breunig, H.-P. Kriegel, R.T. Ng, and J. Sander, “LOF: Identifying Density-Based Local Outliers,” Proc. SIGMOD Conf., pp. 93-104, 2000.
[5] P. Ciaccia and M. Patella, “Searching in Metric Spaces with User-Defined and Approximate Distances,” ACM Trans. Database Systems, vol. 27, no. 4, pp. 398-437, 2002.
[6] P. Ciaccia, M. Patella, and P. Zezula, “M-Tree: An Efficient Access Method for Similarity Search in Metric Spaces,” Proc. Very Large Data Bases Conf. (VLDB), pp. 426-435, 1997.
[7] P. Ciaccia, M. Patella, and P. Zezula, “A Cost Model for Similarity Queries in Metric Spaces,” Proc. Symp. Principles of Database Systems (PODS), pp. 59-68, 1998.
[8] H. Ferhatosmanoglu, I. Stanoi, D. Agrawal, and A.E. Abbadi, “Constrained Nearest Neighbor Queries, Proc. Symp. Spatial and Temporal Databases (SSTD), pp. 257-278, 2001.
[9] G.R. Hjaltason and H. Samet, “Distance Browsing in Spatial Databases,” ACM Trans. Database Systems, vol. 24, no. 2, pp. 265-318, 1999.
[10] G.R. Hjaltason and H. Samet, “Index-Driven Similarity Search in Metric Spaces,” ACM Trans. Database Systems, vol. 28, no. 4, pp. 517-580, 2003.
[11] F. Korn and S. Muthukrishnan, “Influence Sets Based on Reverse Nearest Neighbor Queries,” Proc. SIGMOD Conf., pp. 201-212, 2000.
[12] K.-I. Lin, M. Nolen, and C. Yang, “Applying Bulk Insertion Techniques for Dynamic Reverse Nearest Neighbor Problems,” Proc. Int'l Database Eng. and Applications Symp. (IDEAS), pp. 128-132, 2002.
[13] A. Maheshwari, J. Vahrenhold, and N. Zeh, “On Reverse Nearest Neighbor Queries,” Proc. Canadian Conf. Computational Geometry (CCCG), pp. 128-132, 2002.
[14] A. Nanopoulos, Y. Theodoridis, and Y. Manolopoulos, “C2P: Clustering Based on Closest Pairs,” Proc. Very Large Data Bases Conf. (VLDB), pp. 331-340, 2001.
[15] S. Ramaswamy, R. Rastogi, and K. Shim, “Efficient Algorithms for Mining Outliers from Large Data Sets,” Proc. SIGMOD Conf., pp. 427-438, 2000.
[16] N. Roussopoulos, S. Kelley, and F. Vincent, Nearest Neighbor Queries, Proc. SIGMOD Conf., pp. 71-79, 1995.
[17] A. Singh, H. Ferhatosmanoglu, and A.S. Tosun, “High Dimensional Reverse Nearest Neighbor Queries,” Proc. Conf. Information and Knowledge Management (CIKM), pp. 91-98, 2003.
[18] I. Stanoi, D. Agrawal, and A.E. Abbadi, “Reverse Nearest Neighbor Queries for Dynamic Databases,” Proc. ACM SIGMOD Workshop, pp. 744-755, 2000.
[19] Y. Tao, D. Papadias, and X. Lian, “Reverse kNN Search in Arbitrary Dimensionality,” Proc. Very Large Data Bases Conf. (VLDB), pp. 744-755, 2004.
[20] C. Yang and K.-I. Lin, “An Index Structure for Efficient Reverse Nearest Neighbor Queries,” Proc. Int'l Conf. Data Eng. (ICDE), pp. 485-492, 2001.
|
 Additional Information
|
Index Terms- Reverse nearest neighbor, metric space.
Citation:
Yufei Tao, Man Lung Yiu, Nikos Mamoulis,
"Reverse Nearest Neighbor Search in Metric Spaces,"
IEEE Transactions on Knowledge and Data Engineering,
vol. 18,
no. 9,
pp. 1239-1252,
Sept.,
2006
|
|
RSS Feed