Shard ranking and cutoff estimation for topically partitioned collections
Shard ranking and cutoff estimation for topically partitioned collections
复制标题
DOI：
10.1145/2396761.2396833
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Anagha Kulkarni;Almer S. Tigelaar;D. Hiemstra;Jamie Callan
中科院分区：
文献类型：
--
作者：
Anagha Kulkarni;Almer S. Tigelaar;D. Hiemstra;Jamie Callan
大型文档集合可以划分为“主题碎片”，以促进分布式搜索。在低资源搜索环境中，只有少数分片可以并行搜索。这样的搜索环境面临着两个相互交织的挑战。首先，确定针对给定查询要咨询哪些分片：分片排名。第二，从排名中参考多少碎片：截止估计。在本文中，我们提出了一个家庭的三个算法，解决这两个问题。作为基础，我们采用了一种常用的数据结构，中央样本索引（CSI），代表碎片的内容。对CSI运行查询会产生一个扁平的文档排名，我们的每个算法都会将其转换为树结构。树的自下而上的遍历被用来推断碎片的排名，并且还被用来估计该排名中的停止点，该停止点产生具有成本效益的选择性分布式搜索。与最先进的碎片排序方法相比，所提出的算法提供了更高的搜索效率，同时提供了相当的搜索效果。
Large document collections can be partitioned into 'topical shards' to facilitate distributed search. In a low-resource search environment only a few of the shards can be searched in parallel. Such a search environment faces two intertwined challenges. First, determining which shards to consult for a given query: shard ranking. Second, how many shards to consult from the ranking: cutoff estimation. In this paper we present a family of three algorithms that address both of these problems. As a basis we employ a commonly used data structure, the central sample index (CSI), to represent the shard contents. Running a query against the CSI yields a flat document ranking that each of our algorithms transforms into a tree structure. A bottom up traversal of the tree is used to infer a ranking of shards and also to estimate a stopping point in this ranking that yields cost-effective selective distributed search. As compared to a state-of-the-art shard ranking approach the proposed algorithms provide substantially higher search efficiency while providing comparable search effectiveness.