Exact and approximate flexible aggregate similarity search
Exact and approximate flexible aggregate similarity search
复制标题
DOI：
10.1007/s00778-015-0418-x
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Feifei Li;K. Yi;Yufei Tao;Bin Yao;Y. Li;Dong Xie;Min Wang
中科院分区：
文献类型：
--
作者：
Feifei Li;K. Yi;Yufei Tao;Bin Yao;Y. Li;Dong Xie;Min Wang
聚合相似性搜索，也称为聚合最近邻查询，在空间数据库和多媒体数据库中有许多有用的应用。给定M个查询对象的组Q，它从数据库中检索与Q最相似的对象，其中相似性是聚合（例如，，）每个检索对象和Q中所有对象之间的距离。在本文中，我们提出了一个额外的灵活性的查询定义，其中的相似性是一个聚合之间的距离p和任何子集的对象在Q为some的支持。我们称这个新定义为灵活的聚合相似性搜索，并相应地将查询称为灵活的聚合最近邻（Fann）查询。我们提出的算法answeringFann查询准确和近似。我们的近似算法是特别有吸引力的，这是简单的，高效的，并在低维和高维工作。它们还返回接近最优的答案，并保证在任何维度上都是常数因子近似。在2维到74维的大型真实的和合成数据集上的大量实验证明了它们的上级效率和高质量。
Aggregate similarity search, also known as aggregate nearest-neighbor (Ann) query, finds many useful applications in spatial and multimedia databases. Given a groupQofMquery objects, it retrieves from a database the objects most similar toQ, where the similarity is an aggregation (e.g.,,) of the distances between each retrieved objectpandallthe objects inQ. In this paper, we propose an added flexibility to the query definition, where the similarity is an aggregation over the distances betweenpand any subset ofobjects inQfor somesupport. We call this new definitionflexible aggregate similarity searchand accordingly refer to a query as aflexible aggregate nearest-neighbor (Fann) query. We present algorithms for answeringFannqueries 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 near-optimal 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.