Full Text:   <1861>

Summary:  <1504>

CLC number: TP393

On-line Access: 2016-01-05

Received: 2015-06-06

Revision Accepted: 2015-10-14

Crosschecked: 2015-12-24

Cited: 1

Clicked: 7385

Citations:  Bibtex RefMan EndNote GB/T7714


Kun Jiang


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2016 Vol.17 No.1 P.1-14


Efficient dynamic pruning on largest scores first (LSF) retrieval

Author(s):  Kun Jiang, Yue-xiang Yang

Affiliation(s):  College of Computer, National University of Defense Technology, Changsha 410073, China

Corresponding email(s):   jk_365@126.com

Key Words:  Inverted index, Index traversal, Query latency, Largest scores first (LSF) retrieval, Dynamic pruning

Share this article to: More |Next Article >>>

Kun Jiang, Yue-xiang Yang. Efficient dynamic pruning on largest scores first (LSF) retrieval[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(1): 1-14.

@article{title="Efficient dynamic pruning on largest scores first (LSF) retrieval",
author="Kun Jiang, Yue-xiang Yang",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Efficient dynamic pruning on largest scores first (LSF) retrieval
%A Kun Jiang
%A Yue-xiang Yang
%J Frontiers of Information Technology & Electronic Engineering
%V 17
%N 1
%P 1-14
%@ 2095-9184
%D 2016
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500190

T1 - Efficient dynamic pruning on largest scores first (LSF) retrieval
A1 - Kun Jiang
A1 - Yue-xiang Yang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 17
IS - 1
SP - 1
EP - 14
%@ 2095-9184
Y1 - 2016
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500190

inverted index traversal techniques have been studied in addressing the query processing performance challenges of web search engines, but still leave much room for improvement. In this paper, we focus on the inverted index traversal on document-sorted indexes and the optimization technique called dynamic pruning, which can efficiently reduce the hardware computational resources required. We propose another novel exhaustive index traversal scheme called largest scores first (LSF) retrieval, in which the candidates are first selected in the posting list of important query terms with the largest upper bound scores and then fully scored with the contribution of the remaining query terms. The scheme can effectively reduce the memory consumption of existing term-at-a-time (TAAT) and the candidate selection cost of existing document-at-a-time (DAAT) retrieval at the expense of revisiting the posting lists of the remaining query terms. Preliminary analysis and implementation show comparable performance between LSF and the two well-known baselines. To further reduce the number of postings that need to be revisited, we present efficient rank safe dynamic pruning techniques based on LSF, including two important optimizations called list omitting (LSF_LO) and partial scoring (LSF_PS) that make full use of query term importance. Finally, experimental results with the TREC GOV2 collection show that our new index traversal approaches reduce the query latency by almost 27% over the WAND baseline and produce slightly better results compared with the MaxScore baseline, while returning the same results as exhaustive evaluation.

This paper studies the traversal on inverted index to support efficient top-k search queries. The focus is on document-sorted inverted indexes, and the authors propose a new index traversal algorithm (LSF) and two associated dynamic pruning techniques to reduce the search space and memory consumption in practice. Moreover, the pruning technique is rank safe, so that the results would be the same as if an exhaustive search is performed. Experiments are performend with TREC GOV2 collection, where the two proposed pruning techniques are compared with two popular ones in the literature (WAND and MaxScore), and the results show that one of the proposed pruning techniques (LSF_PS) improves WAND by 27% in query latency, and has slightly better performance than MaxScore. The paper is very well-written, and the results are intereseting.


创新点:提出最大重要度优先(Largest Scores First,LSF)查询算法,使得具有较高重要度的查询词项所指向的倒排链表能够优先得到处理。提出两种精确的动态剪枝算法:基于LSF的去除倒排链表技术(List Omitting,LSF_LO)和基于LSF的文档部分打分技术(Partial Scoring,LSF_PS)。


Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Anh, V.N., Moffat, A., 2005. Simplified similarity scoring using term ranks. Proc. 28th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.226-233.

[2]Anh, V.N., Moffat, A., 2006. Pruned query evaluation using pre-computed impacts. Proc. 29th Annual ACM SIGIR Conf. on Research and Development in Information Retrieval, p.372-379.

[3]Anh, V.N., Moffat, A., 2010. Index compression using 64-bit words. Softw. Pract. Exper., 40(2):131-147.

[4]Badue, C., Ribeiro-Neto, B., Baeza-Yates, R., et al., 2001. Distributed query processing using partitioned inverted files. Proc. 8th Int. Symp. on String Processing and Information Retrieval, p.10-20.

[5]Broder, A.Z., Carmel, D., Herscovici, M., et al., 2003. Efficient query evaluation using a two-level retrieval process. Proc. 12th Int. Conf. on Information and Knowledge Management, p.426-434.

[6]Buckley, C., Lewit, A.F., 1985. Optimization of inverted vector searches. Proc. 8th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.97-110.

[7]Büttcher, S., Clarke, C.L.A., 2007. Index compression is good, especially for random access. Proc. 16th ACM Conf. on Information and Knowledge Management, p.761-770.

[8]Büttcher, S., Clarke, C.L.A., Cormack, G.V., 2010. Information Retrieval: Implementing and Evaluating Search Engines. The MIT Press, USA.

[9]Chakrabarti, K., Chaudhuri, S., Ganti, V., 2011. Interval-based pruning for top-k processing over compressed lists. Proc. 27th Int. Conf. on Data Engineering, p.709-720.

[10]Croft, B., Metzler, D., Strohman, T., 2010. Search Engines: Information Retrieval in Practice. Addison Wesley, USA.

[11]Dean, J., 2009. Challenges in building large-scale information retrieval systems: invited talk. Proc. 2nd ACM Int. Conf. on Web Search and Data Mining, p.1.

[12]Delbru, R., Campinas, S., Tummarello, G., 2012. Searching web data: an entity retrieval and high-performance indexing model. Web Semant. Sci. Serv. Agents World Wide Web, 10:33-58.

[13]Dimopoulos, C., Nepomnyachiy, S., Suel, T., 2013. Optimizing top-k document retrieval strategies for block-max indexes. Proc. 6th ACM Int. Conf. on Web Search and Data Mining, p.113-122.

[14]Ding, S., Suel, T., 2011. Faster top-k document retrieval using block-max indexes. Proc. 34th Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.993-1002.

[15]Fontoura, M., Josifovski, V., Liu, J.H., et al., 2011. Evaluation strategies for top-k queries over memory-resident inverted indexes. Proc. VLDB Endow., p.1213-1224.

[16]Jiang, K., Yang, Y.X., 2015. Exhaustive hybrid posting lists traversing technique. Proc. 5th Int. Conf. on Intelligence Science and Big Data Engineering, p.1-11.

[17]Jiang, K., Song, X.S., Yang, Y.X., 2014. Performance evaluation of inverted index traversal techniques. Proc. 17th Int. Conf. on Computational Science and Engineering, p.1715-1720.

[18]Jonassen, S., Bratsberg, S.E., 2011. Efficient compressed inverted index skipping for disjunctive text-queries. Proc. 33rd European Conf. on Advances in Information Retrieval, p.530-542.

[19]Lacour, P., Macdonald, C., Ounis, I., 2008. Efficiency comparison of document matching techniques. Proc. European Conf. on Information Retrieval, p.37-46.

[20]Lester, N., Moffat, A., Webber, W., et al., 2005. Space-limited ranked query evaluation using adaptive pruning. Proc. 6th Int. Conf. on Web Information Systems Engineering, p.470-477.

[21]Macdonald, C., Ounis, I., Tonellotto, N., 2011. Upper-bound approximations for dynamic pruning. ACM Trans. Inform. Syst., 29(4):17.1-17.28.

[22]Manning, C.D., Raghavan, P., Schütze, H., 2008. Introduction to Information Retrieval. Cambridge University Press, Cambridge, USA.

[23]Melink, S., Raghavan, S., Yang, B., et al., 2001. Building a distributed full-text index for the Web. Proc. 10th Int. Conf. on World Wide Web, p.396-406.

[24]Moffat, A., Zobel, J., 1996. Self-indexing inverted files for fast text retrieval. ACM Trans. Inform. Syst., 14(4):349-379.

[25]Ounis, I., Amati, G., Plachouras, V., et al., 2006. Terrier: a high performance and scalable information retrieval platform. Proc. OSIR Workshop, p.18-25.

[26]Puppin, D., Silvestri, F., Perego, R., et al., 2010. Tuning the capacity of search engines: load-driven routing and incremental caching to reduce and balance the load. ACM Trans. Inform. Syst., 28(2):5.1-5.36.

[27]Silvestri, F., Venturini, R., 2010. VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming. Proc. 19th ACM Int. Conf. on Information and Knowledge Management, p.1219-1228.

[28]Strohman, T., Croft, W.B., 2007. Efficient document retrieval in main memory. Proc. 30th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.175-182.

[29]Strohman, T., Turtle, H., Croft, W.B., 2005. Optimization strategies for complex queries. Proc. 28th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.219-225.

[30]Turtle, H., Flood, J., 1995. Query evaluation: strategies and optimizations. Inform. Process. Manag., 31(6):831-850.

[31]Wang, L.D., Lin, J., Metzler, D., 2011. A cascade ranking model for efficient ranked retrieval. Proc. 34th Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.105-114.

[32]Zobel, J., Moffat, A., 2006. Inverted files for text search engines. ACM Comput. Surv., 38(2):6.1-6.56.

[33]Zukowski, M., Heman, S., Nes, N., et al., 2006. Super-scalar RAM-CPU cache compression. Proc. 22nd Int. Conf. on Data Engineering, p.59.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE