Optimal-Nearest-Neighbor Queries
Yunjun Gao, Jing Zhang, Gencai Chen, Qing Li, Shen Liu, Chun Chen · 2008
Given two sets DAand DBof multidimensional objects, a spatial region R, and a critical distance dc, an optimal-nearest- neighbor (ONN) query retrieves outside R, the object in DBwith maximum optimality. Let CAR (Sp,p) be the cardinality of the subset Sp of objects in DAwhich locate within R and are enclosed by the vicinity circle centered at p with radius dc. Then, an objectois said to be better than another one o' if (i) CAR (So,o) = CAR (So,o'), or (ii) when CAR (So,o) = CAR (So',o') the sum of the weighted distance from each object in Sotoois 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 DAand DBare indexed by R-trees. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets.