DocumentCode :
1338820
Title :
Group Enclosing Queries
Author :
Li, Feifei ; Yao, Bin ; Kumar, Piyush
Author_Institution :
Comput. Sci. Dept., Florida State Univ., Tallahassee, FL, USA
Volume :
23
Issue :
10
fYear :
2011
Firstpage :
1526
Lastpage :
1540
Abstract :
Given a set of points P and a query set Q, a group enclosing query (Geq) fetches the point p* ∈ P such that the maximum distance of p* to all points in Q is minimized. This problem is equivalent to the Min-Max case (minimizing the maximum distance) of aggregate nearest neighbor queries for spatial databases. This work first designs a new exact solution by exploring new geometric insights, such as the minimum enclosing ball, the convex hull, and the furthest voronoi diagram of the query group. To further reduce the query cost, especially when the dimensionality increases, we turn to approximation algorithms. Our main approximation algorithm has a worst case √2-approximation ratio if one can find the exact nearest neighbor of a point. In practice, its approximation ratio never exceeds 1.05 for a large number of data sets up to six dimensions. We also discuss how to extend it to higher dimensions (up to 74 in our experiment) and show that it still maintains a very good approximation quality (still close to 1) and low query cost. In fixed dimensions, we extend the √2-approximation algorithm to get a (1 + ε)-approximate solution for the Geq problem. Both approximation algorithms have O(log N + M) query cost in any fixed dimension, where N and M are the sizes of the data set P and query group Q. Extensive experiments on both synthetic and real data sets, up to 10 million points and 74 dimensions, confirm the efficiency, effectiveness, and scalability of the proposed algorithms, especially their significant improvement over the state-of-the-art method.
Keywords :
computational complexity; computational geometry; minimax techniques; minimisation; query processing; Voronoi diagram; aggregate nearest neighbor query; approximation algorithm; approximation ratio; convex hull; data set size; group enclosing query; maximum distance minimization; min-max case; minimum enclosing ball; query cost reduction; query set; spatial database; Aggregates; Algorithm design and analysis; Approximation algorithms; Approximation methods; Artificial neural networks; Nearest neighbor searches; Spatial databases; Aggregate nearest neighbor; approximate nearest neighbor; minmax nearest neighbor; nearest neighbor.;
fLanguage :
English
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1041-4347
Type :
jour
DOI :
10.1109/TKDE.2010.181
Filename :
5590242
Link To Document :
بازگشت