Optimal-nearest-neighbor queries

Gao Yunjun, Zhang Jing, Chen Gencai, Li Qing, Liu Shen, Chen Chun

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Pages1454-1456
Number of pages3
DOIs
Publication statusPublished - 1 Oct 2008
Externally publishedYes
Event2008 IEEE 24th International Conference on Data Engineering, ICDE'08 - Cancun, Mexico
Duration: 7 Apr 200812 Apr 2008

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Conference

Conference2008 IEEE 24th International Conference on Data Engineering, ICDE'08
CountryMexico
CityCancun
Period7/04/0812/04/08

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Cite this