[KimelfeldS06]Benny Kimelfeld, Yehoshua Sagiv: Finding and approximating top-k answers in keyword proximity search. PODS 2006:173-182.
温馨提示：“论文导读”旨在推荐他人发表的本领域相关论文。本论文摘要由厦门大学计算机系林子雨老师(http://www.cs.xmu.edu.cn/linziyu)翻译，如果您对该论文细节感兴趣，可以阅读英文原文（全文PDF版权归出版商所有，因此需要到出版商网站下载该论文PDF）。
【摘要】已经有不少研究关注面向关系数据库、XML和WEB的关键词相似搜索，但是，在所有这些方法里，结果都是Q-片段，也就是关于给定数据图G的子树T，T包含了查询Q的所有关键词，并且不存在具有这种性质的T的子树。结果的排序是和结果的尺寸成反比。这里有三个有趣的问题：寻找最优的结果，计算top-k个结果，以及以排序的方式枚举出所有结果。研究已经表明，鉴于数据复杂性，一个可以解决第一个问题的高效算法，也足够可以用来在多项式时间延迟内解决其他两个问题。类似地，为了寻找最优答案的“θ–近似”而设计的高效算法，也可以足够用来在多项式时间延迟内解决如下两个问题。首先，以“（θ+1）–近似”的次序进行枚举。其次，计算 top-k结果的“（θ+1）–近似”。作为一个推论，这篇论文给出了第一个在数据复杂性下的高效算法，来以排序的方式对结果进行枚举，以及计算top-k个结果。同时也给出了高效的算法，它们可以在数据查询复杂性情况下，以一种近似的次序进行枚举，以及计算一个top-k查询的近似。