More Web Proxy on the site http://driver.im/

poster

Fast candidate generation for two-phase document ranking: postings list intersection with bloom filters

Authors:

Jimmy LinAuthors Info & Claims

CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

Pages 2419 - 2422

https://doi.org/10.1145/2396761.2398656

Published: 29 October 2012 Publication History

Abstract

Most modern web search engines employ a two-phase ranking strategy: a candidate list of documents is generated using a "cheap" but low-quality scoring function, which is then reranked by an "expensive" but high-quality method (usually machine-learned). This paper focuses on the problem of candidate generation for conjunctive query processing in this context. We describe and evaluate a fast, approximate postings list intersection algorithms based on Bloom filters. Due to the power of modern learning-to-rank techniques and emphasis on early precision, significant speedups can be achieved without loss of end-to-end retrieval effectiveness. Explorations reveal a rich design space where effectiveness and efficiency can be balanced in response to specific hardware configurations and application scenarios.

References

[1]

J. Barbay, A. López-Ortiz, and T. Lu. Faster adaptive set intersections for text searching. Workshop on Experimental Algorithms, 2006.

Digital Library

[2]

B. Bloom. Space/time trade-offs in hash coding with allowable errors. CACM, 13(7):422--426, 1970.

Digital Library

[3]

P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid, and Y. Tang. On the false-positive rate of Bloom filters. Information Processing Letters, 108:210--213, October 2008.

Digital Library

[4]

A. Broder, D. Carmel, M. Herscovici, A. Soffer, and J. Zien. Efficient query evaluation using a two-level retrieval process. CIKM, 2003.

Digital Library

[5]

C. Burges. From RankNet to LambdaRank to LambdaMART: An overview. Technical Report MSR-TR-2010--82, Microsoft Research, 2010.

[6]

M. Busch, K. Gade, B. Larson, P. Lok, S. Luckenbill, and J. Lin. Earlybird: Real-time search at Twitter. ICDE, 2012.

Digital Library

[7]

G. Cormack, M. Smucker, and C. Clarke. Efficient and effective spam filtering and re-ranking for large web datasets. CoRR, abs/1004.5168, 2010.

[8]

E. Demaine, A. López-Ortiz, and J. Munro. Experiments on adaptive set intersections for text retrieval systems. Workshop on Algorithm Engineering and Experiments, 2001.

Digital Library

[9]

Y. Ganjisaffar, R. Caruana, and C. Lopes. Bagging gradient-boosted trees for high precision, low variance ranking models. SIGIR, 2011.

Digital Library

[10]

K. J\"arvelin and J. Kek\"al\"ainen. Cumulative gain-based evaluation of IR techniques. ACM TOIS, 20(4):422--446, 2002.

Digital Library

[11]

H. Li. Learning to Rank for Information Retrieval and Natural Language Processing. Morgan & Claypool, 2011.

Digital Library

[12]

J. Li, B. T. Loo, J. Hellerstein, M. Kaashoek, D. Karger, and R. Morris. On the feasibility of peer-to-peer web indexing and search. Workshop on Peer-to-Peer Systems, 2003.

[13]

J. Lin, D. Metzler, T. Elsayed, and L. Wang. Of Ivory and Smurfs: Loxodontan MapReduce experiments for web search. TREC, 2009.

[14]

D. Metzler. Automatic feature selection in the Markov random field model for information retrieval. CIKM, 2007.

Digital Library

[15]

G. Pass, A. Chowdhury, and C. Torgeson. A picture of search. Conference on Scalable Information Systems, 2006.

Digital Library

[16]

M. Shepherd, W. Phillips, and C.-K. Chu. A fixed-size Bloom filter for searching textual documents. The Computer Journal, 32(3):212--219, 1989.

Digital Library

[17]

S. Tatikonda, B. Cambazoglu, and F. Junqueira. Posting list intersection on multicore architectures. SIGIR, 2011.

Digital Library

[18]

D. Tsirogiannis, S. Guha, and N. Koudas. Improving the performance of list intersection. VLDB, 2009.

Digital Library

[19]

M. Zukowski, S. Heman, N. Nes, and P. Boncz. Super-scalar RAM-CPU cache compression. ICDE 2006, April 2006.

Digital Library

Cited By

