Fast generation of result snippets in web search

ABSTRACT

The presentation of query biased document snippets as part of results pages presented by search engines has become an expectation of search engine users. In this paper we explore the algorithms and data structures required as part of a search engine to allow efficient generation of query biased snippets. We begin by proposing and analysing a document compression method that reduces snippet generation time by 58% over a baseline using the zlib compression library. These experiments reveal that finding documents on secondary storage dominates the total cost of generating snippets, and so caching documents in RAM is essential for a fast snippet generation process. Using simulation, we examine snippet generation performance for different size RAM caches. Finally we propose and analyse document reordering and compaction, revealing a scheme that increases the number of document cache hits with only a marginal affect on snippet quality. This scheme effectively doubles the number of documents that can fit in a fixed size cache.

References

1. S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. In WWW7, pages 107--117, 1998.
2. R. Fagin, Ravi K., K. S. McCurley, J. Novak, D. Sivakumar, J. A. Tomlin, and D. P. Williamson. Searching the workplace web. In WWW2003, Budapest, Hungary, May 2003.
3. T. Fagni, R. Perego, F. Silvestri, and S. Orlando. Boosting the performance of web search engines: Caching and prefetching query results by exploiting historical usage data. ACM Trans. Inf. Syst., 24(1):51--78, 2006.
4. J.-L. Gailly and M. Adler. Zlib Compression Library. www.zlib.net. Accessed January 2007.
5. S. Garcia, H. E. Williams, and A. Cannane. Access-ordered indexes. In V. Estivill-Castro, editor, Proc. Australasian Computer Science Conference, pages 7--14, Dunedin, New Zealand, 2004.
6. S. Ghemawat, H. Gobioff, and S. Leung. The google ?le system. In SOSP '03: Proc. of the 19th ACM Symposium on Operating Systems Principles, pages 29--43, New York, NY, USA, 2003. ACM Press.
7. J. Goldstein, M. Kantrowitz, V. Mittal, and J. Carbonell. Summarizing text documents: sentence selection and evaluation metrics. In SIGIR99, pages 121--128, 1999.
8. D. Hawking, Nick C., and Paul Thistlewaite. Overview of TREC-7 Very Large Collection Track. In Proc. of TREC-7, pages 91--104, November 1998.
9. B. J. Jansen, A. Spink, and J. Pedersen. A temporal comparison of altavista web searching. J. Am. Soc. Inf. Sci. Tech. (JASIST), 56(6):559--570, April 2005.
10. J. Kupiec, J. Pedersen, and F. Chen. A trainable document summarizer. In SIGIR95, pages 68--73, 1995.
11. S. Lawrence and C. L. Giles. Accessibility of information on the web. Nature, 400:107--109, July 1999.
12. H. P. Luhn. The automatic creation of literature abstracts. IBM Journal, pages 159--165, April 1958.
13. I. Mani. Automatic Summarization, volume 3 of Natural Language Processing. John Benjamins Publishing Company, Amsterdam/Philadelphia, 2001.
14. A. Moffat, J. Zobel, and N. Sharman. Text compression for dynamic document databases. Knowledge and Data Engineering, 9(2):302--313, 1997.
15. G. Navarro and V. Mäkinen.Compressed full text indexes. ACM Computing Surveys, 2007. To appear.
16. D. R. Radev, E. Hovy, and K. McKeown. Introduction to the special issue on summarization. Comput. Linguist., 28(4):399--408, 2002.
17. M. Richardson, A. Prakash, and E. Brill. Beyond pagerank: machine learning for static ranking. In WWW06, pages 707--715, 2006.
18. T. Sakai and K. Sparck-Jones. Generic summaries for indexing in information retrieval. In SIGIR01, pages 190--198, 2001.
19. H. G. Silber and K. F. McCoy. Efficiently computed lexical chains as an intermediate representation for automatic text summarization. Comput. Linguist., 28(4):487--496, 2002.
20. A. Tombros and M. Sanderson. Advantages of query biased summaries in information retrieval. In SIGIR98, pages 2--10, Melbourne, Aust., August 1998.
21. R. W. White, I. Ruthven, and J. M. Jose. Finding relevant documents using top ranking sentences: an evaluation of two alternative schemes. In SIGIR02, pages 57--64, 2002.
22. H. E. Williams and J. Zobel. Compressing integers for fast ?le access. Comp. J., 42(3):193--201, 1999.
23. H. E. Williams and J. Zobel. Searchable words on the Web. International Journal on Digital Libraries, 5(2):99--105, April 2005.
24. I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishing, San Francisco, second edition, May 1999.
25. The Zettair Search Engine. www.seg.rmit.edu.au/zettair. Accessed January 2007.

Index Terms

• Information systems

  • Information retrieval

    • Evaluation of retrieval results

    • Information retrieval query processing