TY - JOUR
T1 - Ranked reverse nearest neighbor search
AU - Lee, Ken C.K.
AU - Zheng, Baihua
AU - Lee, Wang Chien
N1 - Funding Information:
Wang-Chien Lee and Ken C.K. Lee were supported in part by the US National Science Foundation under Grant IIS-0328881, Grant IIS-0534343, and Grant CNS-0626709.
PY - 2008/7
Y1 - 2008/7
N2 - Given a set of data points p and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in p whose nearest neighbors (NNs) are q. Reverse k-NN (RkNN) query (where k ≥ 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have an influence on all those answer data points. The degree of q's influence on a data point p (ε p) is denoted by κP, where q Is the κpth NN of p. We introduce a new variant of RNN query, namely, Ranked RNN (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest κS with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, κ-Counting and κ-Browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.
AB - Given a set of data points p and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in p whose nearest neighbors (NNs) are q. Reverse k-NN (RkNN) query (where k ≥ 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have an influence on all those answer data points. The degree of q's influence on a data point p (ε p) is denoted by κP, where q Is the κpth NN of p. We introduce a new variant of RNN query, namely, Ranked RNN (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest κS with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, κ-Counting and κ-Browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.
UR - http://www.scopus.com/inward/record.url?scp=44649200433&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=44649200433&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2008.36
DO - 10.1109/TKDE.2008.36
M3 - Article
AN - SCOPUS:44649200433
SN - 1041-4347
VL - 20
SP - 894
EP - 910
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 7
M1 - 4445674
ER -