Full Citation
Title: Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates
Citation Type: Conference Paper
Publication Year: 2015
ISBN:
ISSN:
DOI:
NSFID:
PMCID:
PMID:
Abstract: In many domains such as computational geometry and database management, an object may be described by multiple instances (points). Then the distance (or similarity) between two objects is captured by the pair-wise distances among their instances. In the past, numerous nearest neighbor (NN) functions have been proposed to define the distance between objects with multiple instances and to identify the NN object. Nevertheless, considering that a user may not have a specific NN function in mind, it is desirable to provide her with a set of NN candidates. Ideally, the set of NN candidates must include every object that is NN for at least one of the NN functions and must exclude every nonpromising object. However, no one has studied the problem of NN candidates computation from this perspective. Although some of the existing works aim at returning a set of candidate objects, they do not focus on the NN functions while computing the candidate objects. As a result, they either fail to include an NN object w.r.t. some NN functions or include a large number of unnecessary objects that have no potential to be the NN regardless of the NN functions. Motivated by this, we classify the existing NN functions for objects with multiple instances into three families by characterizing their key features. Then, we advocate three spatial dominance operators to compute NN candidates where each operator is optimal w.r.t. different coverage of NN functions. Efficient algorithms are proposed for the dominance check and corresponding NN candidates computation. Extensive empirical study on real and synthetic datasets shows that our proposed operators can significantly reduce the number of NN candidates. The comprehensive performance evaluation demonstrates the efficiency of our computation techniques.
Url: http://www.aamircheema.com/research/SIGMOD2015_SpatialDominance.pdf
User Submitted?: No
Authors: Wang, Xiaoyang; Zhang, Ying; Zhang, Wenjie; Lin, Xuemin; Cheema, Muhammad A
Conference Name: SIGMOD
Publisher Location: Melbourne, Victoria, Australia
Data Collections: IPUMS USA
Topics: Methodology and Data Collection
Countries: