Empirical Asymptotic Growth of Dynamic Pruning Mechanisms

Abstract

Document-at-a-time query processing can be accelerated through the use of dynamic pruning mechanisms. In this empirical study we measure query time as a function of three numeric and three categorical facets, and infer relationships that allow models of computation time to be established. Using different-sized subsets of three collections, three retrieval models, and three pruning techniques, we quantify the way in which all of collection size, number of documents retrieved, and query length affect query execution times. Despite variations across pruning mechanisms, we find that in combination document retrieval is linear in the collection size when combined with retrieval depth, across all cate- gorical dimensions. Our results allow selection of query processing techniques for specific search tasks, with the choice influenced by collection size, query length, and number of documents retrieved.

Publication
Proceedings of the 3rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval in the Asia Pacific Region (SIGIR-AP 2025)
Date
Links