信息检索里面经典问题。
精确top K 检索及其加速办法
?方法一：快速计算余弦
? 方法二：堆排序法N中选K
? 方法三：提前终止计算
精确top K检索加速方法一：
快速计算余弦 ? 检索排序就是找查询的K近邻 ? 一般而言，在高维空间下，计算余弦相似度没有很 高效的方法 ? 但是如果查询很短，是有一定办法加速计算的，而 且普通的索引能够支持这种快速计算
特例– 不考虑查询词项的权重 ? 查询词项无权重 ? 相当于假设每个查询词项都出现1次 ? 于是，不需要对查询向量进行归一化 ? 可以对上一讲给出的余弦相似度计算算法进行轻微的简化
精确top k检索加速方法二：
堆排序法N中选K ? 检索时，通常只需要返回前K条结果 ? 可以对所有的文档评分后排序，选出前K个结果，但是这 个排序过程可以避免 ? 令 J = 具有非零余弦相似度值的文档数目 ? 从J中选K个最大的
技巧：相似度为0的不参与建堆（减少建堆开销）
?
精确top K 检索加速方法三：
提前终止计算
? 到目前为止的倒排记录表都按照docID排序
? 接下来将采用与查询无关的另外一种反映结果好坏程度 的指标(静态质量)
? 便宜美国vps 例如: 页面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)
? 策略二：胜者表
? 策略三：静态得分
? 策略四：影响度排序
? 策略五：簇剪枝方法——预处理
? 策略六：参数化索引以及域索引
? 策略七：层次索引
