Quicklink selection for navigational query results
Quicklink selection for navigational query results
复制标题
导航查询结果的快速链接选择
DOI：
10.1145/1526709.1526762
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Kunal Punera
中科院分区：
文献类型：
--
作者：
Deepayan Chakrabarti;Ravi Kumar;Kunal Punera
网站的快速链接是在搜索结果页面上显示在网站主页下方的导航快捷方式，可以让用户直接跳转到网站内的选定点。由于搜索结果页面上的位置是有限且有价值的，因此选择最佳的快速链接集以最大限度地为大多数用户提供好处成为搜索引擎的一个重要问题。利用从浏览器工具栏中获得的用户浏览轨迹和一个简单的概率模型，将快速链接选择问题表述为一个组合优化问题。我们首先证明了目标的硬度，然后提出了一种算法，该算法可证明在最优的1-1/e因子内。我们还提出了一种不同的算法，它适用于树，可以找到最优解；与之前的算法不同，该算法可以在选择的快速链接集上合并自然约束。我们的方法的有效性通过对手动标记的一组网站和一组从现实世界的搜索引擎获得的几个网页的快速链接点击率的经验结果来证明。
Quicklinks for a website are navigational shortcuts displayed below the website homepage on a search results page, and that let the users directly jump to selected points inside the website. Since the real-estate on a search results page is constrained and valuable, picking the best set of quicklinks to maximize the benefits for a majority of the users becomes an important problem for search engines. Using user browsing trails obtained from browser toolbars, and a simple probabilistic model, we formulate the quicklink selection problem as a combinatorial optimizaton problem. We first demonstrate the hardness of the objective, and then propose an algorithm that is provably within a factor of 1-1/e of the optimal. We also propose a different algorithm that works on trees and that can find the optimal solution; unlike the previous algorithm, this algorithm can incorporate natural constraints on the set of chosen quicklinks. The efficacy of our methods is demonstrated via empirical results on both a manually labeled set of websites and a set for which quicklink click-through rates for several webpages were obtained from a real-world search engine.