Anytime Ranking on Document-Ordered Indexes

被引:10
作者
Mackenzie, Joel [1 ]
Petri, Matthias [2 ]
Moffat, Alistair [1 ]
机构
[1] Univ Melbourne, Melbourne, Vic, Australia
[2] Amazon Alexa, Manhattan Beach, CA USA
基金
澳大利亚研究理事会;
关键词
Tail latency; dynamic pruning; query processing; web search; EFFICIENCY;
D O I
10.1145/3467890
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Inverted indexes continue to be a mainstay of text search engines, allowing efficient querying of large document collections. While there are a number of possible organizations, document-ordered indexes are the most common, since they are amenable to various query types, support index updates, and allow for efficient dynamic pruning operations. One disadvantage with document-ordered indexes is that high-scoring documents can be distributed across the document identifier space, meaning that index traversal algorithms that terminate early might put search effectiveness at risk. The alternative is impact-ordered indexes, which primarily support top-k disjunctions but also allow for anytime query processing, where the search can be terminated at any time, with search quality improving as processing latency increases. Anytime query processing can be used to effectively reduce high-percentile tail latency that is essential for operational scenarios in which a service level agreement (SLA) imposes response time requirements. In this work, we show how document-ordered indexes can be organized such that they can be queried in an anytime fashion, enabling strict latency control with effective early termination. Our experiments show that processing document-ordered topical segments selected by a simple score estimator outperforms existing anytime algorithms, and allows query runtimes to be accurately limited to comply with SLA requirements.
引用
收藏
页数:32
相关论文
共 78 条
[1]  
Allan J., 2007, P TEXT RETR C TREC 0
[2]  
Altingovde Ismail Sengor, 2008, P SIGIR SING JUL, P861
[3]  
Aly R, 2013, SIGIR'13: THE PROCEEDINGS OF THE 36TH INTERNATIONAL ACM SIGIR CONFERENCE ON RESEARCH & DEVELOPMENT IN INFORMATION RETRIEVAL, P673
[4]   Probabilistic models of information retrieval based on measuring the divergence from randomness [J].
Amati, G ;
Van Rijsbergen, CJ .
ACM TRANSACTIONS ON INFORMATION SYSTEMS, 2002, 20 (04) :357-389
[5]  
Anh V. N., 2006, Proceedings of the Twenty-Ninth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, P372, DOI 10.1145/1148170.1148235
[6]   Load-Sensitive Selective Pruning for Distributed Search [J].
Broccolo, Daniele ;
Macdonald, Craig ;
Orlando, Salvatore ;
Ounis, Iadh ;
Perego, Raffaele ;
Silvestri, Fabrizio ;
Tonellotto, Nicola .
PROCEEDINGS OF THE 22ND ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT (CIKM'13), 2013, :379-388
[7]  
Broder A. Z., P ACM INT C INF KNOW, P426
[8]   Efficiency and effectiveness of query processing in cluster-based retrieval [J].
Can, F ;
Altingövde, IS ;
Demir, E .
INFORMATION SYSTEMS, 2004, 29 (08) :697-717
[9]  
Carterette B., 2008, P TEXT RETR C TREC 0
[10]  
Carterette B., P TEXT RETR C TREC 0