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: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 2: Ronald Fagin , Ravi Kumar , Kevin S. McCurley , Jasmine Novak , D. Sivakumar , John A. Tomlin , David P. Williamson, Searching the workplace web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775204]
• 3: Tiziano Fagni , Raffaele Perego , Fabrizio Silvestri , Salvatore Orlando, Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.51-78, January 2006 [doi>10.1145/1125857.1125859]
• 4: J.-L. Gailly and M. Adler. Zlib Compression Library. www.zlib.net. Accessed January 2007.
• 5: Steven Garcia , Hugh E. Williams , Adam Cannane, Access-ordered indexes, Proceedings of the 27th Australasian conference on Computer science, p.7-14, January 01, 2004, Dunedin, New Zealand
• 6: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 7: Jade Goldstein , Mark Kantrowitz , Vibhu Mittal , Jaime Carbonell, Summarizing text documents: sentence selection and evaluation metrics, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.121-128, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312665]
• 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: Bernard J. Jansen , Amanda Spink , Jan Pedersen, A temporal comparison of AltaVista Web searching: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.559-570, April 2005 [doi>10.1002/asi.v56:6]
• 10: Julian Kupiec , Jan Pedersen , Francine Chen, A trainable document summarizer, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.68-73, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215333]
• 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: Alistair Moffat , Justin Zobel , Neil Sharman, Text Compression for Dynamic Document Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.302-313, March 1997 [doi>10.1109/69.591454]
• 15: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 16: Dragomir R. Radev , Eduard Hovy , Kathleen McKeown, Introduction to the special issue on summarization, Computational Linguistics, v.28 n.4, p.399-408, December 2002 [doi>10.1162/089120102762671927]
• 17: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 18: Tetsuya Sakai , Karen Sparck-Jones, Generic summaries for indexing in information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.190-198, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383987]
• 19: H. Grogory Silber , Kathleen F. McCoy, Efficiently computed lexical chains as an intermediate representation for automatic text summarization, Computational Linguistics, v.28 n.4, p.487-496, December 2002 [doi>10.1162/089120102762671954]
• 20: Anastasios Tombros , Mark Sanderson, Advantages of query biased summaries in information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.2-10, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290947]
• 21: Ryen W. White , Ian Ruthven , Joemon M. Jose, Finding relevant documents using top ranking sentences: an evaluation of two alternative schemes, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564389]
• 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: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 25: The Zettair Search Engine. www.seg.rmit.edu.au/zettair. Accessed January 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional 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, Measurement, Performance

Keywords:
document caching, snippet generation, web summaries