Fröbe MMackenzie JMitra BNardini FPotthast MHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)ReNeuIR at SIGIR 2024: The Third Workshop on Reaching Efficiency in Neural Information RetrievalProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657994(3051-3054)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657994
Lalla SLu RGuan YZhang S(2024)BloomDT - An Improved Privacy-Preserving Decision Tree Inference SchemeJournal of Information and Intelligence10.1016/j.jiixd.2024.02.003Online publication date: Feb-2024
https://doi.org/10.1016/j.jiixd.2024.02.003
Bruch SNardini FIngber ALiberty E(2023)An Approximate Algorithm for Maximum Inner Product Search over Streaming Sparse VectorsACM Transactions on Information Systems10.1145/360979742:2(1-43)Online publication date: 8-Nov-2023
https://dl.acm.org/doi/10.1145/3609797
Show More Cited By

Index Terms

Fast candidate generation for two-phase document ranking: postings list intersection with bloom filters
1. Information systems
  1. Information retrieval

Recommendations

Speeding up Document Ranking with Rank-based Features
SIGIR '15: Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval

Learning to Rank (LtR) is an effective machine learning methodology for inducing high-quality document ranking functions. Given a query and a candidate set of documents, where query-document pairs are represented by feature vectors, a machine-learned ...
Quality-biased ranking for queries with commercial intent
WWW '13 Companion: Proceedings of the 22nd International Conference on World Wide Web

Modern search engines are good enough to answer popular commercial queries with mainly highly relevant documents. However, our experiments show that users behavior on such relevant commercial sites may differ from one to another web-site with the same ...
Ranking Relevance in Yahoo Search
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Search engines play a crucial role in our daily lives. Relevance is the core problem of a commercial search engine. It has attracted thousands of researchers from both academia and industry and has been studied for decades. Relevance in a modern search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

October 2012

2840 pages

ISBN:9781450311564

DOI:10.1145/2396761

General Chair:
Xuewen Chen
Wayne State University, USA
,
Program Chairs:
Guy Lebanon
Georgia Institute of Technology
,
Haixun Wang
Microsoft Research Asia
,
Mohammed J. Zaki
Rensselaer Polytechnic Institute

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

CIKM'12

Sponsor:

CIKM'12: 21st ACM International Conference on Information and Knowledge Management

October 29 - November 2, 2012

Hawaii, Maui, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
211
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fröbe MMackenzie JMitra BNardini FPotthast MHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)ReNeuIR at SIGIR 2024: The Third Workshop on Reaching Efficiency in Neural Information RetrievalProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657994(3051-3054)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657994
Lalla SLu RGuan YZhang S(2024)BloomDT - An Improved Privacy-Preserving Decision Tree Inference SchemeJournal of Information and Intelligence10.1016/j.jiixd.2024.02.003Online publication date: Feb-2024
https://doi.org/10.1016/j.jiixd.2024.02.003
Bruch SNardini FIngber ALiberty E(2023)An Approximate Algorithm for Maximum Inner Product Search over Streaming Sparse VectorsACM Transactions on Information Systems10.1145/360979742:2(1-43)Online publication date: 8-Nov-2023
https://dl.acm.org/doi/10.1145/3609797
Bruch SLucchese CNardini F(2023)Report on the 1st Workshop on Reaching Efficiency in Neural Information Retrieval (ReNeuIR 2022) at SIGIR 2022ACM SIGIR Forum10.1145/3582900.358291656:2(1-14)Online publication date: 31-Jan-2023
https://dl.acm.org/doi/10.1145/3582900.3582916
Bruch SMackenzie JMaistro MNardini FChen HDuh WHuang HKato MMothe JPoblete B(2023)ReNeuIR at SIGIR 2023: The Second Workshop on Reaching Efficiency in Neural Information RetrievalProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591922(3456-3459)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1145/3539618.3591922
Bruch SLucchese CNardini FAmigo ECastells PGonzalo JCarterette BCulpepper JKazai G(2022)ReNeuIR: Reaching Efficiency in Neural Information RetrievalProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3477495.3531704(3462-3465)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3477495.3531704
Hron JKrauth KJordan MKilbertus NRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)On component interactions in two-stage recommender systemsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540471(2744-2757)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540471
Chen JJiang CWang CZhou SFeng YChen CEster MHe X(2021)CoSam: An Efficient Collaborative Adaptive Sampler for RecommendationACM Transactions on Information Systems10.1145/345028939:3(1-24)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1145/3450289
He JWu KKannan SArpaci-Dusseau AArpaci-Dusseau RNoh SWelch B(2020)Read as neededProceedings of the 18th USENIX Conference on File and Storage Technologies10.5555/3386691.3386698(59-74)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.5555/3386691.3386698
Li YHuang JFan MLei JWang HChen E(2020)Personalized Query Auto-Completion for Large-Scale POI Search at Baidu MapsACM Transactions on Asian and Low-Resource Language Information Processing10.1145/339413719:5(1-16)Online publication date: 18-Jun-2020
https://dl.acm.org/doi/10.1145/3394137
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents