{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T01:35:46Z","timestamp":1777599346936,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T00:00:00Z","timestamp":1642464000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T00:00:00Z","timestamp":1642464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP200103136"],"award-info":[{"award-number":["DP200103136"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001782","name":"University of Melbourne","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001782","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Inf Retrieval J"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In top-<jats:italic>k<\/jats:italic> ranked retrieval the goal is to efficiently compute an ordered list of the highest scoring <jats:italic>k<\/jats:italic> documents according to some stipulated similarity function such as the well-known BM25 approach. In most implementation techniques a min-heap of size <jats:italic>k<\/jats:italic> is used to track the top scoring candidates. In this work we consider the question of how best to retrieve the <jats:italic>second<\/jats:italic> page of search results, given that a first page has already been computed; that is, identification of the documents at ranks <jats:inline-formula><jats:alternatives><jats:tex-math>$$k+1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to 2<jats:italic>k<\/jats:italic> for some query. Our goal is to understand what information is available as a by-product of the first-page scoring, and how it can be employed to accelerate the second-page computation, assuming that the second-page of results is required for only a fraction of the query load. We propose a range of simple, yet efficient, next-page retrieval techniques which are suitable for accelerating Document-at-a-Time mechanisms, and demonstrate their performance on three large text collections.<\/jats:p>","DOI":"10.1007\/s10791-021-09402-7","type":"journal-article","created":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T11:03:13Z","timestamp":1642503793000},"page":"27-43","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient query processing techniques for next-page retrieval"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7992-4633","authenticated-orcid":false,"given":"Joel","family":"Mackenzie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Petri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alistair","family":"Moffat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,18]]},"reference":[{"key":"9402_CR1","doi-asserted-by":"crossref","unstructured":"Allan, J., Carterette, B., Aslam, J.\u00a0A., Pavlu, V., Dachev, B., & Kanoulas, E. (2007). Million query track 2007 overview. In Proceedings of the text retrieval conference (TREC).","DOI":"10.21236\/ADA477388"},{"key":"9402_CR2","doi-asserted-by":"crossref","unstructured":"Allan, J., Aslam, J.\u00a0A., Carterette, B., Pavlu, V., & Kanoulas, E. (2008). Million query track 2008 overview. In Proceedings of the text retrieval conference (TREC).","DOI":"10.21236\/ADA477388"},{"key":"9402_CR3","doi-asserted-by":"crossref","unstructured":"Azzopardi, L., & Zuccon, G. (2016). Two scrolls or one click: A cost model for browsing search results. In Proceedings of the European conference on information retrieval (ECIR) (pp. 696\u2013702).","DOI":"10.1007\/978-3-319-30671-1_55"},{"key":"9402_CR4","doi-asserted-by":"crossref","unstructured":"Broder, A.\u00a0Z., Carmel, D., Herscovici, M., Soffer, A., & Zien, J. (2003). Efficient query evaluation using a two-level retrieval process. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 426\u2013434).","DOI":"10.1145\/956863.956944"},{"key":"9402_CR5","unstructured":"Carterette, B., Pavlu, V., Fang, H., & Kanoulas, E. (2009). Million query track 2009 overview. In Proceedings of the text retrieval conference (TREC)."},{"key":"9402_CR6","doi-asserted-by":"crossref","unstructured":"Chen, R.-C., Gallagher, L., Blanco, R., & Culpepper, J.\u00a0S. (2017). Efficient cost-aware cascade ranking in multi-stage retrieval. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 445\u2013454).","DOI":"10.1145\/3077136.3080819"},{"key":"9402_CR7","unstructured":"Costa, M., & Silva, M. A. (2010). Search log analysis of a Portuguese web search engine. In INForum \u2013 Simp\u00f3sio de Inform\u00e1tica (pp. 525\u2013536)."},{"key":"9402_CR8","doi-asserted-by":"crossref","unstructured":"Crane, M., Culpepper, J. S., Lin, J., Mackenzie, J., & Trotman, A. (2017). A comparison of Document-at-a-Time and Score-at-a-Time query evaluation. In Proceedings of the ACM international conference on web search and data mining (WSDM) (pp. 201\u2013210).","DOI":"10.1145\/3018661.3018726"},{"issue":"3","key":"9402_CR9","first-page":"178","volume":"6","author":"LLS de Carvalho","year":"2015","unstructured":"de Carvalho, L. L. S., de Moura, E. S., Daoud, C. M., & da Silva, A. S. (2015). Heuristics to improve the BMW method and its variants. Journal of Information and Data Management, 6(3), 178\u2013191.","journal-title":"Journal of Information and Data Management"},{"key":"9402_CR10","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Kabiljo, I., Karrer, B., Ottaviano, G., Pupyrev, S., & Shalita, A. (2016). Compressing graphs and indexes with recursive graph bisection. In Proceedings of the ACM international conference on knowledge discovery and data mining (KDD)(pp. 1535\u20131544).","DOI":"10.1145\/2939672.2939862"},{"key":"9402_CR11","doi-asserted-by":"crossref","unstructured":"Ding, S., & Suel, T. (2011). Faster top-$$k$$ document retrieval using block-max indexes. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 993\u20131002).","DOI":"10.1145\/2009916.2010048"},{"issue":"12","key":"9402_CR12","first-page":"1213","volume":"4","author":"M Fontoura","year":"2011","unstructured":"Fontoura, M., Josifovski, V., Liu, J., Venkatesan, S., Zhu, X., & Zien, J. (2011). Evaluation strategies for top-$$k$$ queries over memory-resident inverted indexes. Proceedings of the Very Large Databases (VLDB), 4(12), 1213\u20131224.","journal-title":"Proceedings of the Very Large Databases (VLDB)"},{"key":"9402_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, B. J., & Spink, A. (2006). How are we searching the world wide web? A comparison of nine search engine transaction logs. Information Processing & Management, 42(1), 248\u2013263.","DOI":"10.1016\/j.ipm.2004.10.007"},{"key":"9402_CR14","doi-asserted-by":"crossref","unstructured":"Jansen, B. J., Spink, A., & Saracevic, T. (2000). Real life, real users, and real needs: a study and analysis of user queries on the web. Information Processing & Management, 36(2), 207\u2013227.","DOI":"10.1016\/S0306-4573(99)00056-4"},{"key":"9402_CR15","doi-asserted-by":"crossref","unstructured":"Kamphuis, C., de\u00a0Vries, A.\u00a0P., Boytsov, L., & Lin, J. (2020). Which BM25 do you mean? A large-scale reproducibility study of scoring variants. In Proceedings of the European conference on information retrieval (ECIR) (pp 28\u201334).","DOI":"10.1007\/978-3-030-45442-5_4"},{"key":"9402_CR16","doi-asserted-by":"crossref","unstructured":"Kane, A., & Tompa, F.\u00a0W. (2018). Split-lists and initial thresholds for WAND-based search. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 877\u2013880).","DOI":"10.1145\/3209978.3210066"},{"key":"9402_CR17","doi-asserted-by":"crossref","unstructured":"Kelly, D., & Azzopardi, L. (2015). How many results per page? A study of SERP size, search behavior and user experience. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 183\u2013192).","DOI":"10.1145\/2766462.2767732"},{"key":"9402_CR18","doi-asserted-by":"crossref","unstructured":"Lin, J., & Yang, P. (2019). The impact of score ties on repeatability in document ranking. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 1125\u20131128).","DOI":"10.1145\/3331184.3331339"},{"key":"9402_CR19","doi-asserted-by":"crossref","unstructured":"Lin, J., Mackenzie, J., Kamphuis, C., Macdonald, C., Mallia, A., Siedlaczek, M., Trotman, A., & de\u00a0Vries, A. (2020). Supporting interoperability between open-source search engines with the common index file format. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 2149\u20132152).","DOI":"10.1145\/3397271.3401404"},{"key":"9402_CR20","doi-asserted-by":"crossref","unstructured":"Mackenzie, J., & Moffat, A. (2020). Examining the additivity of top-$$k$$ query processing innovations. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 1085\u20131094).","DOI":"10.1145\/3340531.3412000"},{"key":"9402_CR21","doi-asserted-by":"crossref","unstructured":"Mackenzie, J., Mallia, A., Petri, M., Culpepper, J.\u00a0S., & Suel, T. (2019). Compressing inverted indexes with recursive graph bisection: A reproducibility study. In Proceedings of the European conference on information retrieval (ECIR) (pp. 339\u2013352).","DOI":"10.1007\/978-3-030-15712-8_22"},{"key":"9402_CR22","doi-asserted-by":"crossref","unstructured":"Mackenzie, J., Benham, R., Petri, M., Trippas, J.\u00a0R., Culpepper, J.\u00a0S., & Moffat, A. (2020). CC-News-En: A large English news corpus. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 3077\u20133084).","DOI":"10.1145\/3340531.3412762"},{"key":"9402_CR23","doi-asserted-by":"crossref","unstructured":"Mallia, A., Ottaviano, G., Porciani, E., Tonellotto, N., & Venturini, R. (2017). Faster BlockMax WAND with variable-sized blocks. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 625\u2013634).","DOI":"10.1145\/3077136.3080780"},{"key":"9402_CR24","first-page":"50","volume":"2019","author":"A Mallia","year":"2019","unstructured":"Mallia, A., Siedlaczek, M., Mackenzie, J., & Suel, T. (2019a). PISA: Performant indexes and search for academia. Proceedings of the OSIRRC workshop at SIGIR, 2019, 50\u201356.","journal-title":"Proceedings of the OSIRRC workshop at SIGIR"},{"key":"9402_CR25","doi-asserted-by":"crossref","unstructured":"Mallia, A., Siedlaczek, M., & Suel, T. (2019b). An experimental study of index compression and DAAT query processing methods. In Proceedings of the European conference on information retrieval (ECIR) (pp. 353\u2013368).","DOI":"10.1007\/978-3-030-15712-8_23"},{"key":"9402_CR26","doi-asserted-by":"crossref","unstructured":"Mallia, A., Siedlaczek, M., Sun, M., & Suel, T. (2020). A comparison of top-k threshold estimation techniques for disjunctive query processing. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 2141\u20132144).","DOI":"10.1145\/3340531.3412080"},{"key":"9402_CR27","doi-asserted-by":"crossref","unstructured":"Mansouri, B., Zahedi, M.\u00a0S., Campos, R., & Farhoodi, M. (2018). Online job search: Study of users\u2019 search behavior using search engine query logs. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 1185\u20131188).","DOI":"10.1145\/3209978.3210125"},{"key":"9402_CR28","doi-asserted-by":"crossref","unstructured":"Matveeva, I., Burges, C., Burkard, T., Laucius, A., & Wong, L. (2006). High accuracy retrieval with multiple nested ranker. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 437\u2013444).","DOI":"10.1145\/1148170.1148246"},{"key":"9402_CR29","doi-asserted-by":"crossref","unstructured":"Petri, M., Moffat, A., Mackenzie, J., Culpepper, J.\u00a0S., & Beck, D. (2019). Accelerated query processing via similarity score prediction. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 485\u2013494).","DOI":"10.1145\/3331184.3331207"},{"key":"9402_CR30","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1561\/1500000019","volume":"3","author":"SE Robertson","year":"2009","unstructured":"Robertson, S. E., & Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3, 333\u2013389.","journal-title":"Foundations and Trends in Information Retrieval"},{"issue":"1","key":"9402_CR31","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/331403.331405","volume":"33","author":"C Silverstein","year":"1999","unstructured":"Silverstein, C., Marais, H., Henzinger, M., & Moricz, M. (1999). Analysis of a very large web search engine query log. SIGIR Forum, 33(1), 6\u201312.","journal-title":"SIGIR Forum"},{"key":"9402_CR32","unstructured":"Spina, D., Maistro, M., Ren, Y., Sadeghi, S., Wong, W., Baldwin, T., Cavedon, L., Moffat, A., Sanderson, M., Scholer, F., & Zobel, J. (2017). Understanding user behavior in job and talent search: An initial investigation. In Proceedings of the SIGIR workshop on eCommerce. http:\/\/ceur-ws.org\/Vol-2311\/paper_2.pdf"},{"issue":"3","key":"9402_CR33","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1002\/1097-4571(2000)9999:9999<::AID-ASI1591>3.0.CO;2-R","volume":"52","author":"A Spink","year":"2001","unstructured":"Spink, A., Wolfram, D., Jansen, B. J., & Saracevic, T. (2001). Searching the web: The public and their queries. Journal of the American Society for Information Science, 52(3), 226\u2013234.","journal-title":"Journal of the American Society for Information Science"},{"key":"9402_CR34","first-page":"40","volume":"2012","author":"A Trotman","year":"2012","unstructured":"Trotman, A., Jia, X.-F., & Crane, M. (2012). Towards an efficient and effective search engine. Proceedings of the OSIR workshop at SIGIR, 2012, 40\u201347.","journal-title":"Proceedings of the OSIR workshop at SIGIR"},{"key":"9402_CR35","doi-asserted-by":"crossref","unstructured":"Trotman, A., Puurula, A., & Burgess, B. (2014). Improvements to BM25 and language models examined. In Proceedings of the Australasian document computing symposium (ADCS) (pp. 58\u201365).","DOI":"10.1145\/2682862.2682863"},{"key":"9402_CR36","doi-asserted-by":"crossref","unstructured":"Wang, L., Lin, J., & Metzler, D. (2011). A cascade ranking model for efficient ranked retrieval. In Proceedings of the ACM international conference on research and development in information retrieval (SIGIR) (pp. 105\u2013114).","DOI":"10.1145\/2009916.2009934"},{"issue":"3","key":"9402_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3015466","volume":"35","author":"RW White","year":"2017","unstructured":"White, R. W., Diaz, F., & Guo, Q. (2017). Search result prefetching on desktop and mobile. ACM Transactions on Information Systems, 35(3), 1\u201334.","journal-title":"ACM Transactions on Information Systems"},{"key":"9402_CR38","doi-asserted-by":"crossref","unstructured":"Wicaksono, A.\u00a0F., & Moffat, A. (2018). Empirical evidence for search effectiveness models. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 1571\u20131574).","DOI":"10.1145\/3269206.3269242"},{"key":"9402_CR39","doi-asserted-by":"crossref","unstructured":"Yafay, E., & Altingovde, I. S. (2019). Caching scores for faster query processing with dynamic pruning in search engines. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 2457\u20132460).","DOI":"10.1145\/3357384.3358154"},{"issue":"4","key":"9402_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3239571","volume":"10","author":"P Yang","year":"2018","unstructured":"Yang, P., Fang, H., & Lin, J. (2018). Anserini: Reproducible ranking baselines using Lucene. ACM Journal of Data and Information Quality, 10(4), 1\u201320.","journal-title":"ACM Journal of Data and Information Quality"},{"key":"9402_CR41","doi-asserted-by":"crossref","unstructured":"Yang, Z., Moffat, A., & Turpin, A. (2016). How precise does document scoring need to be? In Proceedings of the Asia information retrieval societies conference (AIRS) (pp. 279\u2013291).","DOI":"10.1007\/978-3-319-48051-0_21"},{"key":"9402_CR42","unstructured":"Zhang, Y., & Moffat, A. (2006). Some observations on user search behavior. In Proceedings of the Australasian document computing symposium (ADCS) (pp. 1\u20138)."},{"issue":"2","key":"9402_CR43","doi-asserted-by":"publisher","first-page":"6.1","DOI":"10.1145\/1132956.1132959","volume":"38","author":"J Zobel","year":"2006","unstructured":"Zobel, J., & Moffat, A. (2006). Inverted files for text search engines. ACM Computing Surveys, 38(2), 6.1-6.56.","journal-title":"ACM Computing Surveys"}],"container-title":["Information Retrieval Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10791-021-09402-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10791-021-09402-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10791-021-09402-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T06:45:39Z","timestamp":1644389139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10791-021-09402-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,18]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["9402"],"URL":"https:\/\/doi.org\/10.1007\/s10791-021-09402-7","relation":{},"ISSN":["1386-4564","1573-7659"],"issn-type":[{"value":"1386-4564","type":"print"},{"value":"1573-7659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,18]]},"assertion":[{"value":"10 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}