Dynamic index pruning for effective caching

ABSTRACT

RAM and dynamic pruning schemes to reduce query evaluation times. While only a small portion of lists are processed with dynamic pruning, current systems still store the entire inverted list in cache. In this paper we investigate caching only the pieces of the inverted lists that are actually used to answer a query during dynamic pruning. We examine an LRU cache model, and two recently proposed models. We also introduce a new dynamic pruning scheme for impact-ordered inverted lists.

Using two large web collections and corresponding query logs we show that, using an LRU cache, our new pruning scheme reduces the number of disk accesses during query processing time by 7%-15% over the state-of-the-art impact-ordered baseline, without reducing answer quality. Surprisingly, however, we discover that using our new pruning scheme makes little difference to disk traffic when the more sophisticated caching schemes are employed.

REFERENCES

• 1: V. N. Anh. Impact-based Document Retrieval. PhD thesis, Department of Computer Science and Software Engineering, The University of Melbourne, 2004.
• 2: Vo Ngoc Anh , Alistair Moffat, Pruned query evaluation using pre-computed impacts, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148235]
• 3: S. Büttcher and C. L. A. Clarke. A document-centric approach to static index pruning in text retrieval systems. In CIKM, 2006.
• 4: Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
• 5: David Carmel , Doron Cohen , Ronald Fagin , Eitan Farchi , Michael Herscovici , Yoelle S. Maarek , Aya Soffer, Static index pruning for information retrieval systems, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.43-50, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383958]
• 6: Edleno S. de Moura , Célia F. dos Santos , Daniel R. Fernandes , Altigran S. Silva , Pavel Calado , Mario A. Nascimento, Improving Web search efficiency via a locality based static pruning method, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060783]
• 7: S. Garcia. Search Engine Optimisation Using Past Queries. PhD thesis, School of Computer Science and IT, RMIT, 2007.
• 8: David Hawking, Efficiency/effectiveness trade-offs in query processing (from theory into practice workshop, 1998 SIGIR conf.), ACM SIGIR Forum, v.32 n.2, p.16-22, Sept. 1998 [doi>10.1145/305110.305119]
• 9: D. Hawking, N. Craswell, and P. Thistlewaite. Overview of TREC-7 Very Large Collection Track. In Proc. of TREC-7, 1998.
• 10: B. J. Jansen and A. Spink. An analysis of web documents retrieved and viewed. In H. R. Arabnia and Y. Mun, editors, International Conference on Internet Computing, 2003.
• 11: Xiaohui Long , Torsten Suel, Three-Level Caching for Efficient Query Processing in Large Web Search Engines, World Wide Web, v.9 n.4, p.369-395, December 2006 [doi>10.1007/s11280-006-0221-0]
• 12: Alistair Moffat , William Webber , Justin Zobel , Ricardo Baeza-Yates, A pipelined architecture for distributed text query evaluation, Information Retrieval, v.10 n.3, p.205-231, June 2007 [doi>10.1007/s10791-006-9014-4]
• 13: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 14: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• 15: Paricia Correia Saraiva , Edleno Silva de Moura , Novio Ziviani , Wagner Meira , Rodrigo Fonseca , Berthier Riberio-Neto, Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.51-58, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383959]
• 16: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 17: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
caching, efficiency, inverted lists, search engines