Flexible aggregate similarity search
Flexible aggregate similarity search
复制标题
DOI：
10.1145/1989323.1989429
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Y. Li;Feifei Li;K. Yi;Bin Yao;Min Wang
中科院分区：
文献类型：
--
作者：
Y. Li;Feifei Li;K. Yi;Bin Yao;Min Wang
聚合相似度搜索，又称聚合最近邻查询，在空间数据库和多媒体数据库中有着广泛的应用。给定一组问M查询对象,它检索最(或top-k)相似的对象从数据库P, Q相似性的一个聚合(如总和,max) P和所有对象检索到的对象之间的距离在问:在本文中,我们提出一个额外的灵活性,查询定义,相似性是一个聚合的P和任何子集之间的距离ÆM对象在问一些支持0 <Æd 1。我们把这个新定义称为柔性聚合相似度搜索（Fann），它对Ann问题进行了推广。接下来，我们提出了精确和近似地回答范恩查询的算法。我们的近似算法特别吸引人，它简单，高效，在低维和高维上都能很好地工作。它们还返回在任何维度上都有保证的常因子近似值的近似最优答案。在2到74维的大型真实数据集和合成数据集上进行的大量实验表明，该方法具有优越的效率和高质量。
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 < Æ d 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.