Locality-Based pruning methods for web search

ABSTRACT

This article discusses a novel approach developed for static index pruning that takes into account the locality of occurrences of words in the text. We use this new approach to propose and experiment on simple and effective pruning methods that allow a fast construction of the pruned index. The methods proposed here are especially useful for pruning in environments where the document database changes continuously, such as large-scale web search engines. Extensive experiments are presented showing that the proposed methods can achieve high compression rates while maintaining the quality of results for the most common query types present in modern search engines, namely, conjunctive and phrase queries. In the experiments, our locality-based pruning approach allowed reducing search engine indices to 30% of their original size, with almost no reduction in precision at the top answers. Furthermore, we conclude that even an extremely simple locality-based pruning method can be competitive when compared to complex methods that do not rely on locality information.

REFERENCES

• 1: Charu C. Aggarwal , Fatima Al-Garawi , Philip S. Yu, On the design of a learning crawler for topical resource discovery, ACM Transactions on Information Systems (TOIS), v.19 n.3, p.286-309, July 2001 [doi>10.1145/502115.502119]
• 2: Anderson, T. W. and Finn, J. D. 1997. The New Statistical Analysis of Data, 1st ed. Springer.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Dirk Bahle , Hugh E. Williams , Justin Zobel, Efficient phrase querying with an auxiliary index, 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.564415]
• 5: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 6: Ronald Brandow , Karl Mitze , Lisa F. Rau, Automatic condensation of electronic publications by sentence selection, Information Processing and Management: an International Journal, v.31 n.5, p.675-685, Sept. 1995 [doi>10.1016/0306-4573(95)00052-I]
• 7: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 8: Pável Calado , Berthier Ribeiro-Neto , Nivio Ziviani , Edleno Moura , Ilmério Silva, Local versus global link information in the Web, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.42-63, January 2003 [doi>10.1145/635484.635486]
• 9: James P. Callan, Passage-level evidence in document retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.302-310, July 03-06, 1994, Dublin, Ireland
• 10: 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]
• 11: Junghoo Cho , Hector Garcia-Molina, Effective page refresh policies for Web crawlers, ACM Transactions on Database Systems (TODS), v.28 n.4, p.390-426, December 2003 [doi>10.1145/958942.958945]
• 12: 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]
• 13: Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast and flexible word searching on compressed text, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.113-139, April 2000 [doi>10.1145/348751.348754]
• 14: Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas, G. W., and Harshman, R. A. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Inf. Sci. 41, 6, 391--407.
• 15: H. P. Edmundson, New Methods in Automatic Extracting, Journal of the ACM (JACM), v.16 n.2, p.264-285, April 1969 [doi>10.1145/321510.321519]
• 16: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: David Hawking , Nick Craswell , Paul Thistlewaite , Donna Harman, Results and challenges in Web search evaluation, Proceedings of the eighth international conference on World Wide Web, p.1321-1330, May 1999, Toronto, Canada
• 18: Hawking, D., Voorhees, E., Bailey, P., and Craswell, N. 1999. Overview of Trec-8 Web track. In Proceedings of the Text Retrieval Conference (TREC-8). Gaithersburg, MD, 131--150.
• 19: Hawking, D., Craswell, N., and Thistlewaite, P. B. 1998. Overview of TREC-7 very large collection track. In Proceedings of the Text Retrieval Conference (TREC-7), Gaithersburg, MD, 91--104.
• 20: Hovy, E. H. and Lin, C.-Y. 1998. Automated text summarization in SUMMARIST. In Advances in Automated Text Summarization, I. Mani and M. Maybury, eds. MIT Press, 81--94.
• 21: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 22: Xiaoyong Liu , W. Bruce Croft, Passage retrieval based on language models, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584854]
• 23: Daniel Mallett , James Elding , Mario A. Nascimento, Information-Content Based Sentence Extraction for Text Summarization, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04) Volume 2, p.214, April 05-07, 2004
• 24: Sergey Melink , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the web, ACM Transactions on Information Systems (TOIS), v.19 n.3, p.217-241, July 2001 [doi>10.1145/502115.502116]
• 25: Gonzalo Navarro , Edleno Silva De Moura , Marden Neubert , Nivio Ziviani , Ricardo Baeza-Yates, Adding Compression to Block Addressing Inverted Indexes, Information Retrieval, v.3 n.1, p.49-77, July 2000 [doi>10.1023/A:1009934302807]
• 26: Tadashi Nomoto , Yuji Matsumoto, A new approach to unsupervised text summarization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.26-34, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383956]
• 27: 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]
• 28: Daniel E. Rose , Danny Levinson, Understanding user goals in web search, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988675]
• 29: Andrew Rosenbloom, Introduction, Communications of the ACM, v.47 n.12, December 2004 [doi>10.1145/1035134.1035161]
• 30: 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]
• 31: Gerard Salton , J. Allan , Chris Buckley, Approaches to passage retrieval in full text information systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-58, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160693]
• 32: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 33: Mark Sanderson , Justin Zobel, Information retrieval system evaluation: effort, sensitivity, and reliability, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076064]
• 34: Silverstein, C., Henzinger, M., Marais, H., and Moricz, M. 1998. Analysis of a very large Altavista query log. Tech. Rep. 14, Systems Research Center Laboratory. October.
• 35: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 36: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

General Terms:
Algorithms, Performance

Keywords:
Pruning, indexing, information retrieval, search, search engines, web search