Flexible aggregate similarity search
Authors:
Open Access
- 12 June 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1009-1020
Abstract
Aggregate similarity search, a.k.a. aggregate nearest neighbor (Ann) query, finds many useful applications in spatial and multimedia databases. Given a group Q of M query objects, it retrieves the most (or top-k) similar object to Q from a database P, where the similarity is an aggregation (e.g., sum, max) of the distances between the retrieved object p and all the objects in Q. In this paper, we propose an added flexibility to the query definition, where the similarity is an aggregation over the distances between p and any subset of φM objects in Q for some support 0 < φ ≤ 1. We call this new definition flexible aggregate similarity (Fann) search, which generalizes the Ann problem. Next, we present algorithms for answering Fann queries exactly and approximately. Our approximation algorithms are especially appealing, which are simple, highly efficient, and work well in both low and high dimensions. They also return nearoptimal answers with guaranteed constant-factor approximations in any dimensions. Extensive experiments on large real and synthetic datasets from 2 to 74 dimensions have demonstrated their superior efficiency and high quality. © 2011 ACMKeywords
This publication has 16 references indexed in Scilit:
- Two ellipse-based pruning methods for group nearest neighbor queries2005
- iDistanceACM Transactions on Database Systems, 2005
- Aggregate nearest neighbor queries in spatial databasesACM Transactions on Database Systems, 2005
- Approximate minimum enclosing balls in high dimensions using core-setsACM Journal of Experimental Algorithmics, 2003
- Efficient similarity search and classification via rank aggregation2003
- Optimal aggregation algorithms for middleware2001
- A cost model for query processing in high dimensional data spacesACM Transactions on Database Systems, 2000
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- An optimal algorithm for approximate nearest neighbor searching fixed dimensionsJournal of the ACM, 1998
- Nearest neighbor queries1995