信息检索里面经典问题。
精确top K 检索及其加速办法
•方法一：快速计算余弦
• 方法二：堆排序法N中选K
• 方法三：提前终止计算
精确top K检索加速方法一：
快速计算余弦 • 检索排序就是找查询的K近邻 • 一般而言，在高维空间下，计算余弦相似度没有很 高效的方法 • 但是如果查询很短，是有一定办法加速计算的，而 且普通的索引能够支持这种快速计算
特例– 不考虑查询词项的权重 • 查询词项无权重 • 相当于假设每个查询词项都出现1次 • 于是，不需要对查询向量进行归一化 • 可以对上一讲给出的余弦相似度计算算法进行轻微的简化
精确top k检索加速方法二：
堆排序法N中选K • 检索时，通常只需要返回前K条结果 • 可以对所有的文档评分后排序，选出前K个结果，但是这 个排序过程可以避免 • 令 J = 具有非零余弦相似度值的文档数目 • 从J中选K个最大的
技巧：相似度为0的不参与建堆（减少建堆开销）
精确top K 检索加速方法三：
提前终止计算
• 到目前为止的倒排记录表都按照docID排序
• 接下来将采用与查询无关的另外一种反映结果好坏程度 的指标(静态质量)
• 例如: 页面d的PageRank g(d), 就是度量有多少好页面指向d的一 种指标 (《信息检索导论》参考第 21章)
• 于是可以将文档按照PageRank排序 g(d1) > g(d2) > g(d3) > . . . • 将PageRank和余弦相似度线性组合得到文档的最后得分 net-score(q, d) = g(d) + cos(q, d)
提前终止计算
• 假设:
• (i) g → [0, 1];
• (ii) 检索算法按照d1,d2,…，依次计算(为文档为单位 的计算，document-at-a-time)，当前处理的文档的 g(d) < 0.1；
• (iii) 而目前找到的top K 的得分中最小的都 > 1.2 • 由于后续文档的得分不可能超过1.1 ( cos(q,d) <1 ) • 所以，我们已经得到了top K结果，不需要再进行 后续计算
非精确top K检索 （详情待写）
• 策略一：索引去除(Index elimination)
• 策略二：胜者表
• 策略三：静态得分
• 策略四：影响度排序
• 策略五：簇剪枝方法——预处理
• 策略六：参数化索引以及域索引
• 策略七：层次索引