TY - GEN
T1 - Optimal-nearest-neighbor queries
AU - Yunjun, Gao
AU - Jing, Zhang
AU - Gencai, Chen
AU - Qing, Li
AU - Shen, Liu
AU - Chun, Chen
PY - 2008
Y1 - 2008
N2 - Given two sets DA and DB of multidimensional objects, a spatial region R, and a critical distance dc, an optimal-nearestneighbor (ONN) query retrieves outside R, the object in D B with maximum optimality. Let CAR (Sp, p) be the cardinality of the subset Sp of objects in DA which locate within R and are enclosed by the vicinity circle centered at p with radius dc. Then, an object o is said to be better than another one o′ if (i) CAR (So, o) > CAR (S0′ o′), or (ii) when CAR (So, o) = CAR (So′, o′) the sum of the weighted distance from each object in So to o is smaller than the sum of the weighted distance between every object in So′: and o′. This type of queries is quite useful in many decision making applications. In this paper, we formalize the ONN query, develop the optimality metric, and propose several algorithms for finding optimal nearest neighbors efficiently. Our techniques assume that both DA and DB are indexed by R-trees. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets. © 2008 IEEE.
AB - Given two sets DA and DB of multidimensional objects, a spatial region R, and a critical distance dc, an optimal-nearestneighbor (ONN) query retrieves outside R, the object in D B with maximum optimality. Let CAR (Sp, p) be the cardinality of the subset Sp of objects in DA which locate within R and are enclosed by the vicinity circle centered at p with radius dc. Then, an object o is said to be better than another one o′ if (i) CAR (So, o) > CAR (S0′ o′), or (ii) when CAR (So, o) = CAR (So′, o′) the sum of the weighted distance from each object in So to o is smaller than the sum of the weighted distance between every object in So′: and o′. This type of queries is quite useful in many decision making applications. In this paper, we formalize the ONN query, develop the optimality metric, and propose several algorithms for finding optimal nearest neighbors efficiently. Our techniques assume that both DA and DB are indexed by R-trees. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets. © 2008 IEEE.
UR - http://www.scopus.com/inward/record.url?scp=52649149532&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-52649149532&origin=recordpage
U2 - 10.1109/ICDE.2008.4497587
DO - 10.1109/ICDE.2008.4497587
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781424418374
SP - 1454
EP - 1456
BT - Proceedings - International Conference on Data Engineering
T2 - 2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Y2 - 7 April 2008 through 12 April 2008
ER -