Efficient top-K approximate searches against a relation with multiple attributes
Efficient top-K approximate searches against a relation with multiple attributes
复制标题
DOI：
10.1007/s11280-011-0137-1
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Wei Lu;Jinchuan Chen;Xiaoyong Du;Jieping Wang;Wei Pan
中科院分区：
文献类型：
--
作者：
Wei Lu;Jinchuan Chen;Xiaoyong Du;Jieping Wang;Wei Pan
本文研究了如何有效地确定与给定查询记录最相似的K个记录的问题，其中相似度定义为：（1）对于每个记录，我们使用一个特定的相似度函数计算该记录与查询记录在每个属性上的相似度得分;（2）利用聚合函数将这些相似度分数与权重结合联合收割机，并将聚合值作为记录的相似度。在计算所有记录的相似度之后，可以进一步识别具有最大相似度的K个记录。在这个框架下，不幸的是，当关系的基数很大时，计算成本将是非常昂贵的，因为需要计算每个记录的相似度。因此，在本文中，我们提出了两个有效的算法，命名为ScanIndex和自顶向下（TD），以科普这个问题。关于ScanIndex，在各个属性上等于零的相似性分数是免费的。基于ScanIndex，关于TD，跳过在各个属性上小于阈值（而不是零）的相似性分数，其中这些阈值随时间动态地改进。实验结果表明，与朴素的方法相比，使用ScanIndex和TD的性能可以提高两个数量级。
In this paper, we study the problem of efficiently identifyingKrecords that are most similar to a given query record, where the similarity is defined as: (1) for each record, we calculate the similarity score between the record and the query record over each individual attribute using a specific similarity function; (2) an aggregate function is utilized to combine these similarity scores with weights and the aggregated value is served as the similarity of the record. After similarities of all records have been computed,Krecords with the greatest similarities can further be identified. Under this framework, unfortunately, the computational cost will be extremely expensive when the cardinality of relation is large as computation of similarity for each record is required. As a result, in this paper, we propose two efficient algorithms, named ScanIndex and Top-Down (TD for short), to cope with this problem. With respect to ScanIndex, similarity scores that are equal to zero over individual attributes are free from computation. Based on ScanIndex, with respect to TD, similarity scores less than thresholds (rather than zero) over individual attributes are skipped, where these thresholds are improved dynamically over time. Experimental results demonstrate that, comparing with the naive approach, the performance can be improved by two orders of magnitude using ScanIndex and TD.