Efficient query evaluation using a two-level retrieval process
Abstract
We present an efficient query evaluation method based on a two level approach: at the first level, our method iterates in parallel over query term postings and identifies candidate documents using an approximate evaluation taking into account only partial information on term occurrences and no query independent factors; at the second level, promising candidates are fully evaluated and their exact scores are computed. The efficiency of the evaluation process can be improved significantly using dynamic pruning techniques with very little cost in effectiveness. The amount of pruning can be controlled by the user as a function of time allocated for query evaluation. Experimentally, using the TREC Web Track data, we have determined that our algorithm significantly reduces the total number of full evaluations by more than 90%, almost without any loss in precision or recall. At the heart of our approach there is an efficient implementation of a new Boolean construct called WAND or Weak AND that might be of independent interest.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
After the hash function is computed, retrieval of items can be implemented with a two-level retrieval process based on the Weak AND operator.
“After the hash function is computed, retrieval of items can be implemented with a two-level retrieval process based on the Weak AND operator [5].”
From Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018) · cites this paper as [5]
Cites
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004 · see citing works
Space/time trade-offs in hash coding with allowable errors
Bloom, B. (1970) · CACM · doi:10.1145/362686.362692 · Cited by 8,424 · see citing works
Extended Boolean information retrieval
Salton, G., Fox, E. A., & Wu, H. (1983) · Communications of the ACM · doi:10.1145/182.358466 · Cited by 1,058 · see citing works
Query evaluation: Strategies and optimizations
Turtle, H. R., & Flood, J. (1995) · Information Processing & Management · doi:10.1016/0306-4573(95)00020-h · Cited by 306 · see citing works
Optimization of inverted vector searches
Buckley, C., & Lewit, A. F. (1985) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/253495.253515 · Cited by 217 · see citing works
Optimal semijoins for distributed database systems
Mullin, J. K. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.52778 · Cited by 159 · see citing works
Retrieving records from a gigabyte of text on a minicomputer using statistical ranking
Harman, D. K., & Candela, G. T. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199012)41:8 · Cited by 129 · see citing works
The ninth text REtrieval conference (TREC-9)
(2001) · doi:10.6028/nist.sp.500-249 · Cited by 114 · see citing works
Document filtering for fast ranking
Persin, M. (1994) · doi:10.5555/188490.188597 · Cited by 72 · see citing works
Full text indexing based on lexical relations an application: software libraries
Maarek, Y., & Smadja, F. Z. (1989) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/75334.75355 · Cited by 71 · see citing works
Compressed inverted files with reduced decoding overheads
Vo, A. N., & Moffat, A. (1998) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/290941.291011 · Cited by 59 · see citing works
Juru at TREC 10 - Experiments with Index Pruning.
Carmel, D., Amitay, E., Herscovici, M., et al. (2001) · Cited by 47 · see citing works
Self-citationMoffet, A., & Zobel, J. (2002) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde.1994.283064 · Cited by 27 · see citing works
A fast match for continuous speech recognition using allophonic models
Bahl, L. R., de Souza, P. V., Gopalakrishnan, P. S., et al. (1992) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1992.225983 · Cited by 19 · see citing works
Term-ordered query evaluation versus document-ordered query evaluation for large document databases
Kaszkiel, M., & Zobel, J. (1998) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/290941.291031 · Cited by 13 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Graph Convolutional Neural Networks for Web-Scale Recommender Systems
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., & Leskovec, J. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3219890 · Cited by 3,733 · see citing works
- Authors
- Broder, A. Z., Carmel, D., Herscovici, M., Soffer, A., & Zien, J.
- Affiliations
- IBM (United States) (US)
- IBM Research - Haifa (IL)
- IBM Research - Almaden (US)
- Venue
- Proceedings of the twelfth international conference on Information and knowledge management
- Publisher
- ACM
- Published
- 2003-11-03
- Pages
- 426-434
- ISSN
- 2155-0751 (ISSN-L)
- OpenAlex
- W2154610494
- Cited by
- 407
- References
- 15
- Citations by year
- 2026: 12 · 2025: 12 · 2024: 18 · 2023: 12 · 2022: 14 · 2021: 12 · 2020: 22 · 2019: 18 · 2018: 27 · 2017: 38 · 2016: 29 · 2015: 25 · 2014: 34 · 2013: 30 · 2012: 29
- FWCI
- 4.28
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM International Conference on Information and Knowledge Management (CIKM) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Database Systems and Queries
- Keywords
- query processing, dynamic pruning, TREC Web Track
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
