Optimal-nearest-neighbor queries

被引：0

作者：

Gao, Yunjun ^{[1
]}

Zhang, Jing ^{[1
]}

Chen, Gencai ^{[1
]}

Li, Qing ^{[2
]}

Liu, Shen ^{[1
]}

Chen, Chun ^{[1
]}

机构：

[1] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Peoples R China

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

来源：

2008 IEEE 24TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, VOLS 1-3 | 2008年

关键词：

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given two sets D-A and D-B of multidimensional objects, a spatial region R, and a critical distance d(c), an optimal-nearest-neighbor (ONN) query retrieves outside R, the object in DB with maximum optimality. Let CAR (S-p, p) be the cardinality of the subset S, 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 (S-o, o) > CAR (S-o ',S- o '), or (ii) when CAR (S-o, o) = CAR (S-o ',S- o ') the sum of the weighted distance from each object in S, to o is smaller than the sum of the weighted distance between every object in S., and W. 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.

引用

页码：1454 / +

页数：2